1、二叉排序树和平衡二叉树的判别二叉排序树和平衡二叉树的判别 1 引言引言 数据结构是软件工程的一门核心专业基础课程， 在我们专业的课程体系中起 着承上启下的作用， 学好数据结构对于提高理论认知水平和实践能力有着极为重 要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界 中的问题，应该能从中抽象出一个适当的数据模型，该数学模型在计算机内部用 相应的数据结构来表示，然后设计一个解此数学模型的算法，在进行编程调试， 最后获得问题的解答。 本次课程设计的题目是对二叉排序树和平衡二叉树的扩展延伸应用。 首先我 们得建立一个二叉树，二叉树有顺序存储结构和链式存储结构两种存储结构，此 次我
2、选用的是二叉链表的存储结构。对于判断平衡二叉树，需要求出其每个叶子 结点所在的层数，这里我采用的边遍历边求的方式，遍历采用的是先序遍历。二 叉树的建立以及二叉排序树和平衡二叉树的判别中都用到了递归思想。 2 2 需求分析需求分析 2.12.1在日常生活中，人们几乎每天都要进行“查找”工作。所谓“查找”即为 在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素 （或记录） ，即关键字。 2.22.2本程序意为对一个已经建立的动态查找表二叉树判断其是否是二 叉排序树和平衡二叉树。 3 3 数数据结构设计据结构设计 3.13.1抽象数据类型二叉树的定义如下： ADT BinaryT
3、ree 3.1.13.1.1数据对象 D：D 是具有相同特性的数据元素的集合。 3.1.23.1.2数据关系 R: 若 D=NULL，则 R=NULL，称 BinaryTree 为空的二叉树； 若 D!=NULL,则 R=H，H 是如下的二元关系: 3.1.2.13.1.2.1 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； 3.1.2.23.1.2.2 若 D-root!=NULL,则存在 D-root=Dl,Dr,且 Dl 与 Dr 相交为空； 3.1.2.33.1.2.3 若 Dl！=NULL，则 Dl 中存在唯一的元素 xl,属于 H，且存在 Dl 上的关系
4、Hl 属于 H；若 Dr！=NULL，则 Dr 中存在唯一的元素 xr, 属于 H，且存在 Dr 上的关系 Hr 属于 H；H=,Hl,Hr； 3.1.2.43.1.2.4（Dl,Hl)是一棵符合本定义的二叉树，称为根的左子树， （Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。 3.23.2基本操作 P： InitBiTree( 操作结果：构造空二叉树 T。 CreateBiTree( /数据结构 typedef struct Bitree int w; struct Bitree *lchild; struct Bitree *rchild; Bitree; /定义符号常量 cons
5、t Max=100; /定义全局变量 Bitree * root;/根结点 int i;/计数 /自定义函数原型说明 void creat(Bitree *p);/创建二叉树 void Create（）; void judgeBST(Bitree * root);/判断二叉排序树 void judge1(); void judgeAVL(Bitree * root,int count,int mark);/判断平衡/二叉树 void judge2(int mark); 4 4 算法设计算法设计 4.14.1 算法内容算法内容 / Note:Your choice is C+ IDE #incl
6、ude using namespace std; typedef struct Bitree int w; struct Bitree *lchild; struct Bitree *rchild; Bitree; const Max=100; Bitree *root; int i;/计数 /创建二叉树 void creat(Bitree *p) /按照树的先序遍历顺序输入数据，并且当结点的左右孩子不存在时输入0 if(p!=0) /左孩子 p-lchild=new Bitree; coutlchild-w; if(p-lchild-w!=0)creat(p-lchild); else Bitree *q=p-lchild;p-lchild=0;delete q; /右孩子 p-rchild=new Bitree; coutrchild-w; if(p-rchild-w!=0)creat(p-rchild); else Bitree *q=p-rchild;p-rch
