二叉排序树及平衡二叉排序树基本操作实现.docx

《二叉排序树及平衡二叉排序树基本操作实现.docx》由会员分享，可在线阅读，更多相关《二叉排序树及平衡二叉排序树基本操作实现.docx（15页珍藏版）》请在优知文库上搜索。

1、B04900083湖或笈，挈花HUBEIPO1.YTECHNICUNIVERSITY课程设计教学院计算机学院课程名称数据结构及飘法廊曰二叉排序树及平衡二叉持芹树域本操作曰的实现专业计算机科学及技术班级二班姓名同组人员指导老师成俊2015年12月27日课程设计任务书20152016学年第1学期学生姓名:一,专业班级：计科二指导老师：成俊工作部门：计算机学院一、课程设计题目：二又排序树及平衡二又排序树基本操作二、课程设计内容用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作:以回车Cn,为输入结束标记,输入数列1.,生成二叉排序树T：对二叉排序树T作中序遍历：计算二叉择序树T的平均,输出结果

2、：输入元素X,查找二叉排序树T.若存在含X的结点，则删除该结点，并作中序遍历：否则输出信息“无结点x”：推断二叉排序树T是否为平衡二叉树：再用数列1.,牛成平衡二叉排序树BT:当插入新元素之后，发觉当前的二叉排序树BT不是平衡二叉排序树，则马上将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均杳找长度,输出结果.三、进度支配1 .分析问题，给出数学模型,选择数据结构。2 .设计算法，给出算法描述3 .给出海程序清单4 .编辑、编译、调试源程序5 .撰写课程设计报告四、基本要求编写AV1.树判别程序，并判别一个二叉排序树是否为AV1.树。二叉排序树用其先序遍历结果表示，如：5,2,

3、1,3,7,8,实现AV1.树的ADT,包括其上的基本操作：结点的加入和删除；另外包括将一殷二叉排序树转变为AV1.树的操作。实现提示主要考虑树的旋转操作.一、课程设计题目：二叉排序树及平衡二叉排序树基本操作1二、课程设计内容1三、进度支配1四、基本要求1一、概述3Io课程设计的目的32。课程设计的要求3二、总体方案设计4三、具体设计6U课程设计总体思想62.模块划分73o流程图8四、程序的调试及运行结果说明9五、课程设计总结14参考文献14一、概述1.课程设计的目的1 .充分理解和驾驭二叉树、平衡二叉树的相关概念和学问.2 .驾驭排序二叉树的生成、结点删除、插入等操作过程。3 .并实现从键盘

4、上输入一系列数据（整型），建立棵平衡二叉树。4 .随意插入或删除一个结点后推断是否为平衡二叉树。5 .将非平衡二叉树转换成平衡二叉树。6 .按中序遍历输出这棵平衡二叉树.7 .课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车（n）为输入结束标记,输入数列1.,生成二叉排序树T：对二叉排序树T作中序遍历;计算二叉排序树T的平均查找长度,输出结果：输入元素X,查找二叉排序树T.若存在含X的结点，则删除该结点，并作中序遍历：否则输出信息“无结点X；推断二叉排序树T是否为平衡二叉树:再用数列1.生成平衡二叉排序树BT:当插入新元素之后，发觉当前的二叉排序树BT不是平衡二叉

5、排序树,则马上招它转换成新的平衡二叉排序树BT：计算平衡的二叉排序树BT的平均查找长度，输出结果.编写AV1.树判别程序，并判别一个二叉排序树是否为AV1.树。二叉排序树用其先序遍历结果表示,如：5,2,1,3,7,8。实现AV1.树的ADT.包括其上的基本操作：结点的加入和删除：另外包括将一般二叉排序树转变为AV1.树的操作.实现提示主要考虑树的旋转操作。二、总体方案设计1）建立二叉排序树,编写二叉排序树T作中序遍历.2）查找删除二叉排序树函数.3）编写推断二叉排序树T是否为平衡二叉树函数，把非平衡二叉排序树转换成平衡二叉排序树。4）编写计算二叉树叮的平均查找长度函数。我负责的是第一部分，二

6、叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1 .若它的左子树不空，则左子树上全部结点的值均小丁它的根结点的值：2 .若它的右子树不空，则右子树上全部结点的值均大于它的根结点的值：3。它的左、右子树也分别为二叉排序树。以链表存储结构创建二叉排序树，以回车（n）为输入结束标记,输入数列1.,生成二叉排序树T；对二叉排序树T作中序遍历。中序遍历二叉树算法的框架是：若二叉树为空，则空操作：否则（1）中序遍历左子树（1.）：（2）访问根结点（V）;（3）中序遍历右子树（R）。函数1:中序遍历二叉树中序遍历二叉树也采纳递归函数的方式，先访问左子树2i,然后访问根结点i.最终访问右子树2i+1.先

7、向左走究竟再值层返回，直至全部的结点都被访问完毕。（谢石林）函数2:平均查找长度计.算二叉排序树的平均查询长度时，可采纳类似中序遍历的递归方式，用Sid录总查询长度，j记录每个结点的查询长度，S值初值为0,采纳累加的方式最总得到总查询长度s,平均查询长度等于s/iG为树中结点个数）。（吴进）函数3：查找删除二叉排序树函数输入元素X,查找二叉排序树T,若存在含X的结点，则JH该结点,并作中序遍历（执行函数1）；否则输出信息“无x”。（张常勋）函数4：推断二叉排序树T是否为平衡二叉树，若不是则用数列1.,生成平衡排序二叉树BT：最终调用函数6,接着调用函数5.推断二叉排序树是否为平衡二叉树的函数也

