平衡二叉树（c语言实现代码）

#pragma once
class CAVLTree
{
private:
    struct TreeNode
    {
        TreeNode(const int& nVal) :m_nVal(nVal) {}

        int m_nVal = 0;     //数据
        int m_hHeight = 1;  //叶子结点的高度
        TreeNode* m_pParent = nullptr; //父亲
        TreeNode* m_pLeft = nullptr;   //左孩子
        TreeNode* m_pRight = nullptr;  //右孩子
    }; 

public:
    CAVLTree();
    ~CAVLTree();

    void Insert(const int& nVal);  //插入

    //遍历
    void Layer();  //层序遍历
    void LDR();  //中序遍历
    void LDR_Loop();  //中序遍历
    void _LDR(TreeNode* pNode);  //中序遍历
    void DLR();   //前序遍历
    void DLR_Loop();   //前序遍历
    void LRD();   //后序遍历
    void LRD_Loop();   //后序遍历

public:
    void Delete(const int& nVal);
private:
    TreeNode* Find(const int& nVal);
    void DeleteNode(TreeNode* pNodeDel);

private:
    void AdjustHeight(TreeNode* pNode);
    int GetHeight(TreeNode* pNode);
    void RotateRight(TreeNode* pNode);
    void RotateLeft(TreeNode* pNode);
    TreeNode* m_pRoot = nullptr;    //根结点
};

#include "stdafx.h"
#include "AVLTree.h"
#include <queue>
#include <iostream>
#include <stack>
using namespace std;

CAVLTree::CAVLTree()
{
}


CAVLTree::~CAVLTree()
{
}

void CAVLTree::Insert(const int& nVal)
{
    //创建新结点
    TreeNode* pNewNode = new TreeNode(nVal);

    //空树
    if (m_pRoot == nullptr)
    {
        m_pRoot = pNewNode;
        return;
    }

    //插入新数据
    TreeNode* pNode = m_pRoot;
    do 
    {
        //如果值比结点的值小,则取结点的左孩子
        if (nVal < pNode->m_nVal)
        {
            //左孩子不存在,则新结点插入
            if (pNode->m_pLeft == nullptr)
            {
                pNode->m_pLeft = pNewNode;
                pNewNode->m_pParent = pNode;
                break;
            }
            //左孩子存在,继续比较
            else
            {
                pNode = pNode->m_pLeft;
            }
        }
        //如果值比结点的值大,则取结点的右孩子
        else if (nVal > pNode->m_nVal)
        {
            //如果右孩子不存在,则新结点插入
            if (pNode->m_pRight == nullptr)
            {
                pNode->m_pRight = pNewNode;
                pNewNode->m_pParent = pNode;
                break;
            }
            //继续比较
            else
            {
                pNode = pNode->m_pRight;
            }

        }
        //如果相等,则不插入.
        else
        {
            return;
        }

    } while (true);

    AdjustHeight(pNewNode);
}

/*
层序遍历: 一层一层遍历树

    8
 4     15
2  5 10  19

输出结果: 8 4 15 2 5 10 19 
*/
void CAVLTree::Layer()
{
    queue<TreeNode*> queNodes;
    queNodes.push(m_pRoot);

    while (!queNodes.empty())
    {
        //取队首的元素,
        TreeNode* pNode = queNodes.front(); 

        if (pNode == nullptr)
        {
            queNodes.pop();
            continue;
        }

        //左孩子和右孩子入队
        queNodes.push(pNode->m_pLeft);
        queNodes.push(pNode->m_pRight);

        //输出
        cout << pNode->m_nVal << " ";

        //结点出队
        queNodes.pop();
    }

    cout << endl;
}

/*
中序遍历:先左孩子,再自己,再右孩子
     8
  4     15
2  5   10  19

输出结果: 2 4 5 8 10 15 19
*/

void CAVLTree::LDR()
{
    _LDR(m_pRoot);

    cout << endl;
}


