《数据结构课程设计》

1、个人资料整理，仅供个人学习使用数据结构课程设计报告专业： 计算机科学与技术班级： 081 计算机学号： 08136101姓名：学期： 20XX-20XX 学年第 2 学期设计题目： _判别否为二叉排序树 设计地点： _西区理工楼 303指导教师： _唐开山 完成日期： _20XX-6-6_ 成绩： 一、需求分析及规格说明 要求：建立一棵二叉树，然后判别该二叉树是否为二叉排序树。规格说明： 空树默认为二叉排序树，没有作为输入考虑对象。二、概要设计 程序设计比较简单，定义树的结构，创建树CreateBitTree() ， InitTree()为空树 ,用递归方法先序遍历二叉树DLR() 来帮助显示

2、输入的树 .根据二叉排序树的定义 :矚慫润厲钐瘗睞枥庑赖賃軔朧。二叉排序树( Binary Sort Tree )又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树：(1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2) 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3) 左、右子树也分别为二叉排序树；使用了辅助函数 SortTree() 在 main 函数中调用帮助判断所建二叉树是否为二叉排序树三、详细设计#include #include #include typedef char Elemtype;typedef struct BitNodeE

3、lemtype data;BitNode *Lchild,*Rchild;/ 左，右孩子指针BitNode, *BitTree;void InitTree(BitTree *BT) / 构造一个空二叉树BT=NULL;int CreateBitTree(BitTree &BT)/ 构造一个二叉树Elemtype ch;cinch;if(ch=#) BT=NULL;/ 建空树elseif(!(BT=(BitNode*)malloc(sizeof(BitNode)exit(1); BT-data=ch;个人资料整理，仅供个人学习使用CreateBitTree(BT-Lchild);CreateBi

4、tTree(BT-Rchild);return 1;void DLR(BitTree root)/ 递归方法先序遍历二叉树if(root!=NULL)printf(%c ,root-data);DLR(root-Lchild);DLR(root-Rchild);void SortTree(BitTree &T)/ 判断是否是二叉排序树BitTree s100;BitTree t100;int top=0;int k=0;while(T!=NULL|top!=0)while(T)s+top=T;T=T-Lchild;if(top!=0)tk+=stop;T=stop-Rchild;for(int

5、 i=0;idata=ti+1-data)printf( 不是二叉排序树 n);return; 聞創沟燴鐺險爱氇谴净祸測樅。 printf( 是二叉排序树 n);void main()int flag=0;int t ;BitTree T;while(1)printf(*二叉排序树 *n);残骛楼諍锩瀨濟溆塹籟婭骒東。printf(1、建立二叉链表 n);printf(2、遍历二叉树输出 n);printf(3、判断二叉树是否是二叉排序树 n);printf(0、退出操作 n );printf(*n);酽锕极額閉镇桧猪訣锥顧荭钯。scanf(%d,&t);switch(t)个人资料整理，仅供个

6、人学习使用case 1:printf( 请输入字符串构造二叉树 (#代表空树 ):n); flag=CreateBitTree(T);getchar();break;case 2:if(flag=1) if(T!=NULL)printf( 用递归算法先序遍历二叉树 :n);DLR(T);printf(n);elseprintf( 二叉树为空 !n);elseprintf( 请先建立二叉树 !n); break;case 3:if(flag=1) if(T!=NULL)SortTree(T);printf(n);elseprintf( 二叉树为空 !n);elseprintf( 请先建立二叉树 !n); break;case 0:exit(0);break;default:printf( 输入错误 !n);四、调试分析调试通过，输入时要注意，输入的方式不同可能得到的结果不一样，虽然遍历输出的结果看来一样，但判 断是否为二叉排序树时就不相同了。由于构造时，输入方式不同，导致构造的树结构不一样，虽然数据一 样，但树的结构