8、是采纳递归函数的方式，分别判定以树中每个节点为根节点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二义树.函数5：在平衡二叉树BT上插入新元素，若发觉当前的二叉排序树BT不是平衡二叉排序树，则马上将它转换成新的平衡二叉排序树BT。三、具体设计1.课程设计总体思想1。生成二叉排序树：建立二叉排序树采纳的是边杳找边插入的方式。查找函数采纳递归的方式进行查找。查找是根据二叉排序树的性质进行的，通过比较要插入元素的关键字及当前结点关键字的大小来确定我们是遍历当前结点的哪个子树.假如小于当前结点关键字，则遍历它的左子树：大于当前结点关键字,则遍历它的右子树：等丁当前关键字，则此元

9、素不插入原树.我们根据这样的规律，始终向下遍历，知道它的r树为空,则返回当前结点的上个结点。然后利用插入函数将该元素插入原树。2。中序遍历:对二叉排序树进行中序遍历采纳递归函数的方式。在根节点不为空的状况下,先访问左子树,在访问根结点，最终访问右子树。3 .平均查找长度：计算二又排序树的平均查找长度，仍采纳类似中序遍历的递归方式，用S记录总查找长度J记录每个结点的查找长度,S置初值为0,采纳累加的方式最终得到总查找长度s,平均查找长度就等于M(i为树中结点的总个数)。4 .删除结点：删除结点函数，采纳边杳找变删除的方式.假如没有查找到，则不对树做任何的修改：假如查找到结点，则分四种状况分别进行

10、探讨：(1)该结点左右子树均为空：(2)该结点仅左子树为空；(3)该结点仅右子树为空；(4)该结点左右子树都不为空；5 .用数列1.,生成平衡的二叉排序树BT;当插入新元素之后，发觉当前的二叉排序树BT不是平衡二叉排序树，则马上将它转换成新的平衡的二叉排序树BT.我所负成的模块函数定义如下voidTIaverseOrderDSTab1e(BSTreeDT.void(*Visit)(E1.emType)/按中序遍历具体的程序代码如下：typedefstructBSTNode二叉排序树类型E1.emTypedata;structBSTNode*1.chi1.d.*rchi1.d;BSTNode.*

11、BSTree:StatusInitDSTabIcdata)：averseOrdeDSTab1.e(Drchi1.d.Visit);)2.模块划分Main:主函数模块，在主函数中调用其他函数：(1)StatusInsertBSKBSTree&T,E1.emTypee)创建二叉排序树(2)voidTravorseOrderDSTab1.e(BSTreeDT,void(*Visit)(E1.emType)voidTraversQOrderDSTab1.e(AV1.TreeDT,void(*Visit)(E1.emType)中序遍历二叉排序树和平衡二叉排序树(3)voidas1.()/计算平均长度(4

12、)BSTreeSearchBST(BSTreeT,KeyTypekey)voidSearchBST(BSTree&T.KoyTypekey,BSTreef,BSTree&p,StatusAf1.ag)voidDe1.eteBSTree&p)StatusDe1.eteBST(BSTree&T,KeyTypekey)查找并删除结点(5)StatusInsertAV1.(V1.Tree&T.E1.emTypeeStatus&ta1.1.er)创建平衡二叉排序树voidRightBa1.ance(AV1.Tree&T)对以火P为根的二叉排序树作右旋处理，处理之后P指向新的树根结点，即旋转处理之前的左子

13、树的根结点void1.eftBa1.ance(AV1.Tree&T)对以*p为根的二叉排序树作左旋处理，处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点AV1.TreeSearchAV1.(AV1.TreeT,KeyTypekey)衡二叉排序树中进行查找.3.流程图四、程序的调试及运行结果说明主函数代码：voidmain()intnum,i,se1.ect,t,*dcpth,max.f1.ag：KeyTypej;Statusk;E1.emType*r,*tempr,IemPbSI,IemPaV1；BSTreebs1.,p；AV1.Treeav1.,q：do(Printf(谙输入要输入

14、的数据的总数，总数要大于0:);scanf(*,num);if(num=0)Prin1.Nn输入的总数要大于0,请重新输入：”);)whi1.e(num(=0)：g1._count=num：r=(E1.emType*)ma1.Ioc(g1.count*(siZeof(E1.emType)；Prin1.f(请输入生成二叉树的整型数据，前后数据用空格隔开:n)；for(i=0;ig1.count;i+)(scanf(%d,ri.key)：ri.order=i+1；)Printf(n用户输入的数据及序号如下：n)：for(i-0:ig1.-count;i+)(print(ri)；if(i+1.)%6=0)printf(vn);)se1.ect=0：f1.ag=0：InitDSTab1.e(bst);for(i=0;ig1._count：i+)InsertBST(bst,ri)：Printf(n按中序遍历该二叉排序树的结果如F：n*);TraVerSeOrderDSTabIe(bstprint):cout(end1.end1.以下