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

B04900083湖或笈，挈花HUBEIPO1.YTECHNICUNIVERSITY课程设计教学院计算机学院课程名称数据结构及飘法廊曰二叉排序树及平衡二叉持芹树域本操作®曰的实现专业计算机科学及技术班级二班姓名同组人员指导老师成俊2015年12月27日课程设计任务书20152016学年第1学期学生姓名:一,专业班级：计科二指导老师：成俊工作部门：计算机学院一、课程设计题目：二又排序树及平衡二又排序树基本操作二、课程设计内容用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作:以回车Cn,为输入结束标记,输入数列1.,生成二叉排序树T：对二叉排序树T作中序遍历：计算二叉择序树T的平均,输出结果：输入元素X,查找二叉排序树T.若存在含X的结点，则删除该结点，并作中序遍历：否则输出信息“无结点x”：推断二叉排序树T是否为平衡二叉树：再用数列1.,牛成平衡二叉排序树BT:当插入新元素之后，发觉当前的二叉排序树BT不是平衡二叉排序树，则马上将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均杳找长度,输出结果.三、进度支配1 .分析问题，给出数学模型,选择数据结构。2 .设计算法，给出算法描述3 .给出海程序清单4 .编辑、编译、调试源程序5 .撰写课程设计报告四、基本要求编写AV1.树判别程序，并判别一个二叉排序树是否为AV1.树。二叉排序树用其先序遍历结果表示，如：5,2,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 .随意插入或删除一个结点后推断是否为平衡二叉树。5 .将非平衡二叉树转换成平衡二叉树。6 .按中序遍历输出这棵平衡二叉树.7 .课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车（'n'）为输入结束标记,输入数列1.,生成二叉排序树T：对二叉排序树T作中序遍历;计算二叉排序树T的平均查找长度,输出结果：输入元素X,查找二叉排序树T.若存在含X的结点，则删除该结点，并作中序遍历：否则输出信息“无结点X"；推断二叉排序树T是否为平衡二叉树:再用数列1.生成平衡二叉排序树BT:当插入新元素之后，发觉当前的二叉排序树BT不是平衡二叉排序树,则马上招它转换成新的平衡二叉排序树BT：计算平衡的二叉排序树BT的平均查找长度，输出结果.编写AV1.树判别程序，并判别一个二叉排序树是否为AV1.树。二叉排序树用其先序遍历结果表示,如：5,2,1,3,7,8。实现AV1.树的ADT.包括其上的基本操作：结点的加入和删除：另外包括将一般二叉排序树转变为AV1.树的操作.实现提示主要考虑树的旋转操作。二、总体方案设计1）建立二叉排序树,编写二叉排序树T作中序遍历.2）查找删除二叉排序树函数.3）编写推断二叉排序树T是否为平衡二叉树函数，把非平衡二叉排序树转换成平衡二叉排序树。4）编写计算二叉树叮的平均查找长度函数。我负责的是第一部分，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1 .若它的左子树不空，则左子树上全部结点的值均小丁它的根结点的值：2 .若它的右子树不空，则右子树上全部结点的值均大于它的根结点的值：3。它的左、右子树也分别为二叉排序树。以链表存储结构创建二叉排序树，以回车（n'）为输入结束标记,输入数列1.,生成二叉排序树T；对二叉排序树T作中序遍历。中序遍历二叉树算法的框架是：若二叉树为空，则空操作：否则（1）中序遍历左子树（1.）：（2）访问根结点（V）;（3）中序遍历右子树（R）。函数1:中序遍历二叉树中序遍历二叉树也采纳递归函数的方式，先访问左子树2i,然后访问根结点i.最终访问右子树2i+1.°先向左走究竟再值层返回，直至全部的结点都被访问完毕。（谢石林）函数2:平均查找长度计.算二叉排序树的平均查询长度时，可采纳类似中序遍历的递归方式，用Sid录总查询长度，j记录每个结点的查询长度，S值初值为0,采纳累加的方式最总得到总查询长度s,平均查询长度等于s/iG为树中结点个数）。（吴进）函数3：查找删除二叉排序树函数输入元素X,查找二叉排序树T,若存在含X的结点，则JH该结点,并作中序遍历（执行函数1）；否则输出信息“无x”。（张常勋）函数4：推断二叉排序树T是否为平衡二叉树，若不是则用数列1.,生成平衡排序二叉树BT：最终调用函数6,接着调用函数5.推断二叉排序树是否为平衡二叉树的函数也是采纳递归函数的方式，分别判定以树中每个节点为根节点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二义树.函数5：在平衡二叉树BT上插入新元素，若发觉当前的二叉排序树BT不是平衡二叉排序树，则马上将它转换成新的平衡二叉排序树BT。三、具体设计1.课程设计总体思想1。生成二叉排序树：建立二叉排序树采纳的是边杳找边插入的方式。查找函数采纳递归的方式进行查找。查找是根据二叉排序树的性质进行的，通过比较要插入元素的关键字及当前结点关键字的大小来确定我们是遍历当前结点的哪个子树.假如小于当前结点关键字，则遍历它的左子树：大于当前结点关键字,则遍历它的右子树：等丁当前关键字，则此元素不插入原树.我们根据这样的规律，始终向下遍历，知道它的r树为空,则返回当前结点的上个结点。然后利用插入函数将该元素插入原树。2。中序遍历:对二叉排序树进行中序遍历采纳递归函数的方式。在根节点不为空的状况下,先访问左子树,在访问根结点，最终访问右子树。3 .平均查找长度：计算二又排序树的平均查找长度，仍采纳类似中序遍历的递归方式，用S记录总查找长度J记录每个结点的查找长度,S置初值为0,采纳累加的方式最终得到总查找长度s,平均查找长度就等于M(i为树中结点的总个数)。4 .删除结点：删除结点函数，采纳边杳找变删除的方式.假如没有查找到，则不对树做任何的修改：假如查找到结点，则分四种状况分别进行探讨：(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.*BSTree:StatusInitDSTabIc<BSTrcc&DT)(构造一个空的动态BST杳找表DTDT=NU1.1.：return1;)voidTravcrscOrdcrDSTab1.c(BSTrccDT.void(*Visit)(E1.cmTypc)(按中序遍历对DT的每个结点谢用函数ViSit()一次且至多一次if(DT)TraverseOrderDSTab1.e(DT)Ichi1.d.Visit)：Visit(DT>data)：averseOrdeDSTab1.e(D>rchi1.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)BSTreeSearchBST(BSTreeT,KeyTypekey)voidSearchBST(BSTree&T.KoyTypekey,BSTreef,BSTree&p,StatusAf1.ag)voidDe1.ete<BSTree&p)StatusDe1.eteBST(BSTree&T,KeyTypekey)查找并删除结点(5)StatusInsertAV1.(V1.Tree&T.E1.emTypee»Status&ta1.1.er)创建平衡二叉排序树voidRightBa1.ance(AV1.Tree&T)对以火P为根的二叉排序树作右旋处理，处理之后P指向新的树根结点，即旋转处理之前的左子树的根结点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("谙输入要输入的数据的总数，总数要大于0:);scanf(*<',num);if(num<=0)Prin1.N''n输入的总数要大于0,请重新输入：”);)whi1.e(num(=0)：g1._count=num：r=(E1.emType*)ma1.Ioc(g1.count*(siZeof(E1.emType)；Prin1.f("请输入生成二叉树的整型数据，前后数据用空格隔开:n")；for(i=0;i<g1.count;i+)(scanf("%d",ri.key)：ri.order=i+1；)Printf("n用户输入的数据及序号如下：n'')：for(i-0:i<g1.-count;i+÷)(print(ri)；if(i+1.)%6=0)printf(vn);)se1.ect=0：f1.ag=0：InitDSTab1.e(bst);for(i=0;i<g1._count：i+)InsertBST(bst,ri)：Printf("n按中序遍历该二叉排序树的结果如F：n*);TraVerSeOrderDSTabIe(bst»print):cout(<end1.<<end1.<<"以下是对二叉排序树的基本操作:"<<end1.«*1.查找一个节点”(<end1.2。插入个节点”<(end1.<”3。删除个节点”<<end1.<”4。判别二元查找树是否为平衡二叉树”end1.«”5.二叉树转换为平衡二叉树”(<end1.<<"6。退出系统"(<end1.;doif(f1.ag=6);PrinIr("n请输入二叉排序树基本操作的选项：”)；SCanf("%dv,se1.ect)；switch(se1.ect)case1:Printf(“请输入待查找的数据：”);scanf(%d,&j);p=SearchBST(bst.j);if(p)Printf(''n二叉排序树中存在此值：”)；print(p>data):e1.sePrinIf("n二叉排序树中不存在此值.”)；break；case2:PriiUfC请输入需插入的数据：");scanf(",&j);p=SearchBST(bst,j);if(p)(printf(wn二叉排序树中存在此值：")：prim<p-)data)；)e1sotempi-=(E1.emType*)(ma11oc(g1._count*sizeof(E1.emTypc)：for<i=0：i(g1._count：i+)(tempri,key=ri.key;tempri。orderri.order；)tempbst.key=j：tcmpbst.order=+g1._count;r=(E1.cmType*)(ma1.1.oc(g1._count*sizcof<E1.cmTypc)；for(i=0;i<g1._count-1.;i+)(ri。key=tempri.key;riorder=tempri.order：)rikey=Iempbst.key;rieorder=IemPbS1.order；Inser1.BST(bst.1.empbst):print(,数据已经插入二叉排序树中.”)：printf("n按中序遍历该二又排序树的结果如下：n'')：TraverscOrdcrDSTab1e(bst,print)；break;case 3: Printf(”请输入需。除的数据：”)；scanf(,%d",&j);p=SearchBST(bst.j);if(p)tempr=(E1.emType*)(ma1.Ioc(g1.-count*sizeof(E1.emType)；for(i=0:i<g1._count；i÷+)tempri0key=ri<.key；tempri.order=ri.order；De1.eteBST(bst,j):g1._count;r=(E1.emType*)(ma1.1.oc(g1._count*sizeof(E1.emType)；for<i=0,t=0；i<g1._count;i+)if(1.enpri.key!=j)(rtkey=tempri.key;rt.order=tempri«.order;t+：)PrinIfT'二叉排序树中该数据已经删除。”);TraverSeOrderDSTab1o(bst,print)；e1.sePrintfr需删除的数据不存在于二叉树中。”)：break：case 4: depth=(int*)Ina1.1.OC<g1.count*(sizeof(in1.)；BSTDvpthDiff(bst,depth);max=dep1.h;for(i=1.:i(g1._count：i+)if(max<depthij)max=depthiJ：if(max<2)Printf("n该二叉排序树是平衡二叉树.;e1.sePrinIf("n该二叉揖序树不是平衡二叉树。”)；if(max>4)printf("n该二叉排序树有结点的左右子树之差大于4.系统建议您将该二叉排序树转换成平衡二又树."):break：case 5: InitDSTab1.e(av1.)：for(i=0；i(g1.count；i+)InsertAV1.(av1.,ri,k);printfC,该二叉排序树转换成平衡二叉树”)：TraverscOrderDSTab1.e(av1.,print);f1.ag=6：break：case6：break；defau1.t:Prinr1.您输入的选项是错误的，靖重新输入！”);break;whi1.e(se1.ect!=6);输入数据用空格符隔开：随后系统会自动对数据进行中序遍历:功能菜单:一退叉出对二二堂树叉-衡平树为叉否二I树平执行节点的查找功能:排执行插入功能:推断是否为平衡二叉树假如不是可执行转换功能.r5CS2><6.3><9,9><10,10><I1.i1.414.IX1S,SX21.6><23.7><36.8>_J五、课程设计总结本次的数据结构课程设计,让我们独立完成个小系统,组员们从选题到任务分派，都全身心投入。在本次数据结构课程试验中，我们一方面对数据结构有了更好的相识,对数据结构语法上面的学问有了一个应用性的笈习，同时对文件操作有了更好的学习，另一方面组员们对编程的一些良好习惯也有了相识，编程上的细微环节处理也有/解，总之这次训练让我学到许多，对自己也是一个考验和熬炼.通过这次数据结构实训，我们不仅巩固了课本中所学习的学问，还加强了对学问的运用实力，学会了如何用多种方法解决问题，同时也激发了我们对数据结构的学校爱好，信任在以后应用中我们会去的更好的成果，利用VC学问去修改、编写更多的程序去解决生中的问胭，为人们的衣食住行供应便利。这次课程设计，我们组内先安排/各自的任务，然后分别执行。这种方式让我们思路清息，使设计过程简洁化快捷化，且让我们相识到了团队合作的重要性。在这次程序设计中，我负贡的是主函数和二叉排序树的创建。刚得到任务时，的确不知从何处搭起，通过不断学习和请教他人，我渐渐摸清了思路，最终搞出来了。说白了，就是采纳边建立二插排序树采纳边查找边插入的方式.铿找函数采纳递归的方式进行隹我.假如性找胜利则不应再插入原树，否则返回当前结点的上一个结点.然后利用插入函数将该元素插入原树。就是这么简洁。对函数的构造以及调用有了更进步的驾驭，让我在调试程序是有了肯定的阅历。多考虑算法的可行性。在遇到问题是仔细考虑,同时让我意识到数据结构在编程中的重要作用.算法的优越性对程序的重要性.让我在调试程序是有了肯定的阅历。参考文献(U南浩强.C程序设计咫解及上机指导(其次版北京.清华高校出版社,2000年9月.2李春源.数据结构习题及解析M.2版.北京：清华高校出版社,2004附录