（要熟练！）
输入一个结点序列，按照这个序列输入，每插入一次都自动调整为平衡二叉搜索树AVL。求最终形成的AVL树根的值。 在AVL树中，任何节点的两个子子树的高度最多相差一个；如果在任何时候它们相差多于一个，则重新平衡以恢复此属性。
熟练掌握建立AVL的代码即可。
在判断子结点平衡因子的时候，为1和为-1两个if必须是互斥的。一开始没写else，会出现进入第一个if后平衡因子的值改变了又进入第二个if的情况。 debug了一早上，一直以为是别的问题，没注意到这个细节...但发现可以不必在结构体中保存每个结点的高度，需要判断的时候每次递归求解即可。 建立树的过程还不够熟练，一定要多多再写几遍。
最后附上一个按照算法笔记上写的（在节点中加入了参数height表示该结点的高度）代码
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <cstdio> #include <vector> #include <map> #include<algorithm> #include<queue> using namespace std; struct node { int key; node* lchild, * rchild; int height; }; int getheight(node* p) { if (p == NULL)return 0; return p->height; } int balance(node* root) { return getheight(root->lchild) - getheight(root->rchild); } void updateheight(node* root) { root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1; } void R(node*& root) { node* newroot = root->lchild; root->lchild = newroot->rchild; newroot->rchild = root; updateheight(root);//记得更新高度！而且这里必须先更新root（因为它现在是newroot孩子）! updateheight(newroot); root = newroot; } void L(node*& root) { node* newroot = root->rchild; root->rchild = newroot->lchild; newroot->lchild = root; updateheight(root);//记得更新高度！ updateheight(newroot); root = newroot; } void insert(node*& root, int number) { if (root == NULL) { root = new node;//注意细节 root->height = 1; root->key = number; root->lchild = root->rchild = NULL; return; } if (number <= root->key) { insert(root->lchild, number); updateheight(root); if (balance(root) == 2) { if (balance(root->lchild) == 1)R(root); else if (balance(root->lchild) == -1) { L(root->lchild); R(root); } } } else { insert(root->rchild, number); updateheight(root); if (balance(root) == -2) { if (balance(root->rchild) == -1)L(root); else if (balance(root->rchild) == 1) { R(root->rchild); L(root); } } } } int main() { int i, n; scanf("%d", &n); int number; node* root = NULL; for (i = 0;i < n;i++) { scanf("%d", &number); insert(root, number); } printf("%d", root->key); return 0; }