04-树3. Root of AVL Tree.zip

#include <iostream> #include <stdlib.h> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ typedef struct AVLTree { int data; AVLTree *l; AVLTree *r; int height; AVLTree(int data):data(data),l(NULL),r(NULL),height(0){ }; }*pAVLTree; int getheight(pAVLTree p) { if(p==NULL) return 0; return p->height; } bool isBalanced(pAVLTree p) { return abs(getheight(p->l) - getheight(p->r))<2; } pAVLTree LL(pAVLTree p) { pAVLTree child = p->l; p->l=child->r; child->r=p; p->height=max(getheight(p->l), getheight(p->r))+1; child->height=max(getheight(child->l), p->height)+1; return child; } pAVLTree RR(pAVLTree p) { pAVLTree child = p->r; p->r=child->l; child->l=p; p->height=max(getheight(p->l), getheight(p->r))+1; child->height=max(getheight(child->r), p->height)+1; return child; } pAVLTree LR(pAVLTree p) { pAVLTree child=p->l; p->l=RR(child); return LL(p); } pAVLTree RL(pAVLTree p) { pAVLTree child=p->r; p->r=LL(child); return RR(p); } pAVLTree insertion(pAVLTree pt, int v)//insert a value { if(pt==NULL) { pt=(pAVLTree)malloc(sizeof(struct AVLTree)); pt->l=pt->r=NULL; pt->data=v; pt->height=0; } else if(v<pt->data)//l { pt->l=insertion(pt->l,v); if(!isBalanced(pt)) { if(v>pt->l->data)//LR { pt=LR(pt); } else//LL { pt=LL(pt); } } } else if(v>pt->data)//R { pt->r=insertion(pt->r,v); if(!isBalanced(pt)) { if(v>pt->r->data)//RR { pt=RR(pt); } else//RL { pt=RL(pt); } } } pt->height=max(getheight(pt->l), getheight(pt->r))+1; return pt; } int main(int argc, char** argv) { int N=0,tmp=0; int a[21]; pAVLTree root=(pAVLTree)malloc(sizeof(struct AVLTree)); root=NULL; cin>>N; for(int i=0; i<N; i++) { cin>>tmp; root=insertion(root,tmp); } cout<<root->data<<endl; return 0; }