/*
中序遍历:先左孩子,再自己,再右孩子
     8
  4     15
2  5   10  19

输出结果: 2 4 5 8 10 15 19

栈:(底 --> 顶)     输出:
8 
8  4
8  4  2
8  4              2 
8  5              2  4
8                 2  4  5
15                2  4  5  8
15 10             2  4  5  8
15                2  4  5  8  10
19                2  4  5  8  10  15
                  2  4  5  8  10  15  19
*/
void CAVLTree::LDR_Loop()
{
    stack<TreeNode*> stkTmp;

    TreeNode* pNode = m_pRoot;
    while (true)
    {
        //结点入栈
        while (pNode != nullptr)
        {
            stkTmp.push(pNode);
            pNode = pNode->m_pLeft;
        }

        //栈为空,结束
        if (stkTmp.empty())
        {
            break;
        }

        //从栈顶取出元素,处理自己
        pNode = stkTmp.top();
        cout << pNode->m_nVal << " ";
        pNode = pNode->m_pRight;
        stkTmp.pop();
    }

    cout << endl;
}

void CAVLTree::_LDR(TreeNode* pNode)
{
    if (pNode == nullptr)
    {
        return;
    }

    _LDR(pNode->m_pLeft);
    cout << pNode->m_nVal << " ";
    _LDR(pNode->m_pRight);
}


/*
  前序遍历:先自己,再左孩子,再右孩子
  输出自己,右孩子入栈,处理左孩子
*/
void CAVLTree::DLR_Loop()
{
    stack<TreeNode*> stkTmp;
    TreeNode* pNode = m_pRoot;

    while (true)
    {
        //先处理自己
        while (pNode != nullptr)
        {
            cout << pNode->m_nVal << " ";
            stkTmp.push(pNode->m_pRight);
            pNode = pNode->m_pLeft;
        }

        //栈为空,处理完毕
        if (stkTmp.empty())
        {
            break;
        }

        //处理右孩子
        pNode = stkTmp.top();
        stkTmp.pop();
    }
    cout << endl;

}

/*
后序遍历:先左孩子,再右孩子,再自己
自己入栈, 处理左孩子,再右孩子入栈,再处理自己
*/

void CAVLTree::LRD_Loop()
{
    stack<TreeNode*> stkTmp;
    TreeNode* pNode = m_pRoot;
    TreeNode* pLastNode = nullptr;
    while (true)
    {
        while (pNode != nullptr)
        {
            stkTmp.push(pNode);
            pNode = pNode->m_pLeft;
        }

        //栈空则处理完毕
        if (stkTmp.empty())
        {
            break;
        }

        pNode = stkTmp.top();
        if (pNode->m_pRight == nullptr//叶子节点
            || pNode->m_pRight == pLastNode //上一次处理了此节点的右孩子
            ) 
        {
            cout << pNode->m_nVal << " ";
            pLastNode = pNode; 
            pNode = nullptr;
            stkTmp.pop();
        }
        else //上一次没有处理此节点的右孩子,所以此节点不处理,处理其右孩子
        {
            pNode = pNode->m_pRight;
        }
    }

    cout << endl;
}

CAVLTree::TreeNode* CAVLTree::Find(const int& nVal)
{
    TreeNode* pNode = m_pRoot;
    while (true)
    {
        if (pNode == nullptr)
        {
            return nullptr;
        }

        if (nVal == pNode->m_nVal)
        {
            return pNode;
        }
        else if (nVal > pNode->m_nVal)
        {
            pNode = pNode->m_pRight;
        }
        else
        {
            pNode = pNode->m_pLeft;
        }
    }

    return nullptr;
}

/*
删除的情况: 
  1. 叶子节点,直接删掉
  2. 只有左孩子
  3. 只有右孩子
  4. 有两个孩子,则在左子树中查找最大值的结点,
     将其拷贝到待删除节点,删除最大值节点
*/

