数据结构实验十：树和二叉树的应用试验.docVIP

一，实验题目 实验十：树及二叉树的应用试验 试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表存储，且树中结点的关键字均不相同。 二，问题分析 本程序要求判别一个以二叉链表存储且树中结点的关键字均不相同的给定的二叉树是否为二叉排序树，完成这些操作需要解决的关键问题是：以二叉链表的存储形式输入一个二叉树。用一个函数实现判断是否为二叉排序树的功能。 数据的输入形式和输入值的范围：输入的二叉树元素为字符型，注意不能输入空格键和回车键，会出现错误，因为它们也是一个字符。 结果的输出形式：输出的是中序遍历后的二叉树元素。 测试数据：（1）输入的队列元素为：6 4 8 9 @ @ 2 # （2）输入的队列元素为：5 4 7 1 @ 6 9 # 三，概要设计 （1）为了实现上述程序的功能，需要： creatree() A，建立一颗二叉树 main（） B，中序遍历输出该二叉树 inorder（） C，判断该二叉树是否为二叉排序树 （2）本程序包含4个函数： panduan（） a，主函数main（） b，建立二叉树函数creatree() c，中序遍历输出二叉树函数inorder（） d，判断二叉树是否为二叉排序树函数：panduan（） 各函数间关系如右图所示： 四，详细设计 （1）结点类型定义： typedef struct node{ char data; struct node *lchild,*rchild; }Bitree; Bitree *Q[maxsize]; （2）建立二叉树函数伪代码： Bitree *creatree(){ char ch; int front,rear; Bitree *T,*S; T=NULL; front=1;rear=0; scanf(%c,ch); while(ch!=#){ S=NULL; if(ch!=@){ S=(Bitree *)malloc(sizeof(Bitree));S-data=ch;S-lchild=S-rchild=NULL;} rear++;Q[rear]=S; if(rear==1) T=S; else{ if(S!=NULLQ[front]!=NULL) if(rear%2==0) Q[front]-lchild=S; else Q[front]-rchild=S; if(rear%2==1) front++;} scanf(%c,ch);}return T;} （3）中序遍历输出二叉树函数伪代码： void inorder(Bitree *T){ if(T){ inorder(T-lchild); printf(%c,T-data); inorder(T-rchild);}} （4）判断二叉树是否为二叉排序树函数伪代码： int panduan(Bitree *p) { int x=0; if(p){if(p-lchildp-datap-lchild-data) x=1; if(p-rchildp-datap-rchild-data) x=1; x=x||panduan(p-lchild); x=x||panduan(p-rchild); } return x; } 五，源代码 #include stdio.h #include malloc.h #define maxsize 100 #define NULL 0 typedef struct node{ //定义二叉树的结构类型 char data; struct node *lchild,*rchild; }Bitree; Bitree *Q[maxsize]; //定义一个指向二叉树的队列Q指针 Bitree *creatree(){ //建立二叉树函数 char ch; int front,rear; //front和rear指向当前与其孩子结点建立链接的父节点和当前输入的结点 Bitree *T,*S; //定义两个Bitree型指针T，S T=NULL; //置空二叉树 front=1;rear=0; //置空队列 printf(请输入二叉树元素，输入#号键结束:); scanf(%c,ch); while(ch!=#){ //当输入的不是结束字符时 S=NULL;