数据结构》课程设计--二叉排序树调整为平衡二叉树

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

1、计算机与信息工程系《数据结构》课程设计报告学号2013-2014学年第一学期1208020228《数据结构》课程设计报告题目：二叉排序树调整为平衡二叉树专业：网络工程班级：二姓名：汪杰指导教师：刘义红成绩：计算机与信息工程系2013年1月2日1计算机与信息工程系《数据结构》课程设计报告目录1、问题描述………………………………………2、设计思路(数学模型的选择)……………3、二叉排序树和平衡二叉树定义…………………………4、程序清单……………………………5.程序功能说明……………………………5.运行与调试分析……………………

2、…6.总结…………………………………1计算机与信息工程系《数据结构》课程设计报告1.问题描述输入带排序序列生成二叉排序树，并调整使其变为平衡二叉树，运行并进行调试。2.设计思路平衡二叉树的调整方法平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：⑴每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即

3、计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；⑵若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；⑶判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；⑷1计算机与信息工程系《数据结构》课程设计报告如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树

4、，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；3.二叉排序树和平衡二叉树定义二叉排序树二叉排序树（BinarySortTree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）（3）左、右子树也分别为二叉排序树；平衡二叉树平衡二叉树（BalancedBinaryTree或Height-BalancedTree）又称AVL树，它或者是一棵空树

5、，或者是具有以下性质的二叉；它的左子树右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，平衡二叉树上的任何节点的左子树和右子树的深度的差值只能是－1、0或1。4.程序功能说明voidpreorder(bintreet)/*前序遍历*/voidmidorder(bintreet)/*中序遍历*/lastorder(bintreet)/*后序遍历{bintreea;intj,k;clrscr();textcolor(2);1计算机与信息工程系《数据结构》课程设计报告printf("***************

6、***********欢迎您使用本二叉树操作系统**************************");printf("建造一棵二叉树请您输入各个结点的元素值,()表示一个空格键:");printf("输入示例:abc()()de()g()()f()()()回车:");a=createbitree();printf("您输入的二叉数嵌套法表示如下:");printree(a);printf("");printf("树的深度为:");j=treedepth(a);printf("%d",j);p

7、rintf("二叉数的叶子接点个数为:");k=treeleaf(a);printf("%d",k);printf("您所输入的二叉树的前序遍历顺序输出如下:");if(!a)printf("二叉树为空");else{preorder(a);printf("");}printf("您所输入的二叉树的中序遍历顺序如下输出:");if(!a)printf("二叉树为空");else{midorder(a);printf("");}printf("您所输入的二叉树的后序遍历顺序输出如下:");

8、if(!a)printf("二叉树为空");else{lastorder(a);printf("");}printf("您所输入的二叉树的层次顺序遍历输出如下:");1计算机与信息工程系《数据结构》课程设计报告if(!a)printf("二叉树为空");else{translevel(a