2. 考研
  3. 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink—rlink法存储。

请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink—rlink法存储。

admin2019-08-15  15
问题 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink—rlink法存储。
选项
答案 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre(初值为null)和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0 typedef struct node{ datatype data； struct node*llink，*rlink： }*BTree； void JudgeBST(BTree t，int flag){ ／／判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论 if(t!=null&&flag){ JudgeBST(t一＞llink，flag)； ／／中序遍历左子树 if(pre==null)pre=t； ／／中序遍历的第一个结点不必判断 else if(pre一＞data＜t一＞>data)pre=t； ／／前驱指针指向当前结点 else flag=false； ／／不是二叉排序树 JudgeBST(t一＞rlink，flag)； ／／中序遍历右子树 } } 本题的另一算法是依照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下： int JudgeBST(BTree t){ ／／判断二叉树t是否是二叉排序树，若是，返回true，否则，返回false if(t==null)return true： if(JudgeBST(t一＞llink)&&JudgeBST(t一＞rlink)){ ／／若左右子树均为二叉排序树 m=max(t一＞llink)；n=min(t一＞rlink)； ／／左子树中最大值和右子树中最小值 return(t一＞data＞m&&t一＞data＜n)； } else return false； ／／不是二叉排序树 } int max(BTree p){ ／／求二叉树左子树的最大值 if(p==null)return—maxint； ／／返回机器最小整数 else{ while(p一＞rlink!=null)P=p一＞rlink； return p一＞data； } } int min(BTree p){ ／／求二叉树右子树的最小值 if(P==null)return maxint； ／／返回机器最大整数 else{ while(p一＞llink !=null)p=p一＞rlink； return p一＞data； } }
解析
转载请注明原文地址:https://jikaoti.com/ti/6oGjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)