#include <iostream>
using namespace std;
#define DataType int
/*
    定義AVL樹(shù)的結(jié)構(gòu)體，鏈?zhǔn)?
*/
typedef struct AvlNode{
    DataType    data;
    AvlNode    * m_pLeft;
    AvlNode    * m_pRight;
    int height;
}*AvlTree,*Position,AvlNode;
//求兩個(gè)數(shù)的最大值
int Max(int a,int b)
{
    return a>b?a:b;
}
//求樹(shù)的高度
int Height( AvlTree T)
{
    if(NULL == T)
        return -1;
    else
        return T->height;
}
//單旋轉(zhuǎn)右旋
AvlTree singleRotateWithRight(AvlTree T)
{
    AvlTree L = T->m_pLeft;
    T->m_pLeft = L->m_pRight;
    L->m_pRight = T;
    T->height = Max( Height(T->m_pLeft),Height(T->m_pRight) ) + 1;
    L->height = Max( Height(L->m_pLeft),Height(L->m_pRight) ) + 1;
    return L;    //此時(shí)L成為根節(jié)點(diǎn)了（可參考AVL的插入的左左情況的右旋圖）
}
//單旋轉(zhuǎn)左旋
AvlTree singleRotateWithLeft(AvlTree T)
{
    AvlTree R = T->m_pRight;
    T->m_pRight = R->m_pLeft;
    R->m_pLeft = T;
    T->height = Max( Height(T->m_pLeft),Height(T->m_pRight) ) + 1;
    R->height = Max( Height(R->m_pLeft),Height(R->m_pRight) ) + 1;
    return R;    //此時(shí)R成為根節(jié)點(diǎn)了（可參考AVL的插入的左左情況的左旋圖）
}
//雙旋轉(zhuǎn)，先左后右
AvlTree doubleRotateWithLeft(AvlTree T)        //先左后右
{
    T->m_pLeft = singleRotateWithLeft(T->m_pLeft);
    return singleRotateWithRight(T);
}
//雙旋轉(zhuǎn)，先右后左
AvlTree doubleRotateWithRight(AvlTree T)    //先右后左
{
    T->m_pRight = singleRotateWithRight(T->m_pRight);
    return singleRotateWithLeft(T);
}
AvlTree AvlTreeInsert(AvlTree T, DataType x)
{
    if(T == NULL)    //如果樹(shù)為空
    {
        T = (AvlNode *)malloc(sizeof(struct AvlNode));
        if(T)
        {
            T->data = x;
            T->m_pLeft    = NULL;
            T->m_pRight = NULL;
            T->height = 0;
        }
        else
        {
            cout << "空間不夠" << endl;
            exit(0);
        }
    }
    else if( x < T->data)        //如果插入到T結(jié)點(diǎn)的左子樹(shù)上
    {
        T->m_pLeft = AvlTreeInsert(T->m_pLeft,x);    //先插入，后旋轉(zhuǎn)
        if(Height(T->m_pLeft) - Height(T->m_pRight) == 2) //只有可能是這個(gè)
        {
            if(x < T->m_pLeft->data)        //左左情況，只需要右旋轉(zhuǎn)
            {
                T = singleRotateWithRight( T );
            }
            else                            //左右情況，雙旋轉(zhuǎn),先左
            {
                T = doubleRotateWithLeft( T );
            }
        }
    }
    else if( x > T->data )
    {
        T->m_pRight = AvlTreeInsert(T->m_pRight,x);
        if(Height(T->m_pRight) - Height(T->m_pLeft) == 2)
        {
            if(x > T->m_pRight->data)        //右右情況，進(jìn)行左旋
            {
                T = singleRotateWithLeft( T );
            }
            else                            //左右情況，雙旋轉(zhuǎn),先右
            {
                T = doubleRotateWithRight( T );
            }
        }
    }
    //如果這個(gè)數(shù)已經(jīng)存在，那么不進(jìn)行插入
    T->height = Max(Height(T->m_pLeft),Height(T->m_pRight)) + 1;
    return T;
}
//遞歸實(shí)現(xiàn)中序遍歷
void inOrderVisitUseRecur(const AvlTree pCurrent)
{
    if(pCurrent)
    {
        inOrderVisitUseRecur(pCurrent->m_pLeft);
        cout << pCurrent->data << " ";
        if(pCurrent->m_pLeft)
            cout << " leftChild: "<<pCurrent->m_pLeft->data;
        else
            cout << " leftChild: "<<"NULL" ;
        if(pCurrent->m_pRight)
            cout << " rightChild: "<<pCurrent->m_pRight->data;
        else
            cout << " rightChild: "<< "NULL";
        cout << endl;
        inOrderVisitUseRecur(pCurrent->m_pRight);
    }
}
int main()
{
    AvlTree root = NULL;
    root = AvlTreeInsert(root,1);
    root = AvlTreeInsert(root,2);
    root = AvlTreeInsert(root,3);
    root = AvlTreeInsert(root,4);
    root = AvlTreeInsert(root,5);
    root = AvlTreeInsert(root,6);
    root = AvlTreeInsert(root,7);
    root = AvlTreeInsert(root,8);
    root = AvlTreeInsert(root,9);
    root = AvlTreeInsert(root,10);
    root = AvlTreeInsert(root,11);
    root = AvlTreeInsert(root,12);
    root = AvlTreeInsert(root,13);
    root = AvlTreeInsert(root,14);
    root = AvlTreeInsert(root,15);
    inOrderVisitUseRecur(root);
    return 0;
}