中北大学
数 据 结 构
课 程 设 计 说 明 书
学生姓名:
梁庆
学号:
0921010149
学 院 : 软件学院
专 业 : 软件工程
题 目 : 二叉平衡排序树
成 绩
指 导 教 师
贾美丽、康珺
2011 年 1 月 6 日
1.设计目的(小标题黑体五号字)
《数据结构》课程主要介绍最常用的数据结构,阐明各种数据结构内在的逻辑关系,
讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率
进行简单的分析和讨论。进行数据结构课程设计要达到以下目的:
了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;
初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的
工作方法和作风。
2.设计内容和要求
设计内容:
从一颗空树开始创建,在创建过程中,保证树的有序性,同时还要针对树的平衡性做
些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。
包括:(1)创建(插入、调整、改组);
(2)输出。
设计要求:
(1) 符合课题要求,实现相应功能;
(2) 要求界面友好美观,操作方便易行;
(3) 注意程序的实用性、安全性;
3.本设计所采用的数据结构
树 root 的最小结点; 树 root 的最大结点; key 查找; 前驱结点; 后继结点; 调整旋转操作; 构
造平衡二叉树; 二叉树的插入和删除;销毁平衡二叉树;中序遍历;先序遍历
4.功能模块详细设计
4.1 详细设计思想
树 root 的最小结点
如果根结点为空,则返回根节点;当根结点的左子树不为空,则根结点被赋值为原来根结
点的左子树,返回根结点;
树 root 的最大结点
如果根结点为空,则返回根节点;当根结点的右子树不为空,则根结点被赋值为原来根结
点的右子树,返回根结点;
1
求前驱结点
若所求的目标结点为空,则返回空;若目标结点的左子树不为空,则返回树 targe 的最大
结点;否则当目标结点的双亲不为空同时目标结点不等于目标结点的双亲结点的右子树,
则目标结点等于目标结点的双亲结点,返回目标结点的双亲结点;
求后继结点
如果目标结点为空,则返回空;如果目标结点的后继结点不等于空,则返回目标结点的最
大子树;否则当目标结点的双亲结点不为空同时目标结点不等于原来目标结点的双亲的左
子树,则目标结点等于目标结点的双亲结点,返回目标结点的双亲结点;
调整二叉树的平衡性
假设双亲不为空同时孩子也不为空,switch 双亲的平衡因子为 2 时,假设孩子的平衡因子
为-1 时,双亲结点的值被赋值为双亲结点的双亲的值,孩子的右结点被赋值为其左孩子的
值,如果这个孩子结点的右结点的左孩子的值不为空时,这个结点的双亲结点被赋值为原
先孩子结点的值,原来双亲结点的左孩子的值被赋值为孩子结点的右孩子的右孩子;如果
孩子结点的右孩子的右孩子不为空,则其结点的右孩子的双亲结点被赋值为原先双亲结点
的值,孩子结点的右孩子的左孩子为孩子结点的值,孩子结点的双亲结点的值被赋值为孩
子结点的右孩子的值,孩子结点的右孩子的右孩子的值被赋值为双亲结点的值;如果双亲
结点的双亲不为空,在这个条件下如果双亲结点的双亲的左孩子恒等于双亲结点的值,则
双亲结点的双亲的左孩子的值等于孩子结点的右孩子的值,否则根结点被赋值为孩子结点
的右孩子的值,双亲结点的双亲值被赋值为孩子结点的右孩子的值,如果孩子结点的右孩
子的平衡因子等于 0,则双亲的平衡因子为 0,孩子的平衡因子为 0,否则如果孩子结点的
右孩子的平衡因子为-1,则双亲结点的平衡因子为 0,且孩子结点的平衡因子为 1,否则
双亲结点的平衡因子为-1,且孩子结点的平衡因子为 0;孩子结点的右孩子的平衡因子为
0,
否则孩子结点的双亲被赋值为双亲结点的双亲的值,双亲结点的左孩子的值被赋值为孩
子结点的右孩子的值,如果孩子结点的右孩子的值不为空,则孩子结点的右孩子的双亲结
点的值为双亲结点的值,孩子结点的右孩子的值等于双亲结点的值;如果双亲结点的双亲
的值不为空,在这个条件下如果双亲结点的双亲的左孩子的值恒等于双亲结点的值,则双
亲结点的双亲的左孩子的值被赋值为孩子结点的值,否则双亲结点的双亲的右孩子的值为
孩子结点的值;否则根结点的值为孩子结点的值,双亲的双亲的值被赋值为孩子的值,吐
过孩子结点的平衡因子为 1,则孩子的平衡因子为 0,且双亲的平衡因子也为 0,否则孩子
结点的平衡因子为-1,双亲的平衡因子为 1;
平衡因子为-2 的时候略
二叉排序树的插入
在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义。
插入过程:若二叉排序树已存在,则返回根节点;
当节点不存在时,将待插结点关键字 key 和树根关键字 parent->key 进行比较,
若 key<parent->key,则插入到根的左子树中,
否则,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同,如此进行
下去,直到把结点作为一个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键
字的结点为止。并且注意二叉树的平衡性,时刻调整。
2
二叉排序树的删除
假设在二叉排序树上被删结点为*tp,其双亲结点为*parent,且不失一般性,可设*
*parent 是* parent->left;的左孩子。
若*parent 结点为叶子结点,即 PL 和 PR 均为空树。由于删去叶子结点不破坏整棵树的结
构,则只需要修改其双亲结点的指针即可;若*parent 结点只有左子树 PL 或者只有右子
树 PR,此时只要令 PL 或 PR 直接成为其双亲结点*f 的左子树即可。显然,作此修改也不
破坏二叉排序树的特性;若*parent 结点的左子树和右子树均不空,并且注意二叉树的平衡
性,时刻调整;
把二叉排序树转换为二叉平衡排序树
一般情况下,假设由于插入结点而失去平衡,找出其中的最小不平衡子树,在保持二叉排
序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使
之成为新的平衡子树。具体步骤如下:
(1)每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先
结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值均不超过 1,则平衡二叉树没
有失去平衡,继续插入结点;
(2)若插入结点的某祖先结点的平衡因子的绝对值大于 1,则找出其中最小不平衡子树的根
结点;
(3)判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整;
(4)如果是 LL 型或 RR 型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,
应用旋转优先原则调整冲突;如果是 LR 型或 LR 型,则需应用扁担原理旋转两次,第一次
最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树
在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;
(5)计算调整后的平衡二叉树中各结点的平衡因子,检验是否因为旋转而破坏其他结点的平
衡因子,以及调整后的平衡二叉树中是否存在平衡因子大于 1 的结点。
调整二叉树的平衡性
主要有四种调整类型根据平衡因子主要有 LR、LL、RL、RR
(1)、若双亲结点的平衡因子 的值为 2 时,孩子结点的平衡因子为-1 时是 LR 型,否则
为 LL 型;
(2)双亲结点的平衡因子的值为-2 时,孩子结点的平衡因子为 1 时是 RL 型,否则为 RR
销毁平衡二叉树
如果根结点不为空,则销毁根结点的左子树,销毁根结点的右子树,释放根结点,重复则
根结点为空;
中序遍历
根结点不为空,先遍历左子树,然后输出左子树,根结点,再遍历右子树
先序遍历
根结点不为空,先遍历根结点,再遍历左子树,右子树
给出了一组数据{1, 13, 7, 4},对数据中序遍历和先序遍历,然后是插入、删除、
查询、退出操作。
4.2 核心代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
3
#include <errno.h>
#include <assert.h> // assert 用于调试声明宏,用于定位程序开发中的逻辑
//错误当参数 expression 为 false 时程序执行被中断
typedef struct node node;
struct node
{
node* parent;
node* left;
node* right;
int balance;
int key;
};
extern void interordertraverse(node* root); //中序遍历
extern void preordertraverse(node* root); //前序遍历
int searchNode(int key, node* root, node** parent) //按 key 查找结点
{
node* temp;
assert (root != NULL);
temp = root;
*parent = root->parent;
while (temp !=NULL)
{
if (temp->key == key) return 1;
else{
*parent = temp;
if (temp->key > key)
temp = temp->left;
else
temp = temp->right;
}
}
return 0;
}
node* minNode(node* root) //树 root 的最小结点
{
if (root == NULL)
return NULL;
while (root->left != NULL)
4