数据结构课程设计---二叉排序树和平衡二叉树的判别

1、二叉排序树和平衡二叉树的判别1引言数据结构是软件工程的一门核心专业基础课程，在我们专业的课程体系中 起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极 为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现 实世界中的问题，应该能从屮抽彖出一个适当的数据模型，该数学模型在计算 机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，在进行 编程调试，最后获得问题的解答。木次课程设计的题目是对二叉排序树和平衡二叉树的扩展延伸应用。首先 我们得建立一个二叉树，二叉树有顺序存储结构和链式存储结构两种存储结构, 此次我选用的是二叉链表的存储结构。对于判断平衡二叉树

2、，需要求出其每个 叶子结点所在的层数，这里我采用的边遍历边求的方式，遍历采用的是先序遍 历。二叉树的建立以及二叉排序树和平衡二叉树的判别中都用到了递归思想。2需求分析21在日常生活中，人们几乎每天都要进行“查找”工作。所谓“查找”即为 在一个含有众多的数据元素（或记录）的查找表中找岀某个“特定的”数据元 素（或记录），即关键字。2. 2木程序意为对一个己经建立的动态查找表一一二叉树一一判断其是否是二 叉排序树和平衡二叉树。3数据结构设计3. 1抽象数据类型二叉树的定义如下：adt binar ytree 3. 1. 1数据对象d： d是具有和同特性的数据元素的集合。3. 1.2数据关系r:若

3、d=nu ll,则 r=null ,称 binarytr ee 为空的二叉树；若d!二null,则r二h, h是如下的二元关系:3. 1.2.1在d中存在唯一的称为根的数据元素ro ot,它在关系h下无前驱；3. 1.2.2 若 d-root !=null,则存在 d-root = d 1, dr,且 d1 与dr 相交为空;3. 1 . 2. 3若di! =n ull,则di中存在oot, xl>屈于h ,且存在di上的关系hl 属于h；若dr! =null,则dr中存在唯一的元素xr,于h,且存在dr上的关系 hr 属于 h； h 二,hl, hr；3. 1.2.4 (di, hl)

4、是一棵符合本定义的二叉树，称为根的左子树，(dr, hr)是一棵符合本定义的二叉树，称为根的右子树。3. 2基本操作p：initbi操作结果：构造空二叉树t。crcatebi finition)；初始条件:defin ition给出二叉树t的定义。操作结果：按definitio n构造二叉树t。 a dt tree/包含头文件#inclu m>using na mespace st d;数据结构typedef struct bitreeint w;struct bitree*lchild;struct bi tree *rchild; bitree;定义符号常量cons t max=10

5、0;定义全局变量bi tree * roo t;根结点int i;计数自定义函数原型说明vo id creat(b itree *p);创建二叉树voi d create ();voidjudgebst(bitree* root);/判断二叉排序树v oid judge 1 ();void ju dgeavl(bit ree * root ,int count ,int mark);/判断平衡二叉树void j udge2(int mark);4算法设计4.1算法内容/ note: your choiceis c+ ide #include iostream> using namespa

6、ce std;typedef s true tb itreeint w;structbitree*lchild;structbitree*rchild; bitree;const max=100;bitreeroot;inti;/计数创建二叉树voidcreat(bitree*p)按照树的先序遍历顺序输入数据，并且当结点的左右孩子不存在时输入0if(p!二 0)左孩子p->lchild=newbitree;cout"请输入结点数据：cin»p->lchild->w;if(p->lchild-> w! =o)creat(p->lchild)

7、;else bitree * q=p->lchild;p->lchild=o;deleteq;右孩子p>rchild=new bitree;cout«n请输入结点数据：”；cin»p->rchild->w;if(p->rchild->w !=o)creat(p->rchild);else bitree*q=p->rchild;p->rchild=o;delete q;voidcreate()root=newbitree;按照树的先序遍历顺序输入数据，并且当结点的左右孩子不存在时输入0 cout”请输入结点数据:”；

8、 cin»root->w;if(root->w !=0)creat(root);else bitree*p=root;root=0;delete p;j下面两个函数为判断二叉树是否为二叉排序树voidj udgeb st (b itree*root)bitree*l,*r;if(root!=0)if(i=0) l=root->lchild;if(l !=null&&root->w<l->w) i+；return; judgebst(l);if(i=o)r=root->rchild;if(r!=null&&roo

9、t->w>r->w) i+;return; judgebst(r);voidjudge 1()if(i=0)cout«h 是二叉排序树 vendl; elsecout«h 不是二叉排序树!"«endl;下面两个函数判断二叉树是否为平衡二叉树voidjudgeavl(bitree:root,intcount,intmark)if(root=0)marki+=count;elsecount+;judgeavl(root->lchild,count,mark);judgeavl(root->rchild,count,mark);)

10、void judge2(int mark)int mark2=0;for(intj=0;j<i;j+)if(markj-marko<-l |markj-mark0>l)mark2=l; if(mark2=0)cout«h 是平衡二叉树! “;else cout”不是平衡二叉树!”;主函数void main()create();/创建二叉树判断二叉树是否为二叉排序树i二0;/标志judgebst(root);judgel();判断二叉树是否为平衡二叉树intcount=0,markmax;i=0;/计数judgeavl(root,count,mark); judge2

