⼆叉排序树的判定算法//函数功能：⼆叉排序树的判定算法
/*
算法思想：根据⼆叉树的特点“其中序遍历序列为有序序列”，对⼆叉树进⾏中序遍历，
同时检查当前结点与其中前驱关键字值的⼤⼩。
*/
//中序遍历过程中判定给定的⼆叉树是否为⼆叉排序树，⼊是返会true，否则返回false
//pre指向中序前驱结点，初值为NULL
1 typedef struct treeNode
完全二叉树算法
2 {
3int data; //⼆叉排序树的元素类型为int
4struct treeNode *l,*r;
5 }treeNode,*BiTree;
6
7/*
8中序遍历⼆叉树，root为根节点，pre初始值为null。
9
10*/
11
12bool Is_BS_Tree(BiTree root,BiTree pre)
13 {
14if（!root）
15    {//空⼆叉树也是⼆叉排序树，所以返回true。
16return true;
17      }
18if（Is_BS_Tree(root->l,pre)）
19    {//若左⼦树是⼆叉排序树。
20//是否为⼆叉排序树取决于前驱值和根节点值的⼤⼩。
21if((pre==null)||(pre->data<root->data))
22            {
23                pre=root;
24//再次判断右⼦树是否为⼆叉排序树。
25return Is_BS_Tree(root->l,pre);
26            }
27      }
28//以上情况出现异常，则返回false。
29return false;
30 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。