22判别给定的二叉树是否为二叉排序树.docVIP

22判别给定的二叉树是否为二叉排序树 #includestdio.h #includestdlib.h #define max 10 typedef struct node{ int data; //数据域 node *lchild,*rchild; //左孩子指针，右孩子指针 }Bitree; //结点的结构体定义 Bitree *B[max]; int temp=0; int Btree[max]; Bitree *Creatree(){ //建立二叉树 Bitree *T,*S; int ch; int front,rear,sign; sign=0; //结点的序号从0开始编号（按照完全二叉树的顺序标记） front=0; //双亲结点下标初值 rear=-1; //自身结点下标初值 T=NULL; //初始化树T printf(建立二叉树(1表示虚结点,0表示输入结束):\n); scanf(%d,ch); //按完全二叉树的顺序输入结点 while(ch!=0) { if(ch!=1) //输入结点不是虚结点 { S=(Bitree *)malloc(sizeof(Bitree)); //创建新结点S S-data=ch; //将输入的数据保存到S中 S-lchild=S-rchild=NULL; //将S的左右子树为空 rear++; //结点下标加1 B[rear]=S; //将S保存到数组B中，即从下标为0开始存储 if(rear==front) //双亲结点下标与本身下标相同时，即无双亲结点（只有第一个结点会产生这种情况） { T=S; sign++; //结点的序号加1 } else //寻找双亲结点 { if(sign%2==1) B[front]-lchild=S; //S作为左孩子 if(sign%2==0) { B[front]-rchild=S;//S作为右孩子 front++; //下标加1，即寻找下一个双亲结点 } sign++;//结点序号加1 } } else{ //输入结点为虚结点 if(sign%2==0) //为右子树时 {front++;} //双亲结点加1 即下一个双亲结点 sign++; //结点序号加1 } scanf(%d,ch); } return T; } void Inorder(Bitree *T) //中序遍历二叉树T，并将每个结点数据存入数组中 { if(T!=NULL) //如果树不为空 { Inorder(T-lchild); printf(%d\t,T-data); Btree[temp]=T-data; temp++; Inorder(T-rchild); } } int Judgesort_bitree(int Btree[]) //判断中序遍历后的二叉树是否是二叉排序树 { int i,sign=1; for(i=0;itemp-1;i++) //用for循环语句 看二叉树是否有序递增 { if(Btree[i]Btree[i+1]) //不是有序递增的 { sign=0; break; } } return sign; } void Judgeout(int a)//判断输出 将sign赋给a { if(a==1) printf(给定二叉树是二叉排序树!\n); if(a==0) printf(给定二叉树不是二叉排序树!\n); } int main() { Bitree *T; T=Creatree(); //建立二叉树 printf(中序遍历:\n); Inorder(T); //中序遍历二叉树 printf(\n); Judgeout(Judgesort_bitree(Btree)); //判断是否为排序二叉树 return 0; }