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

《数据结构课程设计---二叉排序树和平衡二叉树的判别》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、用的是二叉链表的存储结构。对于判断平衡二叉树，需要求出其每个叶子结点所在的层数，这里我采用的边遍历边求的方式，遍历采用的是先序遍历。二叉树的建立以及二叉排序树和平衡二叉树的判别中都用到了递归思想。2需求分析2.1在日常生活中，人们几乎每天都要进行“查找”工作。所谓“查找”即为在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），即关键字。2.2本程序意为对一个已经建立的动态查找表——二叉树——判断其是否是二叉排序树和平衡二叉树。3数据结构设计3.1抽象数据类型二叉树的定义如下：ADTBinaryTree{3.1.1数据对象D：D是具有相同特性的数

3、据元素的集合。3.1.2数据关系R:若D=NULL，则R=NULL，称BinaryTree为空的二叉树；若D!=NULL,则R={H}，H是如下的二元关系:3.1.2.1在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；3.1.2.2若D-{root}!=NULL,则存在D-{root}={Dl,Dr},且Dl与Dr相交为空；3.1.2.3武汉理工大学《数据结构》课程设计说明书若Dl！=NULL，则Dl中存在唯一的元素xl,属于H，且存在Dl上的关系Hl属于H；若Dr！=NULL，则Dr中存在唯一的元素xr,属于H，且存在Dr

4、上的关系Hr属于H；H={,,Hl,Hr}；3.1.2.4（Dl,{Hl})是一棵符合本定义的二叉树，称为根的左子树，（Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。3.2基本操作P：InitBiTree(&T);操作结果：构造空二叉树T。CreateBiTree(&T,definition)；初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。}ADTTree//包含头文件#includeusingnamespacestd;//数据结构typedefstruct

5、Bitree{intw;structBitree*lchild;structBitree*rchild;}Bitree;//定义符号常量constMax=100;//定义全局变量Bitree*root;//根结点inti;//计数//自定义函数原型说明voidcreat(Bitree*p);//创建二叉树voidCreate（）;voidjudgeBST(Bitree*root);//判断二叉排序树voidjudge1();voidjudgeAVL(Bitree*root,intcount,intmark[]);//判断平衡//二叉树voidjudge2(intmark[]

6、);4算法设计4.1算法内容//Note:YourchoiceisC++IDE#includeusingnamespacestd;typedefstructBitree{intw;structBitree*lchild;武汉理工大学《数据结构》课程设计说明书structBitree*rchild;}Bitree;constMax=100;Bitree*root;inti;//计数//创建二叉树voidcreat(Bitree*p)//按照树的先序遍历顺序输入数据，并且当结点的左右孩子不存在时输入0{if(p!=0){//左孩子p->lchild=newB

7、itree;cout<<"请输入结点数据：";cin>>p->lchild->w;if(p->lchild->w!=0)creat(p->lchild);else{Bitree*q=p->lchild;p->lchild=0;deleteq;}//右孩子p->rchild=newBitree;cout<<"请输入结点数据：";cin>>p->rchild->w;if(p->rchild->w!=0)creat(p->rchild);else{Bitree*q=p->rchild;p->rchild=0;delete