代码：
#include<iostream>#include<cstdio>#include<cmath>#include<stdlib.h>#define Max(a,b) ((a)>(b)?(a):(b))using namespace std;struct Node{int value;Node* l;Node* r;int BF;//左子树高度 – 右子树高度void init(int v){value=v;l=NULL;r=NULL;BF=0;}};int Abs(int a){return a>=0?a:-a;}int getBF(Node* p){if(p == NULL)return -1;return p->BF;}bool isBalanced(Node* p){return Abs(getBF(p->l) – getBF(p->r)) < 2;}Node* LL(Node* p){Node* child = p->l;p->l = child->r;child->r = p;p->BF = Max(getBF(p->l),getBF(p->r)) + 1;child->BF = Max(getBF(child->l),getBF(child->r)) + 1;return child;}Node* RR(Node* p){Node* child = p->r;p->r= child->l;child->l = p;p->BF = Max(getBF(p->l),getBF(p->r)) + 1;child->BF = Max(getBF(child->l),getBF(child->r)) + 1;return child;}Node* LR(Node* p){Node* child = p->l;p->l = RR(child);return LL(p);}Node* RL(Node* p){Node* child = p->r;p->r =LL(child);return RR(p);}Node* Insert(Node* p,int x){if(p!=NULL){if(x>p->value)//R{p->r= Insert(p->r,x);if(!isBalanced(p)){if(x> p->r->value)//R-Rp = RR(p);else//R-Lp=RL(p);}}else//L{p->l= Insert(p->l,x);if(!isBalanced(p)){if(x > p->l->value)//L-Rp = LR(p);else//L-Lp = LL(p);}}}else{p=(Node*)malloc(sizeof(Node));(*p).init(x);}p->BF = Max(getBF(p->l),getBF(p->r)) + 1;return p;}/*void PrintTree(Node* root)//先序遍历AVL树{if(root != NULL){cout<<root->value<<"–";PrintTree(root->l);PrintTree(root->r);}}*/int main(){int n;while(scanf("%d",&n)==1){Node* root=NULL;int x;for(int i=0; i<n; i++){scanf("%d",&x);root=Insert(root,x);}printf("%d\n",root->value);//PrintTree(root);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
人之所以能，是相信能。
