I
II
目 录
课程设计成绩评定表 ...................................I
一、需求分析 .........................................1
1.1 问题描述 ...............................................1
1.2 基本要求 ...............................................1
二、概要设计 .........................................2
2.1 存储结构、逻辑结构 .....................................2
2.2 基本算法 ...............................................2
三、详细设计 .........................................3
3.1 程序流程图 .............................................3
3.2 主要算法实现 ...........................................3
四、调试分析 .........................................4
五、测试数据和结果 ...................................5
5.1 测试数据 ...............................................5
5.2 测试结果 ...............................................5
六、 心得体会 ........................................6
七、附录 .............................................7
附录 1 团队成员分工表 ......................................7
附录 2 程序代码 ............................................8
银川科技学院课程设计说明书
第 1 页 共 27 页
一、需求分析
1.1 问题描述
利用 C 语言实现平衡二叉树。
从一颗空树开始创建，在创建过程中，保证树的有序性，同时还要针对树的平衡
性做些调整。最终要创建好二叉平衡排序树。
（1）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供
选择。每种操作均要提示输入关键字。在查找时，如果查找的关键字不存在，则把其
插入到平衡二叉树中。每次插入或删除一个结点后，应更新平衡二叉树的显示。
（2）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数
字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，
并对其进行相应的提示。
（3）实现动态查找表的三种基本功能：查找、插入和删除
包括：（1）创建（插入、调整、改组）；
（2）输出。
设计要求：
(1) 符合课题要求，实现相应功能；
(2) 要求界面友好美观，操作方便易行；
(3) 注意程序的实用性、安全性；
1.2 基本要求
1.建立平衡二叉树：要求以回车('\n')为输入结束标志,输入数列 L，生成一棵
二叉平衡树 T。
2.中序遍历并输出结果：要求将第一步建立的二叉树进行中序遍历，并将结果输
出。
3.平均查找长度并输出：要求计算二叉排序树 T 查找成功的平均查找长度,输出
结果。
4.删除节点：要求输入元素 x,查找二叉平衡树 T,若存在含 x 的结点,则删该结点,
并作中序遍历(执行操作 2)；否则输出信息“无 x”。
5.插入节点到平衡二叉树：要求用一个新加入的节点，生成平衡的二叉平衡树 BT:
当插入新元素之后，发现当前的二叉平衡树 BT 不是平衡的二叉平衡树，则立即将它
第 2 页 共 27 页
转换成新的平衡的二叉平衡树 BT；
6.平均查找长度：计算平衡的二叉平衡树 BT 的平均查找长度，输出结果。
银川科技学院课程设计说明书
第 3 页 共 27 页
二、概要设计
2.1 存储结构、逻辑结构
存储结构：struct root
结构体的设计：树 root 的最小结点; 树 root 的最大结点; key 查找; 前驱结点; 后
继结点; 调整旋转操作; 构造平衡二叉树; 二叉树的插入和删除；销毁平衡二叉树；
中序遍历；先序遍历
逻辑结构：链表结构，队列结构
2.2 基本算法
平衡二叉树( AVL 树 )
①平衡二叉树(Balanced Binary Tree)是指树中任一结点的左右子树的高度大
致相同。
②任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡
的。通常，只要二叉树的高度为 O(1gn)，就可看作是平衡的。
③平衡的二叉排序树指满足 BST 性质的平衡二叉树。
④AVL 树中任一结点的左、右子树的高度之差的绝对值不超过 1。在最坏情
况下，n 个结点的 AVL 树的高度约为 1.44lgn。而完全平衡的二叉树高度约为 lgn，AVL
树是最接近最优的。
1.2.6 平衡因子
树 root 的最小结点
如果根结点为空，则返回根节点；当根结点的左子树不为空，则根结点被赋值为原来
根结点的左子树，返回根结点；
树 root 的最大结点
如果根结点为空，则返回根节点；当根结点的右子树不为空，则根结点被赋值为原来
根结点的右子树，返回根结点；
求前驱结点
若所求的目标结点为空，则返回空；若目标结点的左子树不为空，则返回树 targe 的
最大结点；否则当目标结点的双亲不为空同时目标结点不等于目标结点的双亲结点的
右子树，则目标结点等于目标结点的双亲结点，返回目标结点的双亲结点；
求后继结点
如果目标结点为空，则返回空；如果目标结点的后继结点不等于空，则返回目标结点
的最大子树；否则当目标结点的双亲结点不为空同时目标结点不等于原来目标结点的
双亲的左子树，则目标结点等于目标结点的双亲结点，返回目标结点的双亲结点；
调整二叉树的平衡性
假设双亲不为空同时孩子也不为空，switch 双亲的平衡因子为 2 时，假设孩子的平
