1、 数据结构数据结构课程设计报告课程设计报告 题目：题目： 二叉排序树调整为平衡二叉树二叉排序树调整为平衡二叉树 专业：专业： 网络工程网络工程 班级：班级： 姓名：姓名： 指导教师：指导教师： 成绩：成绩： 计算机与信息工程系计算机与信息工程系 20132013 年年 1 1 月月 2 2 日日 计算机与信息工程系 数据结构课程设计报告 1 目录 1、问题描述 2、设计思路(数学模型的选择) 3、二叉排序树和平衡二叉树定义 4、程序清单 5.程序功能说明 5.运行与调试分析 6.总结 计算机与信息工程系 数据结构课程设计报告 1 1.问题描述 输入带排序序列生成二叉排序树，并调整使其变为平衡二
2、 叉树，运行并进行调试。 2.设计思路 平衡二叉树的调整方法 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结 点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡 性，若是，则找出其中的最小不平衡子树，在保持二叉排序树 特性的前提下，调整最小不平衡子树中各结点之间的链接关 系，进行相应的旋转，使之成为新的平衡子树。 具体步骤如下： 每当插入一个新结点，从该结点开始向上计算各结点的平 衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖 先结点的平衡因子的绝对值均不超过 1，则平衡二叉树没有失 去平衡，继续插入结点； 若插入结点的某祖先结点的平衡因子的绝对值大于 1，则 找出其中最小
3、不平衡子树的根结点； 判断新插入的结点与最小不平衡子树的根结点的关系，确 定是哪种类型的调整； 如果是 LL 型或 RR 型，只需应用扁担原理旋转一次，在旋 转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果 是 LR 型或 LR 型，则需应用扁担原理旋转两次，第一次最小不 平衡子树的根结点先不动，调整插入结点所在子树，第二次再 计算机与信息工程系 数据结构课程设计报告 1 调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋 转优先原则调整冲突； 3.二叉排序树和平衡二叉树定义 二叉排序树 二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是 一棵空树；或者是具有下列
4、性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根 结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根 结点的值； （3）（3）左、右子树也分别为二叉排序树； 平衡二叉树 平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree）又称 AVL 树，它或者是一棵空树，或者是具有以下性质 的二叉；它的左子树右子树都是平衡二叉树，且左子树和右子 树的深度之差的绝对值不超过 1，平衡二叉树上的任何节点的 左子树和右子树的深度的差值只能是1、0 或 1。 4.程序功能说明 void preorder(bintree t)/*前
5、序遍历*/ void midorder(bintree t)/*中序遍历*/ lastorder(bintree t)/*后序遍历 bintree a;int j,k;clrscr();textcolor(2); 计算机与信息工程系 数据结构课程设计报告 1 printf(“*欢迎您使用本二叉树 操作系统*n“); printf(“建造一棵二叉树请您输入各个结点的元素值,()表示 一个空格键:n“); printf(“输入示例:abc()()de()g()()f()()()回 车:n“);a=createbitree(); printf(“您输入的二叉数嵌套法表示如 下:n“);printre
6、e(a);printf(“n“); printf(“树的深度为:n“); j=treedepth(a);printf(“%dn“,j); printf(“二叉数的叶子接点个数为:n“); k=treeleaf(a);printf(“%dn“,k); printf(“您所输入的二叉树的前序遍历顺序输出如下:n“); if(!a) printf(“二叉树为空n“); elsepreorder(a);printf(“n“); printf(“您所输入的二叉树的中序遍历顺序如下输出:n“); if(!a) printf(“二叉树为空n“);else midorder(a);printf(“n“); printf(“您所输入的二叉
