从品牌网站建设到网络营销策划,从策略到执行的一站式服务
算法解析
创新互联坚实的技术研发基础赢得了行业内的良好口碑,公司成立十余年来,为千余家企业提供过网站建设、软件开发、搜索引擎优化技术、互联网大数据整合营销服务,多年的技术服务成功经验、众多的客户使我们能懂得更多,做得更好。"让您的网站跑起来"是我们一直追求的目标!根据二叉排序树的定义,对二叉树进行递归遍历,左子树关键字比根结点关键字小,右子树的关键字比根结点的关键字大,一旦有不满足条件则可判断不是二叉排序树。通过参数 flag 的值来判断,flag 为 1 表示是二叉排序树,为 0 则表示非二叉排序树,flag 初值为 1。设定全局变量 pre(初始值为 NULL)来指向遍历过程结点的前驱。
代码
void JudgeBST(BiTree T, int &flag)
{//判断二叉树是否为二叉排序树
if(T != NULL && flag)
{JudgeBST(T->lchild, flag); //中序遍历左子树
if(pre == NULL) //中序遍历的第一个结点不必判断
pre = T;
else if(pre->data< T->data)
pre = T; //前驱指针指向当前结点
else flag = 0; //不是二叉排序树
JudgeBST(T->rchild, flag); //中序遍历右子树
}
}
思路2
对二叉排序树来说,其中序遍历序列为一个递增有序序列,因此,对
给定的二叉树进行中序遍历,如果始终能保持前一个值比后一个值小,则说明该二叉树是一棵二叉排序树,算法如下。
代码
KeyType predt=-32767; //predt为全局变量,保存当前节点中序前驱的值,初值为
-∞
int judgeBST(BSTNode *bt)
{int b1, b2;
if (bt==NULL) //空树是一棵二叉排序树
return 1;
else
{b1=judgeBST (bt->lchild); //判断左子树
if(b1==0ll predt>=bt->key)
return 0;
predt=bt->key; //保存当前节点的关键字
b2=judgeBST (bt->rchild); //判断右子树
return b2;
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图