平衡二叉树

平衡二叉树：

template <class T>
class BBTree
{
public:
    //元素节点
    typedef struct _TREE_NODE
    {
        T nElement;            //数据
        _TREE_NODE* pLChild;     //左子树
        _TREE_NODE* pRChild;     //右子树
    }TREE_NODE, *PTREE_NODE;
    BBTree();
    ~BBTree();
public:
    bool AddData(T nData);   //添加元素
    bool DelData(T nData);   //删除元素
    void ClearTree();          //清空元素
    void TravsoualPre();       //前序遍历
    void TravsoualMid();       //中序遍历
    void TravsoualBack();      //后序遍历
    void LevelTravsoual();     //层序遍历
    int GetCount();            //获取元素个数
    bool empty();
private:
    bool AddData(PTREE_NODE& pTree, T nData);    //添加元素
    bool DelData(PTREE_NODE& pTree, T nData);    //删除元素
    int GetDeep(PTREE_NODE pTree);                 //获取深度
    void ClearTree(PTREE_NODE& pTree);             //清空元素
    PTREE_NODE GetMaxOfLeft(PTREE_NODE pTree);     //获取左子树中的最大值节点
    PTREE_NODE GetMinOfRight(PTREE_NODE pTree);    //获取又子树中的最小值节点
    void TravsoualPre(PTREE_NODE pTree);           //前序遍历
    void TravsoualMid(PTREE_NODE pTree);           //中序遍历
    void TravsoualBack(PTREE_NODE pTree);          //后序遍历
    //旋转操作
    void LeftWhirl(PTREE_NODE& pTree);       //左旋
    void RightWhirl(PTREE_NODE& pTree);      //右旋
    void LeftRightWhirl(PTREE_NODE& pTree);  //左右旋
    void RightLeftWhirl(PTREE_NODE& pTree);  //右左旋
private:
    PTREE_NODE m_pRoot;   //根节点
    int m_nCount;         //元素个数
};



