題意

給出N個正整數(shù)你虹，將他們依次插入一課初始為空的AVL樹上贯底，求插入后的根節(jié)點(diǎn)的值

思路

無論是LL,LR,RL,RR型休建，我們都可以看成把第二大的當(dāng)作子樹的根袍镀，最小的為它的左子樹岗屏，最大的為右子樹辆琅，這樣就可以方便的計算啦（具體過程可以參考鄧俊輝的《數(shù)據(jù)結(jié)構(gòu)》相關(guān)內(nèi)容漱办，強(qiáng)推！Ｍ裱獭Ｃ渚）

代碼

#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#define getFater( a)  (a->father)
#define getHeight(a) (a==NULL?0:a->height)
#define isRoot(a) (a->father == NULL)
using namespace std;

typedef struct NODE
{
    int value;
    NODE * father;
    int height;
    NODE * lchild, *rchild;
}NODE ,*TREE;
TREE t;
NODE * opt34(NODE *a, NODE* b, NODE *c, NODE *t1, NODE* t2, NODE*t3, NODE*t4);


//判斷是不是父節(jié)點(diǎn)的左子樹
bool isLchild(NODE *a) { return (!isRoot(a) && (a->father->lchild == a)); }
//獲取決定node的高度的那個子節(jié)點(diǎn)
NODE * getTallerChild(NODE * node) { return (((getHeight(node->lchild)) > (getHeight(node->rchild))) ? (node->lchild) : (node->rchild)); }


//更新高度
void updateHeight(NODE * node)
{
    node->height =  max(getHeight(node->lchild), getHeight(node->rchild))+1;
    
}

//插入
NODE * insert(NODE * &node,NODE * &father,int a)
{
    if (node == NULL)
    {
        node = new NODE;
        node->lchild = node->rchild = NULL;
        if (father != node)
            node->father = father;
        else
            node->father = NULL;
        node->height = 1;
        node->value = a;
        return node;
    }
    else
    {
        if (node->value < a)
             return insert(node->rchild, node, a);
        else
            return insert(node->lchild,node,a);
    }
    
}

//旋轉(zhuǎn)
NODE * rotateAT(NODE * a)
{
    NODE *b = a->father;
    NODE *c = b->father;
    if (isLchild(a))
    {
        if (isLchild(b))
        {
            b->father = c->father;
            return opt34(a, b, c, a->lchild, a->rchild, b->rchild, c->rchild);
        }
        else
        {
            a->father = c->father;
            return opt34(c, a, b, c->lchild, a->lchild, a->rchild, b->rchild);
        }
    }
    else
    {
        if (!(isLchild(b)))
        {
            b->father = c->father;
            return opt34(c, b, a, c->lchild, b->lchild, a->lchild, a->rchild);
        }
        else
        {
            a->father = c->father;
            return opt34(b, a, c, b->lchild, a->lchild, a->rchild, c->rchild);
        }
    }
}

//具體操作3+4
NODE * opt34(NODE *a,NODE* b,NODE *c,NODE *t1,NODE* t2,NODE*t3,NODE*t4)
{
    a->lchild = t1; if (t1 != NULL) t1->father = a;
    a->rchild = t2; if (t2 != NULL) t2->father = a;
    updateHeight(a);
    c->lchild = t3; if (t3 != NULL) t3->father = c;
    c->rchild = t4; if (t4 != NULL) t4->father = c;
    updateHeight(c);
    b->lchild = a; a->father = b;
    b->rchild = c; c->father = b;
    updateHeight(b);
    return b;
}

bool AvlBalanced(NODE * g)
{
    int height;
    height = getHeight(g->lchild)- getHeight(g->rchild);
    return (-2 < height)&&(height < 2);
}


//插入過程
void insertAVL(int x)
{
    NODE *temp = insert(t,t,x);
    for (NODE * g = getFater(temp);g!=NULL;g = getFater(g))
    {
               /*
              原來代碼這么寫，然后一直只有最后一個測試點(diǎn)過了隅很，并且出現(xiàn)段錯誤
              (isRoot(g) ? t : (isLchild(g) ? (g)->father->lchild : (g)->father->rchild)) =               rotateAT(getTallerChild(getTallerChild(g)));
              然后改為下文這么一串就對了
              */

        if (!AvlBalanced(g))//情愿代碼寫長一點(diǎn)撞牢，嗚嗚嗚
        {
            if (g == t)
            {
                t = rotateAT(getTallerChild(getTallerChild(g)));
            }
            else
            {
                if (g == g->father->lchild)
                {
                    g->father->lchild = rotateAT(getTallerChild(getTallerChild(g)));
                }
                else
                    g->father->rchild = rotateAT(getTallerChild(getTallerChild(g)));
            }
            
            break;
        }
        else
            updateHeight(g);
    }
    return ;
}

int main()
{
    t = NULL;
    int n;
    int value;
    int ore[25];
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&value);
        insertAVL(value);
    }
    printf("%d\n",t->value);
    system("pause");
    return 0;
}

后記

這一題的通過率超級高，然而我一開始還是只對了一個測試點(diǎn)叔营，并且測試點(diǎn)4和5出現(xiàn)段錯誤屋彪，現(xiàn)在還是不知道為什么，希望能夠靈光一現(xiàn)绒尊，然后解決畜挥，嘻嘻