平衡二叉树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++实现（萌新分享）

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

评分

评分

评分

评分