AVL平衡二叉树——数据结构

#include <iostream>
#define element int
using namespace std;

class AVLTreeNode
{
    private:
        element data;
        AVLTreeNode *lchild;
        AVLTreeNode *rchild;
        int height;
    public:
        AVLTreeNode(element data):lchild(NULL),rchild(NULL),data(data),height(1){}

        //树高
        int Height(AVLTreeNode *root)
        {
            if(root == NULL)return;
            return root->height;
        }

        //更新树高
        void updateHeight(AVLTreeNode *root)
        {
            if(root == NULL)return;
            root->height = max(Height(root->lchild),Height(root->rchild))+1;
        }

        //LL旋转
        AVLTreeNode* LL_Rotation(AVLTreeNode *&root)
        {
            AVLTreeNode *temp = root->lchild;
            root->lchild = temp->rchild;
            temp->rchild = root;
            updateHeight(root);
            updateHeight(temp);
            return temp;
        }

        //RR旋转
        AVLTreeNode* RR_Rotation(AVLTreeNode *&root)
        {
            AVLTreeNode *temp =root->rchild;
            root->rchild = temp->lchild;
            temp->lchild = root;
            updateHeight(root);
            updateHeight(temp);
            return temp;
        }

        //LR旋转
        AVLTreeNode* LR_Rotation(AVLTreeNode *&root)
        {
            root->lchild = RR_Rotation(root->lchild);
            return LL_Rotation(root);
        }

        //RL旋转
        AVLTreeNode* RL_Rotation(AVLTreeNode *&root)
        {
            root->rchild = LL_Rotation(root->rchild);
            return RR_Rotation(root);
        }

        //调节平衡
        void adjustBalance(AVLTreeNode *&root)
        {
            if(root == NULL)return;
            //如果左子树高判断是LL型还是LR型
            if(Height(root->lchild) - Height(root->rchild) > 1){
                //左子树的左子树高就是LL型否则就是LR型
                if(Height(root->lchild->lchild) >= Height(root->lchild->rchild))
                    root = LL_Rotation(root);
                else 
                    root = LR_Rotation(root);
            //如果右右子树高判断是RR型还是RL型
            }else if(Height(root->rchild) - Height(root->lchild) > 1){
                //右子树的右子树高就是RR型否则就是RL型
                if(Height(root->rchild->rchild) >= Height(root->rchild->lchild))
                    root = RR_Rotation(root);
                else 
                    root = RL_Rotation(root);
            }
        }

        //插入节点
        AVLTreeNode *Insert_Node(AVLTreeNode *&root,element data)
        {
            if(root == NULL){
                root = new AVLTreeNode(data);
                return root;
            }

            if(data == root->data) return root;
            if(data < root->data){
                root->lchild = Insert_Node(root->lchild,data);
            }else if(data > root->data){
                root->rchild = Insert_Node(root->rchild,data);
            }
            updateHeight(root);
            adjustBalance(root);
            return root;
        }

        //删除指定节点
        AVLTreeNode *Delete_Node(AVLTreeNode *&root)
        {
            //当前节点没有左右子树时(即叶节点)直接删除
            if(root->lchild==NULL&&root->rchild==NULL){
                AVLTreeNode *temp = root;
                delete root;
                temp = NULL;
                return temp;

            //当前节点没有左子树时，返回当前节点的右子树
            }else if(root->lchild == NULL && root->rchild != NULL){
                AVLTreeNode *temp = root->rchild;
                delete root;
                return temp;

            //当前节点没有右子树时，返回当前节点的左子树
            }else if(root->rchild == NULL && root->lchild != NULL){
                AVLTreeNode *temp = root->lchild;
                delete root;
                return temp;

            //当前节点(root)既有左子树又有右子树时，找到左子树中的最大值(又叫作直接前驱)(即左子树中最右边的值，所以他没有右子树)，将其右子树赋值为当前(即要删除节点）的右子树，然后删除当前节点(root)
            }else if(root->lchild != NULL && root->rchild != NULL){
                AVLTreeNode *cur=root->lchild;
                //找到root的直接前驱(左子树中最右端的值也就是最大值)
                while (cur!=NULL)
                {
                    cur=cur->rchild;
                }
                AVLTreeNode *temp = root->lchild;
                cur->rchild=root->rchild;
                delete root;
                return temp;       
            }
        }

        //根据输入值删除节点 
        AVLTreeNode *Delete_Node_Bydata(AVLTreeNode *&root,element data)
        {
            if(root == NULL)return NULL;
            //如果data大于root->data，则向右子树递归删除
            if(data < root->data){
                Delete_Node_Bydata(root->lchild,data);
            //如果data小于root->data，则向左子树递归删除
            }else if(data >root->data){
                Delete_Node_Bydata(root->rchild,data);
            }else{
                Delete_Node(root);
            }
            updateHeight(root);
            adjustBalance(root);
            return root;
        }

        //销毁AVL树(后序遍历销毁)
        void Destroy(AVLTreeNode *&root)
        {
            if(root->lchild != NULL){
                Destroy(root->lchild);
            }

            if(root->rchild != NULL){
                Destroy(root->rchild);
            }

            root = Delete_Node(root);
            return;
        }

        // 二叉树前序遍历
    void Preorder(AVLTreeNode *root)
    {
        if (root == NULL)
            return;
        cout << root->data << " ";
        Preorder(root->lchild);
        Preorder(root->rchild);
    }

    // 二叉树后序遍历
    void Postorder(AVLTreeNode *root)
    {
        if (root == NULL)
            return;
        Postorder(root->lchild);
        Postorder(root->rchild);
        cout << root->data << " ";
    }

    // 二叉树中序遍历
    void Inorder(AVLTreeNode *root)
    {
        if (root == NULL)
            return;
        Inorder(root->lchild);
        cout << root->data << " ";
        Inorder(root->rchild);
    }

    //显示AVL树
    void Show_AVLTree(AVLTreeNode   *&root)
    {
        if (root == NULL){
            cout << "空树" << endl;
            return;
        }
        cout<<"Preorder:";
        Preorder(root);
        cout << endl;
        cout<<"Inorder:";
        Inorder(root);
        cout << endl;
        cout<<"Postorder:";
        Postorder(root);
        cout << endl;
    }

};  

//写一个测试
//创建AVL树
void Create_AVLTree(AVLTreeNode *&root)
{
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        root = root->Insert_Node(root,x);
    }
    root->Show_AVLTree(root);
    return;
}

//删除测试
void Delete_Test(AVLTreeNode *&root)
{
    int x;
    while (1)
    {
        cin>>x;
        if(x==-1)break;
        root->Delete_Node_Bydata(root,x);
        root->Show_AVLTree(root);
    }
    
}


int main()
{
    AVLTreeNode *root = NULL;
    Create_AVLTree(root);
    Delete_Test(root);
    return 0;
}