void CAVLTree::Delete(const int& nVal)
{
    TreeNode* pNode = Find(nVal);
    DeleteNode(pNode);
}


/*
删除的情况:
1. 叶子节点,直接删掉
2. 只有左孩子
3. 只有右孩子
4. 有两个孩子,则在左子树中查找最大值的结点,
将其拷贝到待删除节点,删除最大值节点
*/
void CAVLTree::DeleteNode(TreeNode* pNodeDel)
{
    //没有左孩子和右孩子
    if (pNodeDel->m_pLeft == nullptr && pNodeDel->m_pRight == nullptr)
    {
        TreeNode* pParent = pNodeDel->m_pParent;
        if (pParent == nullptr)
        {
            m_pRoot = nullptr;
            delete pNodeDel;
            return;
        }

        //被删除结点是父结点的左孩子,父结点左孩子置空
        if (pParent->m_pLeft == pNodeDel)
        {
            pParent->m_pLeft = nullptr;
        }
        //被删除结点是父结点的右孩子,父结点右孩子置空
        else
        {
            pParent->m_pRight = nullptr;
        }
        delete pNodeDel;
        return;
    }

    //只有左孩子
    if (pNodeDel->m_pLeft != nullptr && pNodeDel->m_pRight == nullptr)
    {
        /* 删除B
             C                 C
           B          -->     A
          A

             C                C
               B      -->       A 
              A
        */
        TreeNode* pB = pNodeDel;
        TreeNode* pC = pB->m_pParent;
        TreeNode* pA = pB->m_pLeft;

        //删除结点为根结点
        if (pC == nullptr)
        {
            m_pRoot = pA;
            pA->m_pParent = nullptr;
            delete pB;
            return;
        }

        if (pB == pC->m_pLeft)
        {
            pC->m_pLeft = pA;
        }
        else
        {
            pC->m_pRight = pA;
        }
        pA->m_pParent = pC;
        delete pB;
        return;
    }

    //只有右孩子
    if (pNodeDel->m_pLeft == nullptr && pNodeDel->m_pRight != nullptr)
    {
        /* 删除B
         C                 C
          B          -->     A
           A

          C                C
        B      -->       A
          A
        */
        TreeNode* pB = pNodeDel;
        TreeNode* pC = pB->m_pParent;
        TreeNode* pA = pB->m_pRight;


        //删除结点为根结点
        if (pC == nullptr)
        {
            m_pRoot = pA;
            pA->m_pParent = nullptr;
            delete pB;
            return;
        }

        if (pB == pC->m_pRight)
        {
            pC->m_pRight = pA;
        }
        else
        {
            pC->m_pLeft = pA;
        }
        pA->m_pParent = pC;
        delete pB;
        return;
    }

    //同时有左孩子和右孩子
    //查找左子树中最大值的结点
    TreeNode* pMaxNode = pNodeDel->m_pLeft;
    while (pMaxNode->m_pRight != nullptr)
    {
        pMaxNode = pMaxNode->m_pRight;
    }
    pNodeDel->m_nVal = pMaxNode->m_nVal;
    DeleteNode(pMaxNode);
}

