数据结构
实
验
报
告
实验名称：平衡二叉树
1.实验目的和内容
根据平衡二叉树的抽象数据类型的定义，使用二叉链表实现一个平衡二叉树。
二叉树的基本功能：
1、平衡二叉树的建立
2、平衡二叉树的查找
3、平衡二叉树的插入
4、平衡二叉树的删除
5、平衡二叉树的销毁
6、其他：自定义操作
编写测试main()函数测试平衡二叉树的正确性。
2. 程序分析
2.1 存储结构
struct node
{
int key; //值
int height; //这个结点的父节点在这枝最长路径上的结点个数
node *left; //左孩子指针
node *right; //右孩子指针
node(int k){ key = k; left = right = 0; height = 1; } //构造函数};
2.2 程序流程
2.3 关键算法分析（由于函数过多，在此只挑选部分重要函数）
算法1：void AVL_Tree::left_rotate(node *&x)
[1] 算法功能：对 R-R型进行调整
[2] 算法基本思想：将结点右孩子进行逆时针旋转
[3] 算法空间、时间复杂度分析：都为0（1）
[4] 代码逻辑
node *y = x->right; y为x的右孩子
x->right = y->left; 将y的左孩子赋给x的右孩子 y->left = x; x变为y的左孩子
fixheight(x); 修正x，y的height值
fixheight(y);
x = y; 使x的父节点指向y 算法2：void A VL_Tree::right_rotate(node *&x)
[1] 算法功能：对L-L型进行调整
[2] 算法基本思想：将左孩子进行顺时针旋转
[3] 算法空间、时间复杂度分析：都为0（1）
[4] 代码逻辑
node *y = x->left; //y为x的左孩子 x->left = y->right; y的右孩子赋给x的左孩子
y->right = x; x变为y的右孩子
fixheight(x); 修正x和y的height值
fixheight(y);
x = y; 使x的父节点指向y
算法3：node*& A VL_Tree::balance(node *&p)
[1] 算法功能：对给定结点进行平衡操作
[2] 算法基本思想：通过平衡因子判断属于哪种情况，再依照情况进行平衡
[3] 算法空间、时间复杂度分析：没有递归和循环，都为O（1）
[4] 代码逻辑
fixheight(p); //修正P的height值
if (bfactor(p) == 2) 平衡因子为2，为L-？型
if (bfactor(p->left) < 0) P的左孩子平衡因子<0时，为L-R型，执行left_rotate(p->left); 相关平衡操作，若>0，为L-L型。
right_rotate(p);
}
else if (bfactor(p) == -2) 平衡因子为2 ，为R-?型
{
if (bfactor(p->right)>0) P的右孩子平衡因子>0，为R-L型
right_rotate(p->right); 小于0时，为R-R型
left_rotate(p);
}
fixheight(p); 修正平衡后的P的height值
return p;
算法4：node* A VL_Tree::remove(node *&p, int k)
[1] 算法功能：删除给定key值的结点
[2] 算法基本思想：首先通过递归找到待删除结点，如果其没有右孩子，直接将其
删除，将其左孩子链上去。
若有右孩子，找到右枝中的最小结点代替待删除结
点，对改变后的结点进行平衡。
注意右孩子要删除其中的最小结点
[3] 算法空间、时间复杂度分析：有递归，递归次数最多为深度，时间复杂度0
（nlogn），空间复杂度0（logn）
[4] 代码逻辑
if (k < p->key) K小于根节点，在左枝中寻找p->left=remove(p->left, k); 递归
else if (k>p->key) K大于根节点，在右枝中寻找p->right=remove(p->right, k); 递归
else 找到待删除结点
{
node *q = p->left; q为删除结点的左孩子
node *r = p->right; p为删除结点右孩子
delete p;
if (!r) //没有右子树
return q; 直接将左孩子返回，相当于直接删除p node* min = findmin(r); //有右子树时，找到右枝中的最小值
min->right=removein(r); 使删除最小值后的右枝变为min的右枝
min->left = q; p的左孩子变为min的左孩子，相当于删除了p，
balance(min); 对min进行balance操作
return min;
}
balance(p); 每次递归完都对p进行平衡操作
return p;
算法5：void A VL_Tree::insert(node *&p, int k)
[1] 算法功能：一边插入结点一边进行平衡
[2] 算法基本思想：按照构建排序二叉树的方法插入结点，每插入一次后判断是否
需要平衡
[3] 算法空间、时间复杂度分析：插入节点寻找位置需要递归，时间复杂度O（logn）
空间复杂度O(logn)
[4] 代码逻辑
if (!p) 如果是插入第一个节点
p = new node(k); 直接构造一个结点
else if (k < p->key) 插入值小于根节点，在左枝中寻找
{
insert(p->left, k);
if (height(p->left) - height(p->right) == 2) p的平衡因子为2
{
if (k<p->left->key)
right_rotate(p); //LL型
else
left_right_rotate(p); //L-R型
}
}
else if (k>p->key) 寻找值大于根节点，在右枝中寻找{
insert(p->right, k);
if (height(p->left) - height(p->right) == -2) 平衡因子为-2
{
if (k > p->right->key)
left_rotate(p); R-R型
else
right_left_rotate(p); R-L型
}
}
else;
fixheight(p); 修正P的height值
算法6：node* A VL_Tree::findvalue(int key)
[1] 算法功能：查找key的位置
[2] 算法基本思想：根据排序二叉树的规则进项查找
[3] 算法空间时间复杂度分析：没有递归，时间复杂度0(logn)，空间复杂度O（1）
[4] 代码逻辑
node *r = root; 初始化r为根节点，进行移动查找
while (r != NULL)
{
if (key < r->key) 小于根节点，在左枝中寻找
r = r->left;
else if (key>r->key) 大于根节点，在后枝中寻找
r = r->right;
else return r;
}
throw "无此值";
2.4 其他
使用了结构类型和类的知识。
使用了STL中的算法，直接调用其寻找两个值中最小值的函数min，大大节约了时间
3.程序运行结果分析
程序运行没有问题。
编写了主函数进行了测试，测试结果正确
4.总结
4.1实验的难点和关键点
本实验的难点和关键点在于大量的递归函数以及删除结点这两个方面，递归函数一定要注意递归返回的值，而删除结点时一定要注意是属于哪种情况。
4.2心得体会
本次实验让我对递归函数有了更加深刻的理解，递归函数的难点在于递归返回，我们一定要深刻的理解递归。
递归可以使代码变得异常简洁，但是也可能带来一些问题，在编写递归的时候一定要仔细思考，注意返回值与跳出。
相信以后的编程我可以做的更好。