题意

给出N个正整数，将他们依次插入一课初始为空的AVL树上，求插入后的根节点的值

思路

无论是LL,LR,RL,RR型，我们都可以看成把第二大的当作子树的根，最小的为它的左子树，最大的为右子树，这样就可以方便的计算啦（具体过程可以参考邓俊辉的《数据结构》相关内容，强推！！！）

代码

#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);


//判断是不是父节点的左子树
bool isLchild(NODE *a) { return (!isRoot(a) && (a->father->lchild == a)); }
//获取决定node的高度的那个子节点
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);
    }
    
}

//旋转
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))
    {
               /*
              原来代码这么写，然后一直只有最后一个测试点过了，并且出现段错误
              (isRoot(g) ? t : (isLchild(g) ? (g)->father->lchild : (g)->father->rchild)) =               rotateAT(getTallerChild(getTallerChild(g)));
              然后改为下文这么一串就对了
              */

        if (!AvlBalanced(g))//情愿代码写长一点，呜呜呜
        {
            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;
}

后记

这一题的通过率超级高，然而我一开始还是只对了一个测试点，并且测试点4和5出现段错误，现在还是不知道为什么，希望能够灵光一现，然后解决，嘻嘻