数据结构实验之查找二：平衡二叉树

AC_Code
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 struct node{
 4     int data,d;
 5     struct node *l,*r;
 6 };
 7 
 8 int max(int x,int y){
 9     if( x>y ) return x;
10     else return y;
11 }
12 
13 int deep(struct node *root){
14     if(root==NULL){
15         return -1;
16     }
17     else return root->d;
18 }
19 
20 struct node *rr(struct node *root){
21     struct node *p;
22     p = root->r;
23     root->r = p->l;
24     p->l = root;
25     root->d = max(deep(root->l),deep(root->r))+1;
26     p->d = max(deep(p->l),deep(p->r))+1;
27     return p;
28 }
29 
30 struct node *ll(struct node *root){
31     struct node *p;
32     p = root->l;
33     root->l = p->r;
34     p->r = root;
35     root->d = max(deep(root->l),deep(root->r))+1;
36     p->d = max(deep(p->l),deep(p->r))+1;
37     return p;
38 }
39 
40 struct node *lr(struct node *root){
41     root->l = rr(root->l);
42     root = ll(root);
43     return root;
44 }
45 
46 struct node *rl(struct node *root){
47     root->r = ll(root->r);
48     root = rr(root);
49     return root;
50 }
51 
52 struct node *creat(int x, struct node *root){
53     if( root==NULL ){
54         root=(struct node *)malloc(sizeof(struct node));
55         root->d=0;
56         root->data=x;
57         root->l=NULL;
58         root->r=NULL;
59     }
60     else{
61         if( x<root->data ){
62             root->l=creat(x,root->l);
63             if( deep(root->l)-deep(root->r)>1 ){
64                 if( x<root->l->data){
65                     root=ll(root);
66                 }
67                 else root=lr(root);
68             }
69         }
70         else{
71             root->r=creat(x,root->r);
72             if( deep(root->r)-deep(root->l)>1){
73                 if( x>root->r->data ){
74                     root=rr(root);
75                 }
76                 else root=rl(root);
77             }
78         }
79     }
80     root->d=max(deep(root->l),deep(root->r))+1;
81     return root;
82 }
83 
84 int main()
85 {
86     int x,i,n;
87     scanf("%d",&n);
88     struct node *root;
89     root=NULL;
90 
91     for(i=1;i<=n;i++){
92         scanf("%d",&x);
93         root=creat(x,root);
94     }
95     printf("%d
", root->data);
96     return 0;
97 }