11、(mark);4. 2调试分析整个程序分为三大块：建立二叉树、判断是否为二叉排序树、判断是否为平衡 二叉树。4. 2. 1建立吋开始没有考虑二叉树为空的情况，并且没有注意不用的空间应释 放。经调整，已解决。4. 2.2判断二义树是否为二叉排序树时，开始没注意到当结点为空时，是不能 进行权值的大小比较的。并口标志i一旦不为0即可不再进行比较了。4. 2. 3二叉树是否为平衡二叉树时，应注意到只要m arkj-mar ko<-l和ma rkj-mark 01满足其一就可，所以应用或运算符。4. 2.4调试中数据的输入应充分考虑各种情况：二叉树为空；二叉树非空时， 既是二叉排序树又是平衡二叉树

12、、是二叉排序树不是平衡二叉树、是平衡二叉 树不是二叉排序树、既不是二叉排序树也不是平衡二叉树。这样就可以充分检 验程序的正确性。4. 3调试结果根据二叉树的先序遍历顺序输入结点，若结点不存在，输入结点数据o （或左右 孩子不存在时，孩子结点数据输入0）4. 3. 1请输入结点数据:0是二叉排序树！是平衡二叉树！4. 3. 2请输入结点数据:4请输入结点数据：3请输入结点数据：2请输入结点数据：0请输入结点数据：0请输入结点数据：0请输入结点数据：1请输入结点数据：0请输入结点数据：0不是二叉排序树！是平衡二叉树！4. 3.3请输入结点数据：5 请输入结点数据：3请输入结点数据：2请输入结点数据

13、：0请输入结点数据：0请输入结点数据：0请输入结点数据：0是二叉排序树！不是平衡二叉树！4. 3. 4请输入结点数据：4请输入结点数据：5请输入结点数据：2请输入结点数据：0请输入结点数据：0请输入结点数据：0请输入结点数据：0不是二叉排序树！不是平衡二叉树！4. 3.5请输入结点数据：5请输入结点数据：4请输入结点数据：2请输入结点数据：0请输入结点数据：0请输入结点数据：0请输入结点数据：7请输入结点数据：6请输入结点数据：0请输入结点数据：0请输入结点数据：8请输入结点数据：0请输入结点数据：0是二叉排序树！是平衡二叉树！5有关技术的讨论本程序要解决的问题是建立一个二叉树，判断此二叉树是

14、否为二叉排序树，判 断此二叉树是否为平衡二叉树。其中每个算法的设计都需要用到递归思想。下 面讨论一下这些算法思想：5. 1建立二叉树吋，是按照先序遍历的思想递归建立的。递归的思想是：先建 立根结点，然后建立左孩子，最后建立右孩子。当某个结点为空时，输入其权 值为oo5.2判断二叉排序树时，先让根结点和左孩子结点比较，然后以左孩子结点为 根结点，重复上述过程。接着让根结点和右孩子结点比较，过程同上。比较过 程中一旦根结点小于其左孩子（或大于其右孩子），即让标致i变为1结束程序。 标致i二二1时，二叉树不是二叉排序树；i二二0时，是二叉排序树。5. 3判断平衡二叉树时，是按照边先序遍历边求深度的方

15、法，具体思想见上述 算法。6设计体会通过这几天的课程设计，我对计算机的应用、对数据结构的应用、对 cc+语言的应用有了更深的了解和认识。在理论结合实践时，我深深地感受到 了所学知识的不扎实和不足。我深刻的体会到了原来实践是检验所学知识检验 理论的最好方法；并且理论知识和实际应用也有很大的差距，我们只有多动 手、多动脑，理论联系实际，才能更加扎实牢固地掌握所学知识。同时，通过 课程设计我也了解到原来我们所学的知识和实际的联系是那么的紧密，原来我 们所学的知识在实际生活屮的用处可以这样大。这几天的算法设计和上机实验，使我的代码编写能力，思维能力都有了很 大的提高。在代码的编写和调试过程中，我学会了

16、如何最快的找出错误，如何 思维更加严密，更加完全的写一个算法。同时，我也体会到了，当发现错误时, 要不急不躁，认真分析程序，当自己实在是找不出来时，也要学会寻求帮助， 并且在他人思路的引导下，找自己的错误，认真反省和思考，争取以后不再犯 此类错误，学会他人分析查找程序中错误的方法。在实际的上机操作过程中，不仅是让我了解数据结构的理论知识，更重要 的是培养解决实际问题的能力，同时我也体会到了编程的乐趣，当我终于把问 题解决看到程序成功运行吋那份喜悦和骄傲是无以言表的。通过这次课程设计 我们的分析设计能力和编程能力有了很大提高，为后续课程的学习及实践打好 了坚实的基础。结束语数据结构是一门理论性强、思维抽象、难度较犬的课程，使我们基础课和 专业课z间的桥梁。通过本门课程的学习，我们能够理解各种数据对象的特点, 学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实 际问题的能力，而且这门课程的研究方法对我们在校和离校后的学习和工作也 有着重要的意义。对于这次短短的课程实践，我还要谢谢我的指导老师胡燕老师，实践中我得到 了胡燕老师的很多关心和帮助。她传授给我们的信息在课程设计屮的作用很大