数据结构设计性实验报告
课程名称 数据结构实验■
题目名称 平衡二叉树
学生学院_ 计算机学院
专业班级_
学 号
学生姓名
指导教师
2015年6月14日
目录
TOC \o "1-5" \h \z \o "Current Document" 一、 设计任务、要求以及所用环境及工具 . 4
\o "Current Document" 实验设计任务 . 4
实验要求 . 4
编程环境 . 4
\o "Current Document" 抽象数据类型及接口简要描述 . 5
\o "Current Document" 抽象数据类型 . 5
\o "Current Document" 接口简要描述 . 7
\o "Current Document" 算法设计 8
\o "Current Document" 程序测试 17
测试代码 . 17
测试结果 . 18
测试分析 . 20
\o "Current Document" 思考与小结 21
设计任务、要求以及所用环境及工具
实验设计任务
以教材中讨论的各种抽象数据类型为对象， 利用C语言的数据类型表示和实现其中某个
抽象数据类型。可选的抽象数据类型如下表所列：
编号
抽象数据类型
基本难度
存储结构
1
栈和队列
1.0
顺序和链接
2
线性表
1.0
顺序和链接
3
哈希表
1.1
任选
4
二叉树
1.2
任选
5
堆
1.2
任选
6
二叉排序树
1.2
任选
7
平衡二叉树
1.3
任选
8
树
1.2
任选
9
并查集
1.2
任选
10
B树
1.4
任选
11
有向图
1.3
任选
12
无向图
1.3
任选
13
有向带权图
1.3
任选
注：如果基本操作数量较多，可选择实现其中一个基本操作子集。
实验要求
实验要求如下：
1 ?首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择 题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。 若学生对教材以外的相关
题目较感兴趣，希望选作实验的题目时， 应征得指导教师的认可， 并写出明确的抽象数据类
型定义及说明。
实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象 数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。
实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录 各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。
实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的 数据及相应的运行结果。
编程环境
r l： tzd
HET 募権怪 4.*
J □
"三耙■耐3E P|
C*<
底总￥i4 C4 +
ATk
Viitad C--4
CLU
和
mi*
ECiy.i
G91D.
EiW
? L
a话亦需
▼
Z穷A
下完成。
本次实验设计采用 C++
本次实验设计采用 C++语言，在 Microsoft Visual Studio2010 IDE
所创建的项目类型 Win32控制台应用程序：
抽象数据类型及接口简要描述
本次数据结构实验设计我选择的是二叉平衡树 （AVL）,使用C++面向对象编程语言实现。
利用C++泛型编程技术完成 AVL类AVLTree。
抽象数据类型
平衡二叉树结点的 ADT为：
template <type name T>
class AVLTreeNode
{
public :
T _key; II结点关键字
int _bf; II结点平衡因子
AVLTreeNode *_lchild ; II 结点的左孩指针
AVLTreeNode *_rchild ; II 结点的右孩指针
bool bf)II构造函数
bool bf)
AVLTreeNode(T key ‘AVLTreeNode *lchild , AVLTreeNode *rchild :_key(key), _l child(lchild),_rchild(rchild),_bf(bf){};
};
平衡二叉树类AVLTree的定义为：
template < typename T> class AVLTree
{ private :
AVLTreeNode<T> * _Root ; // 树的根结点 bool _taller ; // 树是否长高的标记
public :
AVLTree(){_Root=NULL;}; // 默认构造函数
~AVLTree(){}; // 析构函数
// 遍历操作void preOrder();void inOrder();
// 遍历操作
void preOrder();
void inOrder();
void postOrder();
bool insert (T key);
void print();
AVLTreeNode<T>* search (T key) ;
AVLTreeNode<T>* minimumNode();
AVLTreeNode<T>* maxmumNode();
void remove(T key); void destory ();
// 前序
// 中序
// 后序
// 插入
// 打印
// 二叉树的查找
// 查找最小的结点
// 查找最大的结点
// 删除结点
II销毁AVL树
private :
II 删除时的左平衡操作
void delLeftBalance(AVLTreeNode<T>*& tree , int childBf);
II 删除时的右平衡操作
void delRightBalance(AVLTreeNode<T>*&tree , int childBf); II 中序遍历
void inOrder(AVLTreeNode<T>*& tree);
II 前序 遍历 void preOrder(AVLTreeNode<T>*& tree);
II 后序遍历 void postOrder(AVLTreeNode<T>*& tree);
II 像二叉树中插入新结点
bool insert(AVLTreeNode<T>*& tree ,T key, bool &taller);
II插入时导致LL型失衡的右旋操作
void rightRotate(AVLTreeNode<T> *& tree);
II插入时导致RF型失衡的左旋左旋
void leftRotate(AVLTreeNode<T> *& tree);
II 左平衡处理
void leftBalance(AVLTreeNode <T>*& tree);
II 右平衡处理
void rightBalance(AVLTreeNode<T> *& tree);
II 删除时的左平衡处理
void dLeftBalance(AVLTreeNode <T>*& tree) ;
//删除时的右平衡处理
void dRightBalance(AVLTreeNode <T>*& tree) ;
//打印二叉树
void print(AVLTreeNode<T>*& tree);
//查找二叉树中指定结点
AVLTreeNode<T>* search(AVLTreeNode<T>* &tree,T key);
//查找二叉树最小的结点
AVLTreeNode<T>* mi nimumNode(AVLTreeNode<T>* & tree);
//查找二叉树最大的结点
AVLTreeNode<T>* maxmumNode(AVLTreeNode<T>* & tree);
//删除指定关键字的结点
AVLTreeNode<T>* remove(AVLTreeNode<T>*&tree,AVLTreeNode<T>*z);
//销毁二叉树，释放所有申请的空间
void destory(AVLTreeNode<T>*& tree);
};
接口简要描述
遍历操作接口
遍历二叉树是指从根结点出发， 按照某种次序访问二叉树所有结点， 使得每个结点
被且仅被访问一次，这里的访问可以是输出、比较、更新、查看结点信息等各种操作。
遍历是二叉树的一类重要操作， 也是二叉树的其他一些操作和各种应用算法的基本框架。
用V表示根节点，用L表示左孩子，用R表示右孩子，且规定先 L后R的访问顺序，则 有VLR（前序）、LVR （中序）、LRV（后续）三种遍历算法。对于图 a中的二叉树，其遍
历结果为：
S3
47 9S '
19 55
（50 ）
前序遍历：88 47 19 55 50 98
中序遍历：19 47 50 55 88 98 后序遍历：19 50 55 47 98 88
AVLTree类提供了三个遍历接口，分别是前序、中序、后续遍历。这三个接口都使 用递归算法实现，调用遍历接口可以得到相应遍历次序的序列。
插入接口
插入操作是AVL树的关键操作，用于向AVL插入新的结点，其难点在于每次插入操 作都要维护树的平衡性。
向平衡二叉树中插入一个新结点后如果破坏了平衡二叉树的平 衡性，首先要找出插入新结点后失去平衡的最小子树（最小失衡子树）根结点的指针， 然后再调整这个子树中有关结点之间的连接关系，使之成为新的平衡二叉树。
当进行插入操作时， 找到该需要插入结点的位置插入后， 从该结点起向上寻找， 第 一个不平衡的结点 （平衡因子变成了 -2 或 2）。以该结点为根的子树即为最小失衡子树。
二叉排序树转成平衡二叉树失去平衡后进行调整的四种情况：
（1）单向右旋平衡处理。
当在左子树插入左结点，使平衡因子由 1 增至 2 时。
（2） 单向左旋平衡处理。
当在右子树中插入有节点，使平衡因子由 -1 增至 -2 时。
（3）双向旋转（先左后右）平衡处理。
当在左子树上插入右结点，使平衡因子由 1 增至 2 时。
（4） 双向旋转（先右后左）平衡处理。
当在右子树上插入左结点，使平衡因子由 -1 增至 -2 时。
插入接口对上述的情况做了处理。
删除接口
删除操作与插入操作一样， 需要在每次删除时维护树的平衡性， 而且删除比插入需 要处理的情况更加复杂。
在实验过程中我主要想法是抓住 “判断树的高度是否降低， 若 是则进行平衡因子判断及结点调整”。
总的来说， 导致树高度降低的原因就是某个结点 的平衡因子由 1（或 -1）变成 0的时候。删除操作采用递归算法实现。
二叉树查找接口
AVLTree 类供提供了三种查找操作， 一种是传统意义上的查找某个指定关键字的结 点，另外两个是查找关键字最小及最大结点。
查找算法使用递归实现。
打印二叉树接口
二叉树打印即描述二叉树的结构构成情况， 例如描述某个结点的左孩子及右孩子指 针指向，依据该接口的输出语句可描画出二叉树的结构。
打印接口同样采用递归算法来实现。
销毁二叉树接口
该接口将创建 AVL 树时申请的结点资源释放， 使用递归算法将整棵二叉树进行销毁。
算法设计
孩子表示法存储结构
// 定义并初始化一个新结点
//AVLTreeNode 类的默认构造函数
AVLTreeNode(T key ,AVLTreeNode *lchild , AVLTreeNode *rchild , bool bf) :_key(key), _lchild(lchild),_rchild(rchild),_bf(bf){};
}
}
// 前序遍历
// 接口
template <typename T>
void AVLTree<T>::preOrder()
{
preOrder(_Root);
}
// 类的私有函数，供接口调用 template <typename T>
void AVLTree<T>::preOrder(AVLTreeNode<T>*& tree) {
if (tree)
{
cout<<tree->_key<< " " ; preOrder(tree->_lchild); preOrder(tree->_rchild);
}
}
// 中序遍历 template < typename T> void AVLTree<T>::inOrder() {
inOrder(_Root);
} template < typename T> void AVLTree<T>::inOrder(AVLTreeNode<T>*& tree) {
if (tree)
{ inOrder(tree->_lchild); cout<<tree->_key<< " " ; inOrder(tree->_rchild);
}
}
// 后序遍历
// 后序遍历 template < typename T> void AVLTree<T>::postOrder() {
postOrder(_Root);
template <typename T>
void AVLTree<T>::postOrder(AVLTreeNode<T>*& tree)
{
if (tree)
{ postOrder(tree->_lchild); postOrder(tree->_rchild); cout<<tree->_key<< " " ;
}
}
// 查找指定结点 template < typename T>
AVLTreeNode<T>* AVLTree<T>::search(AVLTreeNode<T>* &tree,T key) {
AVLTreeNode<T>* temp = tree;
while (temp != NULL)
{
if (temp->_key == key) return temp;
else if (temp->_key>key) temp = temp->_lchild;
else
temp = temp->_rchild;
}
return NULL;
}
// 查找最小结点 template < typename T>
AVLTreeNode<T>* AVLTree<T>::minimumNode()
{
return minimumNode(_Root);
}
template <typename T>
AVLTreeNode<T>* AVLTree<T>::minimumNode(AVLTreeNode<T>*& tree) {
AVLTreeNode<T>* temp = tree;
while (temp->_lchild)
{
temp= temp->_lchild;
}
return temp;
// 查找最大结点 template < typename T> AVLTreeNode<T>* AVLTree<T>::maxmumNode() {
return maxmumNode(_Root);
}
template < typename T>
AVLTreeNode<T>* AVLTree<T>::maxmumNode(AVLTreeNode<T>*& tree) {
AVLTreeNode<T>* temp=tree;
while (temp->_rchild)
{
temp= temp->_rchild;
}
return temp;
}
// 打印二叉树 template <typename T> void AVLTree<T>::print() {
print(_Root);
}
template <typename T>
void AVLTree<T>::print(AVLTreeNode<T>*& tree)
{
if (tree) // 如果 tree 不为空
{
if (tree->_lchild) // 结点有左孩子
cout<< "节点 " <<tree->_key<< " 有左孩子为 " <<tree->_lchild->_key<<endl;
if (tree->_rchild)
cout<< "节点 " <<tree->_key<< " 有右孩子为 " <<tree->_rchild->_key<<endl;
print(tree->_lchild); print(tree->_rchild);
}
}
// 销毁二叉树 template <typename T> void AVLTree<T>::destory()
{
destory(_Root);
}
template <typename T>
void AVLTree<T>::destory(AVLTreeNode<T>*& tree)
{
if (tree->_lchild!=NULL) destory(tree->_lchild);
if (tree->_rchild!=NULL) destory(tree->_rchild);
if (tree->_lchild==NULL&&tree->_rchild==NULL)
{
delete (tree);
tree = NULL;
}
}
// 插入函数 template <typename T> bool AVLTree<T>::insert(T key)
{
_taller= false ; return insert(_Root ,key,_taller);
} template <typename T> bool AVLTree<T>::insert(AVLTreeNode<T>*& tree,T e , bool &taller) {
if (!tree)
{
tree = new AVLTreeNode<T>(e ,NULL,NULL,0);
tree->_bf= EH;
tree->_lchild=tree->_rchild = NULL; taller = true ;
}
else
{
if (e==tree->_key) // 如果 e 已经存在
{
taller = false ; // 则树不长高
return false ;
}
if (e<tree->_key)
{
if (!insert(tree->_lchild,e,taller)) return false ;
if (taller)
{
{
switch (tree->_bf)
{
case LH: leftBalance(tree); taller = false ; break ;
case RH: rightBalance(tree); taller = false ; break ;
case EH: tree->_bf=LH; taller= true ; break ;
}
}
}
} else
{
if (!insert(tree->_rchild,e,taller)) return false
if (!insert(tree->_rchild,e,taller)) return false ;
if (taller)
{
switch (tree->_bf)
{
case LH: tree->_bf= EH; taller = false ; break ;
case RH: rightBalance(tree); taller = false ; break ;
case EH: tree->_bf=RH; taller = true ; break ;
}
}
} } return
} } return
true
// 左旋函数
template <typename T>
void AVLTree<T>::leftRotate(AVLTreeNode<T> *& tree) {
AVLTreeNode<T> * R = tree->_rchild; tree->_rchild= R->_lchild;
R->_lchild = tree; tree = R;
}
// 右旋函数
template <typename T>
void AVLTree<T>::rightRotate(AVLTreeNode<T> *& tree) {
AVLTreeNode<T> * L = tree->_lchild; tree->_lchild = L->_rchild;
L->_rchild= tree;
tree = L;
}
// 左平衡处理
template <typename T>
void AVLTree<T>::leftBalance(AVLTreeNode<T> *& tree) {
AVLTreeNode<T> * Lr; L =
AVLTreeNode<T> * Lr; L = tree->_lchild; switch (L->_bf) { case LH :
//L 指向 tree 的左孩子
// 检查左孩子的平衡度，并做相应的处理
// 新结点插入在左子树的左孩子上，需要做单右旋处理
tree->_bf = L->_bf = EH; rightRotate(tree); break ;
case RH: // 新结点插入在左子树的右孩子上，需要做先左后右旋转处理
Lr = L->_rchild; switch (Lr->_bf) {
case LH :
L->_bf = EH; tree->_bf= RH; break ;
case RH: tree->_bf= EH; L->_bf = LH; break ;
case EH:
tree->_bf=L->_bf = EH; break ;
} Lr->_bf = EH; leftRotate(tree->_lchild); rightRotate(tree);
}
}
// 右平衡处理 template <typename T> void AVLTree<T>::rightBalance(AVLTreeNode<T> *& tree) {
AVLTreeNode<T> *R; AVLTreeNode<T> *Rl;
R = tree->_rchild; switch (R->_bf)
{
case RH: // 新结点插入到右子树的右结点上，单纯做左旋处理。
tree ->_bf = EH;
R->_bf = EH; leftRotate(tree); break ;
case EH:
tree->_bf = RH; R->_bf = LH; leftRotate(tree); break ;
case LH: // 新结点插入到右子树的左结点上，做先右后左处理。
Rl=R->_lchild;
switch (Rl->_bf)
{
case LH: tree->_bf= EH; R->_bf = LH; break ;
case EH: tree->_bf=R->_bf = EH; break ;
case RH: tree->_bf=EH; R->_bf = RH;
break ;
}
Rl->_bf = EH; rightRotate(tree->_rchild); leftRotate(tree);
}
}
// 删除结点时左平衡操作 template <typename T> void AVLTree<T>::delLeftBalance(AVLTreeNode<T>*& tree , int childBf) {
if (tree->_lchild== NULL || childBf != EH&&tree->_lchild->_bf == EH)
{
switch (tree->_bf)
{
case LH: tree->_bf = EH; break ;
case RH: rightBalance(tree); break ;
case EH: tree->_bf = RH; break ;
}
}
}
// 删除结点时的右平衡操作 template <typename T> void AVLTree<T>::delRightBalance(AVLTreeNode<T>*&tree , int childBf) {
if (tree->_rchild == NULL || childBf!= EH&&tree->_rchild->_bf == EH)
{
switch (tree->_bf)
{ case LH:
leftBalance(tree); break ;
case RH : tree->_bf =EH; break ;
case EH:
tree->_bf =LH; break ;
}
}
}
程序测试
测试代码
// AVLTree.cpp :
定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include "AVLTree.h"
#define MAX 200
using namespace std;
int main()
{
srand( ( unsigned )time( NULL ) );
AVLTree<int > atree;
for (int i = 0;i<10;i++)
atree.insert(rand()%MAX);
cout<<
atree.print();
cout<<
atree.inOrder();
cout<<endl;
m ''**********
打印 AVL树********** <<endl；
中序遍历 AVL树*********” <<endl;
请输入查找的数： ************" <<endl；
int a ;
while (cin>>a)
{
if (atree.search(a))
cout<< " 查找成功 "<<endl;
else cout<< " 查找失败 "<<endl;
} cin.clear();
<<endl;cout<< "*********** 请输入要删除的树节点关键字 **********"
<<endl;
while (cin>>a) atree.remove(a);
"<<endl;cout<< " 删除后的结果为： atree.inOrder(); cout<<endl;
"<<endl;
atree.print();
cout<<endl;
}
cout<< "销毁二 AVL树"<<endl;
atree.destory();
cout<< " 销毁结果为： "<<endl;
atree.print();
system( "pause" );
}
测试结果
ITS 192*?******，畫输人要删醸拥对节点关漣字 強后的结臬为：4
ITS 192
*?******，畫输人要删醸拥对节点关漣字 強后的结臬为：
4 IBB 12fr 138 143 155 173 175 182
『|匚卩R]U ?址莫拥k范盟鼻hm
点灯0有右孩壬为3 4 点⑶有右舒加73 点3电有左孩■子刁眷
*
二
IJE!\VS 2010 projfct5^VL7rW\Dfbug\AVLtfm.e? 二 ||P |匠
1 fi 3 3 s- 5 2 0 7 4 4 7 5 9 5 113 1-11-—- CJ L^J L^lr J^r —.^J- i^J i^J 1却丿斗I#斗丿耳.'^"^^1~-\.斗/ 3T--于干干干干-于 14孩孩孩；^孩孩 2右右左右右右 12_^J l^r ^3 -^J -^J 6 6 & 3 3 J 5 8 2 2 0 7 7 4-7 JI 1- JI Jx t—I JI Jx 丄占告吿尸点占4点占”
Au眞.s 二纹任
Z “冃■:冃
巧6打有右孩壬加刘
巧邑打有右孩壬为1骂 讀;175着若雀丈为1翌g
I MMWMJIM.M.M ?| 序偏历R 1|时对**HE*******
:? 34 1QB 12b 139 143 155 173 175 182
.H.” U *Jl ■■■" K, HltK KJt WJLK JI.K K j?
点仙皇电樓壬划1芮 点萌晡芒营辛为銅 占蚀箱右遨壬为做 占诵有庁袴士光K3 点切錯右孩壬为肯5 点如有右孩子为15去
测试分析
程序代码使用rand（）随机函数随机产生值 0~200之间测试结点数据，一共是10个结点。
在上述测试中产生的10个节点值为：
27 34 100 126 138 143 155 173 175 182
结点的输入过程也是二叉平衡树的建立过程，打印查找描述岀插入操作完成后形成的二叉 树，依据打印描述可以得到一下二叉树结构：
（138 }
甜丿 173
(27 } [ 126 143 ) I； 175
\ 、 ￡
6100 j (155 ) ( 182
— —
中序遍历该树可以按从大到小的顺序输出结点：
27 34 100 126 138 143 155 173 175 182
查找平衡二叉树中的结点 27与34都查找成功。
删除结点：
删除结点27时，结点34的平衡因子由-1变成-2，故需要对结点34做平衡处理， 处理方法是使用34的直接前驱（没有）或直接后继（100）来代替34,删掉34的 直接后继100。删除操作完成后平衡二叉树如下图所示：
138 |
I
100 ( 173 )
34 I 126 [； 143 ) 175
155 182
同理的，删除结点138时，使用138的直接前驱（126）来代替138，同时从树中删除138的直 接前驱。删除结果如下图所示：
126
100 ) ( 173 )
34 143 ! 175 )
155 ) I 182
最后是销毁二叉树并打印岀销毁后的二叉树，可以看到销毁后二叉树已经没有内容可供打 印了。
思考与小结
平衡二叉树的难点就在于插入与删除时维护树的平衡度上，在插入上认清楚 LL、RR
LR RL四种旋转情况是关键，而在删除时要时刻抓住哪种结点的删除会导致树高度的减低 来进行分析。AVL的删除很多书基本没有提及，复杂的情况只能自己在纸上慢慢地画出来分 析出来，这个过程中也学到了很多东西。
采用C++来完成这次的实验，是想利用 C++面向对象提供的技术来完成 AVL这种数据结
构的封装。刚开始写AVLTree这个类时，对成员函数如何递归感到有点困惑， 一方面，如果
将类的成员数据暴露给类用户，则会破坏类的封装性，而如果成员函数参数不含数据成员又 无法完成递归。思考之后，才想到一个解决的办法：像类用户提供一个接口，该接口在类内 部实现上调用重载函数进行递归，这样就能解决上面问题。
实际上书里所描述的平衡二叉树准确的说应该是 AVL树，AVL树属于平衡二叉树的一种，
写AVL树的空余时间，我也同时了解了其他的平衡二叉树如红黑树等等， 它们都有各种适用
的场合，如红黑树常作为数据库文件索引的数据结构。
在我看来，学习数据结构应该要举一 反三，有相同作用、相似类型的数据结构应该在一起比较学习，这样能更好地掌握。
在测试程序的时候出了 BUG通过断点、变量监视等调试后发现是左平衡函数中左旋转
函数调用参数写错，算法设计经常会出现莫名其妙的错误，所要做的就是冷静调试了…