用二叉链表作存储结构实平衡的二叉排序树

下午茶的芬芳

用二叉链表作存储结构实平衡的二叉排序树。
      1)用数列L，生成平衡的二叉排序树BT：当插入新元素之后，发现
当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平
衡的二叉排序树BT；
      2)计算平衡的二叉排序树BT的平均查找长度，输出结果。



真的不知道为什么代码编译不出来
求大神检查，真的十分感谢

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define LH 1
   
4. #define EH 0
   
5. #define RH -1
   
6. typedef struct BSTNode
   
7. {
   
8.         int key;
   
9.         int BF;
   
10.         struct BSTNode *lchild,*rchild;
    
11. }BSTNode,*BSTree;
    
12. 
    
13. BSTree ll_rotate(BSTree *p)//左左旋转
    
14. {
    
15.         BSTree *s,*g;
    
16.         *s=(*p)->lchild;
    
17.         *g=(*s)->lchild;
    
18.         (*p)->lchild=(*s)->rchild;
    
19.         (*s)->rchild=(*p);
    
20.         (*p)->BF=EH;
    
21.         (*s)->BF=EH;
    
22.         (*p)=*s;
    
23.         return (*p);
    
24. }
    
25. 
    
26. BSTree lr_rotate(BSTree *p)//左右旋转
    
27. {
    
28.         BSTree *s,*g;
    
29.         (*s)=(*p)->lchild;
    
30.         (*g)=(*s)->lchild;
    
31.         (*s)->rchild=(*g)->lchild;
    
32.         (*p)->lchild=(*g)->rchild;
    
33.         (*g)->lchild=(*s);
    
34.         (*g)->rchild=(*p);
    
35.         switch((*g)->BF)
    
36.         {
    
37.                 case LH:
    
38.                         (*p)->BF=RH;
    
39.                         (*s)->BF=EH;
    
40.                         (*g)->BF=EH;
    
41.                 case EH:
    
42.                         (*p)->BF=EH;
    
43.                         (*s)->BF=EH;
    
44.                         (*g)->BF=EH;
    
45.                 case RH:
    
46.                         (*p)->BF=EH;
    
47.                         (*s)->BF=LH;
    
48.                         (*g)->BF=EH;
    
49.         }
    
50.         (*p)=(*g);
    
51.         return (*p);
    
52. }
    
53. 
    
54. BSTree rl_rotate(BSTree *p)//右左旋转
    
55. {
    
56.         BSTree *s,*g;
    
57.         (*s)=(*p)->rchild;
    
58.         (*g)=(*p)->lchild;
    
59.         (*p)->rchild=(*g)->lchild;
    
60.         (*s)->lchild=(*g)->rchild;
    
61.         (*s)->lchild=(*p);
    
62.         (*g)->rchild=(*s);
    
63.         switch((*g)->BF)
    
64.         {
    
65.                 case LH:
    
66.                         (*p)->BF=EH;
    
67.                         (*s)->BF=RH;
    
68.                         (*g)->BF=EH;
    
69.                 case EH:
    
70.                         (*p)->BF=EH;
    
71.                         (*s)->BF=EH;
    
72.                         (*g)->BF=EH;
    
73.                 case RH:
    
74.                         (*p)->BF=LH;
    
75.                         (*s)->BF=EH;
    
76.                         (*g)->BF=EH;
    
77.         }
    
78.         (*p)=(*g);
    
79.         return (*p);
    
80. }
    
81. 
    
82. BSTree rr_rotate(BSTree *p)//右右旋转
    
83. {
    
84.         BSTree *s,*g;
    
85.         (*s)=(*p)->rchild;
    
86.         (*g)=(*s)->rchild;
    
87.         (*p)->rchild=(*s)->lchild;
    
88.         (*s)->lchild=(*p);
    
89.         (*p)->BF=EH;
    
90.         (*s)->BF=EH;
    
91.         (*p)=(*s);
    
92.         return (*p);
    
93. }
    
94. BSTree leftbalance(BSTree *p)//左平衡
    
95. {
    
96.         BSTree *s;
    
97.         (*s)=(*p)->lchild;
    
98.         switch((*s)->BF)
    
99.         {
    
100.                 case LH:
     
101.                         ll_rotate(p);
     
102.                         break;
     
103.                 case RH:
     
104.                         lr_rotate(p);
     
105.                         break;
     
106.         }
     
107. }
     
108. 
     
109. BSTree rightbalance(BSTree *p)//右平衡
     
110. {
     
111.         BSTree *s;
     
112.         (*s)=(*p)->rchild;
     
113.         switch((*s)->BF)
     
114.         {
     
115.                 case LH:
     
116.                         rl_rotate(p);
     
117.                         break;
     
118.                 case RH:
     
119.                         rr_rotate(p);
     
120.                         break;
     
121.         }
     
122. }
     
123. 
     
124. int compare(int x,int y)
     