template <class T>
BBTree<T>::BBTree() :m_pRoot(0), m_nCount(0){}
template <class T>
BBTree<T>::~BBTree(){}
//添加数据
template <class T>
bool BBTree<T>::AddData(T nData){
    return AddData(m_pRoot, nData);
}
//私有方法添加数据
template <class T>
bool BBTree<T>::AddData(PTREE_NODE& pTree, T nData){
    //pTree是否为空,如果为空说明有空位可以添加
    if (!pTree){
        pTree = new TREE_NODE{};
        pTree->nElement = nData;
        m_nCount++;
        return true;
    }
    //与根做对比，小的放在其左子树，否则放在右子树
    if (nData > pTree->nElement){
        AddData(pTree->pRChild, nData);
        //判断是否平衡
        if (GetDeep(pTree->pRChild) -GetDeep(pTree->pLChild) == 2){
            //判断如何旋转
            if (pTree->pRChild->pRChild){
                //左旋
                LeftWhirl(pTree);
            }
            else if (pTree->pRChild->pLChild){
                //右左旋
                RightLeftWhirl(pTree);
            }
        }
        return true;
    }
    if (nData < pTree->nElement){
        AddData(pTree->pLChild, nData);
        //判断是否平衡
        if (GetDeep(pTree->pLChild) -GetDeep(pTree->pRChild) == 2){
            //判断如何旋转
            if (pTree->pLChild->pLChild){
                //右旋
                RightWhirl(pTree);
            }
            else if (pTree->pLChild->pLChild){
                //左右旋
                LeftRightWhirl(pTree);
            }
        }
         return true;
    }
    return false;
}
//删除元素
template <class T>
bool BBTree<T>::DelData(T nData)
{
    return DelData(m_pRoot, nData);
}
//私有方法删除元素
template <class T>
bool BBTree<T>::DelData(PTREE_NODE& pTree, T nData){
    bool bRet = false;
    //判断是否为空树
    if (empty()){
        return false;
    }
    //开始遍历要删除的数据
    if (pTree->nElement == nData){
        //如果为叶子节点就删除，
        //不是则需要找代替
        if (!pTree->pLChild && !pTree->pRChild){
            delete pTree;
            pTree = nullptr;
            m_nCount--;
            return true;
        }
        //根据左右子树的深度查找要替换的节点
        if (GetDeep(pTree->pLChild) >=GetDeep(pTree->pRChild)){
            PTREE_NODE pMax = GetMaxOfLeft(pTree->pLChild);
            pTree->nElement = pMax->nElement;
            DelData(pTree->pLChild, pMax->nElement);
        }
        else{
            PTREE_NODE pMin = GetMinOfRight(pTree->pRChild);
            pTree->nElement = pMin->nElement;
            DelData(pTree->pRChild, pMin->nElement);
        }
    }
    else if (nData > pTree->nElement){
        bRet = DelData(pTree->pRChild, nData);
        //判断是否平衡
        if (GetDeep(pTree->pLChild) -GetDeep(pTree->pRChild) == 2){
            //判断如何旋转
            if (pTree->pLChild->pLChild){
                //右旋
                RightWhirl(pTree);
            }
            else if (pTree->pLChild->pLChild){
                //左右旋
                LeftRightWhirl(pTree);
            }
        }
    }
    else { /*if (nData < pTree->nElement)*/
        bRet = DelData(pTree->pLChild, nData);
        //判断是否平衡
        if (GetDeep(pTree->pRChild) -GetDeep(pTree->pLChild) == 2){
            //判断如何旋转
            if (pTree->pRChild->pRChild){
                //左旋
                LeftWhirl(pTree);
            }
            else if (pTree->pRChild->pLChild){
                //右左旋
                RightLeftWhirl(pTree);
            }
        }
    }
    return bRet;
}
//清空
template <class T>
void BBTree<T>::ClearTree(){
    ClearTree(m_pRoot);
    m_nCount = 0;
}
////私有方法清空
template <class T>
void BBTree<T>::ClearTree(PTREE_NODE& pTree){
    //从叶子节点开始删除
    //删除其左右子树后再删除根节点本身
    //判断是否为空树
    if (empty()){
        return;
    }
    //判断是否为叶子节点
    if (!pTree->pLChild && !pTree->pRChild){
        delete pTree;
        pTree = nullptr;
        return;
    }
    ClearTree(pTree->pLChild);
    ClearTree(pTree->pRChild);
    ClearTree(pTree);
}
//前序遍历
template <class T>
void BBTree<T>::TravsoualPre(){
    TravsoualPre(m_pRoot);
    cout << endl;
}
//私有方法前序遍历
template <class T>
void BBTree<T>::TravsoualPre(PTREE_NODE pTree){
    //递归的返回条件
    if (!pTree)
    {
        return;
    }
    //根左右
    cout << pTree->nElement << " ";
    TravsoualPre(pTree->pLChild);
    TravsoualPre(pTree->pRChild);
}
//中序遍历
template <class T>
void BBTree<T>::TravsoualMid(){
    TravsoualMid(m_pRoot);
    cout << endl;
}
//私有方法中序遍历
template <class T>
void BBTree<T>::TravsoualMid(PTREE_NODE pTree){
    //递归的返回条件
    if (!pTree){
        return;
    }
    //左根右
    TravsoualMid(pTree->pLChild);
    cout << pTree->nElement << " ";
    TravsoualMid(pTree->pRChild);
}
//后序遍历
template <class T>
void BBTree<T>::TravsoualBack(){
    TravsoualBack(m_pRoot);
    cout << endl;
}
//私有方法后序遍历
template <class T>
void BBTree<T>::TravsoualBack(PTREE_NODE pTree){
    //递归的返回条件
    if (!pTree){
        return;
    }
    //左右根
    TravsoualBack(pTree->pLChild);
    TravsoualBack(pTree->pRChild);
    cout << pTree->nElement << " ";
}
//层序遍历
template <class T>
void BBTree<T>::LevelTravsoual(){
    vector<PTREE_NODE> vecRoot;  //保存根节点
    vector<PTREE_NODE> vecChild; //保存根节点的子节点
    vecRoot.push_back(m_pRoot);
    while (vecRoot.size()){
        for (unsigned int i = 0; i < vecRoot.size(); i++){
            cout << vecRoot[i]->nElement << " ";
            //判断其是否左右子节点
            if (vecRoot[i]->pLChild){
                vecChild.push_back(vecRoot[i]->pLChild);
            }
            if (vecRoot[i]->pRChild){
                vecChild.push_back(vecRoot[i]->pRChild);
            }
        }
        vecRoot.clear();
        vecRoot = vecChild;
        vecChild.clear();
        cout << endl;
    }
}
//获取元素个数
template <class T>
int BBTree<T>::GetCount()
{
    return m_nCount;
}
//获取节点深度
template <class T>
int BBTree<T>::GetDeep(PTREE_NODE pTree){
    //判断pTree是否为空
    if (!pTree){
        return 0;
    }
    int nL = GetDeep(pTree->pLChild);
    int nR = GetDeep(pTree->pRChild);
    //比较左右子树的深度，取最大值加 1 返回
    return (nL >= nR ? nL : nR) + 1;
}
//获取左子树中的最大值
template <class T>
typename BBTree<T>::PTREE_NODE BBTree<T>::GetMaxOfLeft(PTREE_NODE pTree){
    //右子树中找更大的值
    //是否空
    if (!pTree){
        return 0;
    }
    //判断是否有右子树
    while (pTree->pRChild){
        pTree = pTree->pRChild;
    }
    //返回最大值节点
    return pTree;
}
//获取右子树中的最小值
template <class T>
typename BBTree<T>::PTREE_NODE BBTree<T>::GetMinOfRight(PTREE_NODE pTree){
    //左子树中找更小的值
    //是否空
    if (!pTree){
        return 0;
    }
    //判断是否有右子树
    while (pTree->pLChild){
        pTree = pTree->pLChild;
    }
    return pTree;
}
//左旋
template <class T>
void BBTree<T>::LeftWhirl(PTREE_NODE& pK2){
    /*
    k2                  k1
      k1   ==>       k2    N
    X   N              X
    */
    //保存k1
    PTREE_NODE pK1 = pK2->pRChild;
    //保存X
    pK2->pRChild = pK1->pLChild;
    //k2变成k1的左子树
    pK1->pLChild = pK2;
    //k1变成k2
    pK2 = pK1;
}
//右旋
template <class T>
void BBTree<T>::RightWhirl(PTREE_NODE& pK2){
    /*
    k2            k1
  k1     ==>    N    k2
N    X             X
    */
    //保存k1
    PTREE_NODE pK1 = pK2->pLChild;
    //保存X
    pK2->pLChild = pK1->pRChild;
    //k1的右子树为k2
    pK1->pRChild = pK2;
    //k2为k1
    pK2 = pK1;
}
//左右旋
template <class T>
void BBTree<T>::LeftRightWhirl(PTREE_NODE& pK2){
    /*
    k2               k2              N
    k1     左旋       N       右旋  K1   K2
    N             k1 [x]             [x]
    [x]
    */
    LeftWhirl(pK2->pLChild);
    RightWhirl(pK2);
}
//右左旋
template <class T>
void BBTree<T>::RightLeftWhirl(PTREE_NODE& pK2){
    /*
    k2               k2                   N
    k1    右旋       N     左旋    k2     K1
    N               [x]  k1           [x]
    [x]
    */
    RightWhirl(pK2->pRChild);
    LeftWhirl(pK2);
}
template <class T>
bool BBTree<T>::empty(){
    return m_pRoot == 0;
}
int main() {
    BBTree<int> tree;
    tree.AddData(1);
    tree.AddData(2);
    tree.AddData(3);
    tree.AddData(4);
    tree.AddData(5);
    tree.AddData(6);
    tree.AddData(7);
    tree.AddData(8);
    tree.AddData(9);
    tree.AddData(10);
    tree.LevelTravsoual();
    printf("==================\n");
    tree.DelData(4);
    tree.LevelTravsoual();
    printf("==================\n");
    tree.TravsoualPre();
    printf("==================\n");
    tree.TravsoualMid();
    printf("==================\n");
    tree.TravsoualBack();
    system("pause");
    return 0;
}