void CAVLTree::AdjustHeight(TreeNode* pNode)
{
    TreeNode* pCurNode = pNode;
    while (pCurNode != nullptr)
    {
        //取左孩子和右孩子高度最大的值,然后+1
        pCurNode->m_hHeight =
            std::max(GetHeight(pCurNode->m_pLeft), GetHeight(pCurNode->m_pRight)) + 1;

        
        if (GetHeight(pCurNode->m_pLeft) - GetHeight(pCurNode->m_pRight) > 1)
        {
            TreeNode* pB = pCurNode->m_pLeft;
            if (GetHeight(pB->m_pLeft) > GetHeight(pB->m_pRight))
            {
                /*   B的左孩子比右孩子高,对C右旋
                  C               B
                 B        -->    A  C
                A
                */
                RotateRight(pCurNode);
            }
            else
            {
                /*   B的右孩子比左孩子高,先对B进行左旋,再对C右旋
                  C               C              A
                B        -->     A      -->     B  C 
                  A            B  
                */
                RotateLeft(pB);
                RotateRight(pCurNode);
            }
        }
        else if (GetHeight(pCurNode->m_pRight) - GetHeight(pCurNode->m_pLeft) > 1)
        {
            TreeNode* pB = pCurNode->m_pRight;
            if (GetHeight(pB->m_pRight) > GetHeight(pB->m_pLeft))
            {
                /*   B的右孩子比左孩子高,对C左旋
                C                   B
                  B        -->    C   A
                    A
                */
                RotateLeft(pCurNode);
            }
            else
            {
                /*  B的左孩子比右孩子高,先对B进行右旋,再对C左旋
                C                    C               A
                    B        -->       A      -->   C   B
                  A                       B
                */
                RotateRight(pB);
                RotateLeft(pCurNode);
            }
        }



        //继续遍历父结点
        pCurNode = pCurNode->m_pParent;
    }
}

int CAVLTree::GetHeight(TreeNode* pNode)
{
    if (pNode == nullptr)
    {
        return 0;
    }
    return pNode->m_hHeight;
}

void CAVLTree::RotateRight(TreeNode* pNode)
{
    /*   C的左孩子与右孩子的高度差大于1, 向右旋转
       P                   P   
         C                   B
       B   k1      -->    A       C
     A   k2                    k2   k1
    */
    TreeNode* pP = pNode->m_pParent;
    TreeNode* pC = pNode;
    TreeNode* pB = pC->m_pLeft;
    TreeNode* pA = pB->m_pLeft;
    TreeNode* pK1 = pC->m_pRight;
    TreeNode* pK2 = pB->m_pRight;

    if (pP == nullptr)
    {
        //C是根结点
        m_pRoot = pB;
    }
    else
    {
        //C不是根结点
        if (pP->m_pLeft == pC)
        {
            pP->m_pLeft = pB;
        }
        else
        {
            pP->m_pRight = pB;
        }
    }

    pC->m_pParent = pB;
    pC->m_pLeft = pK2;

    pB->m_pParent = pP;
    pB->m_pRight = pC;

    if (pK2 != nullptr)
    {
        pK2->m_pParent = pC;
    }


    //修改高度
    pC->m_hHeight = max(GetHeight(pC->m_pLeft), GetHeight(pC->m_pRight)) + 1;
    pB->m_hHeight = max(GetHeight(pB->m_pLeft), GetHeight(pB->m_pRight)) + 1;
}

void CAVLTree::RotateLeft(TreeNode* pNode)
{
    /*   C的右孩子与做孩子的高度差大于1, 向右旋转
       P                       P
      C                       B
   k1   B        -->     C          A
      k2  A            k1  k2
    */
    TreeNode* pP = pNode->m_pParent;
    TreeNode* pC = pNode;
    TreeNode* pK1 = pC->m_pLeft;
    TreeNode* pB = pC->m_pRight;
    TreeNode* pK2 = pB->m_pLeft;
    TreeNode* pA = pB->m_pRight;

    pC->m_pRight = pK2;
    pC->m_pParent = pB;

    pB->m_pLeft = pC;
    pB->m_pParent = pP;

    if (pK2 != nullptr)
    {
        pK2->m_pParent = pC;
    }

    if (pP == nullptr)
    {
        m_pRoot = pB;
    }
    else
    {
        if (pP->m_pLeft == pC)
        {
            pP->m_pLeft = pB;
        }
        else
        {
            pP->m_pRight = pB;
        }
    }

    //修改高度
    pC->m_hHeight = max(GetHeight(pC->m_pLeft), GetHeight(pC->m_pRight)) + 1;
    pB->m_hHeight = max(GetHeight(pB->m_pLeft), GetHeight(pB->m_pRight)) + 1;
}