125. {
     
126.         if(x==y)        return 0;
     
127.         else
     
128.                 if(x<y)        return -1;
     
129.                 else
     
130.                         return 1;
     
131. }
     
132. 
     
133. int InsertAVL(BSTree *T,char e,bool *taller)//插入结点后，数长高，则×taller置为true
     
134. {
     
135.         int tmp;
     
136.         if(!(*T))
     
137.         {
     
138.                 *T=(BSTree)malloc(sizeof(BSTNode));
     
139.                 (*T)->key=e;
     
140.                 (*T)->lchild=NULL;
     
141.                 (*T)->rchild=NULL;
     
142.                 *taller=true;
     
143.         }
     
144.         else
     
145.         {
     
146.                 tmp=compare(e,(*T)->key);
     
147.                 switch(tmp)
     
148.                 {
     
149.                         case 0:
     
150.                                 *taller=false;
     
151.                                 return 0;
     
152.                                 break;
     
153.                         case -1:
     
154.                                 if(!InsertAVL(&((*T)->lchild),e,taller))
     
155.                                         return 0;
     
156.                                 if(*taller)
     
157.                                 {
     
158.                                         switch((*T)->BF)
     
159.                                         {
     
160.                                                 case LH:
     
161.                                                         *T=leftbalance(T);
     
162.                                                         *taller=false;
     
163.                                                         break;
     
164.                                                 case EH:
     
165.                                                         (*T)->BF=LH;
     
166.                                                         *taller=true;
     
167.                                                         break;
     
168.                                                 case RH:
     
169.                                                         (*T)->BF=EH;
     
170.                                                         *taller=false;
     
171.                                                         break;
     
172.                                         }
     
173.                                 }
     
174.                                 break;
     
175.                         case 1:
     
176.                                 if(!InsertAVL(&((*T)->rchild),e,taller))
     
177.                                         return 0;
     
178.                                 if(*taller)
     
179.                                 {
     
180.                                         switch((*T)->BF)
     
181.                                         {
     
182.                                                 case LH:
     
183.                                                         (*T)->BF=EH;
     
184.                                                         *taller=false;
     
185.                                                         break;
     
186.                                                 case EH:
     
187.                                                         (*T)->BF=RH;
     
188.                                                         *taller=true;
     
189.                                                         break;
     
190.                                                 case RH:
     
191.                                                         *T=rightbalance(T);
     
192.                                                         *taller=false;
     
193.                                                         break;
     
194.                                         }
     
195.                                 }
     
196.                                 break;
     
197.                                
     
198.                 }
     
199.         }
     
200.         return 1;
     
201. }
     
202. int CalAveLength(BSTNode *rt,int *s,int *j,int i)
     
203. {
     
204.         if(rt)
     
205.         {
     
206.                 i++;
     
207.                 *s=*s+i;
     
208.                 if(CalAveLength(rt->rchild,s,j,i))
     
209.                 {
     
210.                         i--;
     
211.                         return i;
     
212.                 }
     
213.         }
     
214.         else
     
215.                 return 1;
     
216. }
     
217. bool Find(BSTree T,int key)
     
218. {
     
219.         if(!T)
     
220.                 return false;
     
221.         else if(T->key==key)
     
222.                 return true;
     
223.         else if(T->key<key)
     
224.                 return Find(T->rchild,key);
     
225.         else
     
226.                 return Find(T->lchild,key);
     
227. }
     
228. void Output(BSTree T)
     
229. {
     
230.         if(T)
     
231.         {
     
232.                  printf("%d",T->key);
     
233.                  if(T->lchild||T->rchild)
     
234.                 {
     
235.                         printf("(");
     
236.                            Output(T->lchild);
     
237.                            printf(",");
     
238.                            Output(T->rchild);
     
239.                            printf(")");
     
240.                   }
     
241.         }
     
242. }
     
243. int main(int argc,char *argv[])
     
244. {
     
245.         int i;
     
246.         int A[]={3,2,1,4,5,6,7,10,9,8};
     
247. 
     
248.         //int A[]={3,2,1};
     
249.         BSTree T=NULL;
     
250.         bool taller;
     
251.         for(i=0;i<sizeof(A)/sizeof(int);i++)
     
252.                 InsertAVL(&T,A[i],&taller);
     
253.         Output(T);
     
254.         printf("\n");
     
255.         if(Find(T,6))
     
256.                 printf("6 is find in the AVL tree!\n");
     
257.         else
     
258.                 printf("6 is not find in the AVL tree!\n");
     
259.         int len,j=0,s=0;
     
260.         len=CalAveLength(T,&s,&j,i);
     
261.         printf("二叉排序树查找成功的平均查找长度为：%d",len);
     
262.         return 0;
     
263. }
     

复制代码

robinmu

报什么错？

下午茶的芬芳

robinmu 发表于 2016-11-10 09:48
报什么错？

编译成功，然而运行不能正确的显示平衡二叉树