平衡二叉树C++实现（萌新分享）

昨非 · 发表于 2020-7-7 10:47:13

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由昨非于 2020-8-8 10:56 编辑

初学编程，参考前辈指导完成，定有不足之处，敬请指出，初来乍到，请多关照。

测试效果图如下：

登录/注册后可看大图

代码清单及注释如下：

/*
Author：昨非
Date:2020.5.21
*/
#include <iostream>
#include <algorithm>
using namespace std;
//结点结构体
template<class T>
class BiNode
{
public:
T data;
BiNode <T>* lch;
BiNode <T>* rch;
int height; //节点高度，判断平衡关键
BiNode<T>(const T _data) : data(_data), lch(NULL), rch(NULL), height(0) {} //初始化
};
//平衡二叉树类
template<class T>
class AVLTree
{
public:
BiNode<T>* root;
AVLTree<T>() { root = NULL; } //默认构造
void CreateAVL(T a[], int n); //建树
void InsertAVL(BiNode<T>*& R, T key); //插入
BiNode<T>* SearchAVL(BiNode<T>* R, T key); //按值查找
BiNode<T>* DeleteAVL(BiNode<T>*& R, T key); //按值删除
void Inorder(BiNode<T>* R); //中序遍历检验
void printAVLTree(BiNode<T>* root, int height, ostream& out);//直观打印
~AVLTree<T>() //递归析构
{
Release(root);
cout << "平衡二叉树已销毁！(析构)" << endl;
}
private:
int GetHeight(BiNode<T>* t); //求结点的高度
BiNode<T>* LL(BiNode<T>* t); //单旋转左
BiNode<T>* RR(BiNode<T>* t); //单旋转右
BiNode<T>* LR(BiNode<T>* t); //双旋转右左
BiNode<T>* RL(BiNode<T>* t); //双旋转左右
void Release(BiNode<T>* R); //析构辅助函数
BiNode<T>* MinNode(BiNode<T>* t) const; //获取树中的最小值辅助判断
BiNode<T>* MaxNode(BiNode<T>* t) const; //获取树中的最大值辅助判断
};
//获取树中的最小值辅助判断
template<class T>
BiNode<T>* AVLTree<T>::MinNode(BiNode<T>* t) const
{
if (NULL == t)
{
return NULL;
}
while (NULL != t->lch)
{
t = t->lch;
}
return t;
}
//获取树中的最大值辅助判断
template<class T>
BiNode<T>* AVLTree<T>::MaxNode(BiNode<T>* t) const
{
if (NULL == t)
{
return NULL;
}
while (NULL != t->rch)
{
t = t->rch;
}
return t;
}
//获得结点高度辅助判断
template <class T>
int AVLTree<T>::GetHeight(BiNode<T>* t)
{
if (t == NULL)
return -1;
else
return t->height;
}
//建树：循环调用InsertAVL
template<class T>
void AVLTree<T>::CreateAVL(T a[], int n)
{
for (int i = 0; i < n; i++)
{
InsertAVL(root, a[i]);
}
cout << "平衡二叉树构造完成！" << endl;
}
//插入函数
template<class T>
void AVLTree<T>::InsertAVL(BiNode<T>*& R, T key)
{
if (R == NULL) //结点为空
{
R = new BiNode<T>(key);
}//判断当前结点应该插入根节点的左子树还是右子树
else if (key < R->data)
{
InsertAVL(R->lch, key);
//判断平衡情况
if ((GetHeight(R->lch) - GetHeight(R->rch)) > 1)//插入后失衡
{
if (key < R->lch->data)
{
R = RR(R);//左左的旋转
}
else
R = LR(R);//左右的旋转
}
}
else if (key > R->data)
{
InsertAVL(R->rch, key);
if ((GetHeight(R->rch) - GetHeight(R->lch)) > 1)// 右插后失衡
{
if (key < R->rch->data)
{
R = RL(R);//右左
}
else
R = LL(R); //右右
}
}
R->height = max(GetHeight(R->lch), GetHeight(R->rch)) + 1;
}
//按值查找
template<class T>
BiNode<T>* AVLTree<T>::SearchAVL(BiNode<T>* R, T key)
{
while (R != NULL)
{
if (key == R->data)
return R;
else if (key < R->data)
R = R->lch;
else
R = R->rch;
}
return NULL;
}
//删除给定值
template<class T>
BiNode<T>* AVLTree<T>::DeleteAVL(BiNode<T>*& R, T key)
{
if (NULL == R) //空
{
return NULL;
}
if (key < R->data)
{
R->lch = DeleteAVL(R->lch, key);
//相当于在右子树上插入节点
if (GetHeight(R->rch) - GetHeight(R->lch) == 2)
{
//相当于在右子树上插入左节点造成的失衡（情况四）
if (GetHeight(R->rch->lch) > GetHeight(R->rch->rch))
{
R = RL(R);//相当与插入的右左
}
else
{
R = RR(R);//相当于插入的右右
}
}
}
else if (key > R->data)
{
R->rch = DeleteAVL(R->rch, key);
if (GetHeight(R->lch) - GetHeight(R->rch) == 2)
{
//判断插入位置
if (GetHeight(R->lch->lch) > GetHeight(R->lch->rch))
R = LL(R);//左左
else
R = LR(R);
}
}
else
{
//1 当前节点是不是叶节点
//2 删除之后还要看看是否破坏了平衡性
if (NULL != R->lch && NULL != R->rch)
{
if (GetHeight(R->lch) > GetHeight(R->rch))//左边子树高度大
{
BiNode<T>* _MaxNode = MaxNode(R->lch);//获取左结点最大值
R->data = _MaxNode->data;
R->lch = DeleteAVL(R->lch, _MaxNode->data);
}
else
{
BiNode<T>* _MinNode = MinNode(R->rch);
R->data = _MinNode->data;
R->rch = DeleteAVL(R->rch, _MinNode->data);
}
}
else //只有一个为NULL
{
BiNode<T>* NowNode = R;
if (NULL != R->lch)
{
R = R->lch;
}
else if (NULL != R->rch)
{
R = R->rch;
}
else
{
R = NULL;// 当前节点是叶节点没有子节点
}
delete NowNode;
}
}
return R;//返回该结点
}
//左左插入导致的不平衡 ->顺时针
template <typename T>
BiNode<T>* AVLTree<T>::LL(BiNode<T>* t)
{
BiNode<T>* q = t->rch;
t->rch = q->lch;
q->lch = t;
t->height = max(GetHeight(t->lch), GetHeight(t->rch)) + 1;
q->height = max(GetHeight(q->lch), GetHeight(q->rch)) + 1;
return q;
}
//右右插入导致的不平衡 ->逆时针
template <typename T>
BiNode<T>* AVLTree<T>::RR(BiNode<T>* t)
{
BiNode<T>* q = t->lch;
t->lch = q->rch;
q->rch = t;
t->height = max(GetHeight(t->lch), GetHeight(t->rch)) + 1;
q->height = max(GetHeight(q->lch), GetHeight(q->rch)) + 1;
return q;
}
//插入点位于t的左儿子的右子树 ->先逆再顺
template <typename T>
BiNode<T>* AVLTree<T>::LR(BiNode<T>* t)
{
t->lch = LL(t->lch);
return RR(t);
}
//插入点位于t的右儿子的左子树 ->先顺再逆
template <typename T>
BiNode<T>* AVLTree<T>::RL(BiNode<T>* t)
{
t->rch = RR(t->rch);
return LL(t);
}
//中序遍历用以验证
template<class T>
void AVLTree<T>::Inorder(BiNode<T>* R)
{
if (R != NULL)
{
Inorder(R->lch);
cout << R->data << " ";
Inorder(R->rch);
}
}
//递归调用用以析构
template<class T>
void AVLTree<T>::Release(BiNode<T>* R)
{
if (R != NULL)
{
Release(R->lch);
Release(R->rch);
delete R;
}
}
//递归实现直观打印
template<class T>
void AVLTree<T>::printAVLTree(BiNode<T>* root, int height, ostream& out)
{
char branches[] = { " /\\<" }; //树枝
if (root != NULL)
{ //打印当前结点右子树，深度+1
printAVLTree(root->rch, height + 1, out); //递归
for (int i = 0; i < height; i++) out << "\t";//根据深度，右移
out << "(" << root->data << ")";
//打印树枝
out << branches[((root->lch != NULL) << 1) | (root->rch != NULL)];
out << endl;//换行，打印当前结点的左子树
printAVLTree(root->lch, height + 1, out); //递归
}
}
int main() //测试
{
int a[] = { 63, 90, 70, 55, 67, 42, 98 };//测试数据
AVLTree<int>avltree; //默认构造
avltree.CreateAVL(a, 7); //依据数组建树
cout << "当前测试数据，整型 { 63, 90, 70, 55, 67, 42, 98 }; " << endl;
cout << "查找测试数据：67" << endl << "插入测试数据：101" << endl << "测试删除数据：70" << endl;
cout << "**********************************************************" << endl;
cout << "原平衡二叉树中序遍历如下：";
avltree.Inorder(avltree.root);
cout << endl;
cout << "打印如下：" << endl;
avltree.printAVLTree(avltree.root, 0, cout);
cout << endl << endl;
cout << "***************************************************\n";
cout << " * │1.打印AVL树 2.插入给定值 │ *\n";
cout << " * │ │ *\n";
cout << " * │3.删除给定值 4.中序遍历检验 │ *\n";
cout << " * │ │ *\n";
cout << " * │5.查找给定值 6.退出程序 │ *\n";
cout << "***************************************************\n";
cout << endl;
BiNode<int>* p = avltree.SearchAVL(avltree.root, 67); //初始化查找指针，避免被case标签跳过
int select;
do
{
cout << "请选择操作方式 (1~6):" << endl;
cin >> select;
if (select > 6)
cout << "错误操作，请重新输入！"<<endl;
else
switch (select) {
case 1:
avltree.printAVLTree(avltree.root, 0, cout);
cout << endl << endl;
break;
case 2:
avltree.InsertAVL(avltree.root, 101);
cout << "插入成功!" << endl;
break;
case 3:
avltree.DeleteAVL(avltree.root, 70);
cout << "删除成功！" << endl;
break;
case 4:
cout << "中序遍历结果：";
avltree.Inorder(avltree.root);
cout << endl << endl;
break;
case 5:
cout << "查找AVL: ";
if (p != NULL)
cout << p->data << endl;
else
cout << "给定值未找到" << endl;
break;
case 6:
cout << "感谢使用！" << endl;
cout << "***********************************************************" << endl;
}
} while (select != 6);
return 0;
}

复制代码

（对于上次只付上bd网盘链接的情况深感抱歉）

my少年时代 · 发表于 2020-7-22 21:14:27

不错

昨非 · 发表于 2020-7-23 11:11:37

my少年时代发表于 2020-7-22 21:14
不错

谢谢大佬的鼓励

昨非 · 发表于 2020-8-8 10:47:30

之前只有一个链接确实很不礼貌，已将源码附上，希望对您有帮助

昨非 · 发表于 2020-8-8 13:10:32

新增效果图（刚学会贴网络图片）

开心小傻猪 · 发表于 2020-8-21 17:47:45

支持（但这不应该在数据结构板块吗？？？

）

发哥 · 发表于 2020-12-3 19:55:43

好家伙

hornwong · 发表于 2022-3-28 18:21:17

a1372245671 · 发表于 2022-3-28 18:53:37

账号		自动登录	找回密码
密码			立即注册

[技术交流] 平衡二叉树C++实现（萌新分享）

马上注册，结交更多好友，享用更多功能^_^

评分

评分

评分

评分

浏览过的版块