《判断是否是二叉排序树》由会员分享，可在线阅读，更多相关《判断是否是二叉排序树（2页珍藏版）》请在金锄头文库上搜索。
1、源代码#include#include #define max 10 typedef struct nodeint data;node *lchild,*rchild;Bitree;Bitree *Bmax; int temp=0;int Btreemax;Bitree *Creatree()/建立二叉树Bitree *T,*S;int ch;int front,rear,sign; sign=0;front=0; rear=-1; T=NULL;printf(“建立二叉树(1 表示虚结点,0 表示输入完毕):n“);scanf(“%d“,&ch); while(ch!=0)if(ch!=1)
2、/输入结点不是虚结点S=(Bitree*)malloc(sizeof(Bitree);S-data=ch;S-lchild=S-rchild=NULL; rear+;Brear=S; if(rear=front)T=S;sign+;elseif(sign%2=1)/查找父结点Bfront-lchild=S; if(sign%2=0)Bfront-rchild=S; front+;sign+;else/输入结点为虚结点if(sign%2=0)front+; sign+;scanf(“%d“,&ch);return T;void Inorder(Bitree *T)/中序遍历二叉树，并将每个结点数
3、据存入数组中if(T!=NULL)Inorder(T-lchild); printf(“%dt“,T-data); Btreetemp=T-data; temp+;Inorder(T-rchild);int Judgesort_bitree(int Btree)/推断是否是二叉树int i,sign=1; for(i=0;iBtreei+1) sign=0;break;return sign;void Judgeout(int a)/推断输出if(a=1)printf(“ 给定二叉树是二叉排序树!n“);if(a=0)printf(“给定二叉树不是二叉排序树!n“);void main()Bi
4、tree *T; T=Creatree();printf(“中序遍历:n“);Inorder(T);printf(“n“);Judgeout(Judgesort_bitree(Btree);题目：试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表存储，且树中结点的关键字均不一样。问题分析：本程序要求实现判定一棵二叉树是否为二叉排序树。为实现上述功能，需要解决的关键问题是：建立一棵二叉树及判定二叉树过程。概要设计：建立一个以二叉链表方式存储的二叉树，输入结点信息时依据完全二叉树的结点挨次输入。由于一棵二叉排序树中序遍历后的序列是递增有序的，因此可利用中序遍历一棵二叉树后的序列是否递
5、增有序来推断是否为二叉排序树。具体设计：建立二叉树时，依据完全二叉树的结点挨次输入，表示虚结点，#表示输入完毕。 假设不是虚结点时，那么建立一个新结点，并且将其作为左孩子或右孩子结点连接到它的父结点上第一个结点无父结点；假设是虚结点，那么将空结点NULL作为左孩子或右孩子结点连接到它的父节点上。判定二叉树时，中序遍历整棵二叉树，访问根结点时将根结点信息存入一个数组中，以 用来比较中序遍历后序列是否为空。比较数组元素时，从下标为 0 的数组元素开头比较，先将下标为i=0 的ai与下标为 1 的 ai+1比较，假设aiai+1，那么完毕比较，即该二叉树不是二叉排序树，否那么连续比较，直至比较完整个数组元素。调试分析及小结：
