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

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

admin2017-01-04  1
问题 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用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
解析
转载请注明原文地址:https://kaotiyun.com/show/4QRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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