1、<p><b>　　一．題目與要求</b></p><p><b>　　問(wèn)題提出</b></p><p>　　編寫(xiě)已個(gè)平衡二叉樹(shù)，主要是對(duì)插入一個(gè)元素導(dǎo)致樹(shù)不平衡的情況進(jìn)處平衡化處理以及相關(guān)的處理。</p><p><b>　　本系統(tǒng)涉及的知識(shí)點(diǎn)</b></p><p&g

2、t;　　隊(duì)列的插入，刪除，二叉樹(shù)的建立于銷(xiāo)毀，平衡樹(shù)的平衡化，以及C語(yǔ)言中基礎(chǔ)應(yīng)用于結(jié)構(gòu)等。</p><p><b>　　功能要求</b></p><p>　　(1).通過(guò)不斷插入的方式創(chuàng)建一棵平衡二叉樹(shù)，包括輸入結(jié)點(diǎn)的關(guān)鍵字和相關(guān) 信息。</p><p>　　(2)按要求輸出創(chuàng)建的平衡二叉樹(shù)結(jié)點(diǎn)，包括 順序（中序）輸出和按

3、層次輸出。</p><p>　　(3)插入新增的結(jié)點(diǎn)，若結(jié)點(diǎn)不存在則插入平衡二叉樹(shù)，并進(jìn)行相關(guān)調(diào)整。</p><p><b>　　(4)銷(xiāo)毀二叉樹(shù)。</b></p><p><b>　　(5)退出 </b></p><p><b>　　二．功能設(shè)計(jì)</b></p

4、><p><b>　　1.數(shù)據(jù)結(jié)構(gòu)的定義</b></p><p>　　typedef struct ElemType{</p><p>　　KeyType Key; //鍵值類(lèi)型</p><p>　　char info[20];</p><p>　　}ElemT

5、ype;</p><p>　　Typedef struct BSTNode{</p><p>　　ElemType data； </p><p>　　int bf ; //結(jié)點(diǎn)的平衡因子</p><p>　　struct BSTNode *lchild，*rch

6、ild；//左右孩子指針</p><p>　　}BSTNode，*BSTree；</p><p><b>　　模塊圖 </b></p><p><b>　　1.主程序的流程</b></p><p>　　2.各模塊之間的層次調(diào)用 </p

7、><p><b>　　程序代碼設(shè)計(jì)</b></p><p><b>　　1.調(diào)平二叉樹(shù)</b></p><p>　　if(插入元素與當(dāng)前根元素相等) </p><p><b>　　{ </b></p><p>　　printf

8、("已存在相同關(guān)鍵字的結(jié)點(diǎn)\n"); </p><p><b>　　}</b></p><p>　　if(插入元素小于當(dāng)前根元素)) </p><p><b>　　{</b></p><p>　　if(插入新結(jié)點(diǎn)不成功)</p><p>&l

9、t;b>　　return 0;</b></p><p>　　if(插入成功) </p><p>　　switch(查看根的平衡因子) </p><p><b>　　{</b></p><p><b>　　case +1: </b></p&

10、gt;<p><b>　　進(jìn)行左平衡處理;</b></p><p><b>　　{</b></p><p>　　檢查*T的左子樹(shù)的平衡度，并作相應(yīng)平衡處理</p><p><b>　　{</b></p><p>　　case +1: </p>

11、;<p>　　令根及其左孩子的平衡因子為0;</p><p><b>　　做右平衡處理;</b></p><p><b>　　{</b></p><p>　　BTree lc; </p><p>　　lc指向的結(jié)點(diǎn)左子樹(shù)根結(jié)點(diǎn);</p><p

12、>　　rc的右子樹(shù)掛接為結(jié)點(diǎn)的左子樹(shù);</p><p>　　lc的右孩子為原結(jié)點(diǎn); </p><p>　　原結(jié)點(diǎn)指向新的結(jié)點(diǎn)lc;</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case -1:

13、 </p><p>　　rd指向*T的左孩子的右子樹(shù)根</p><p>　　switch(查看右孩子平衡因子) </p><p><b>　　{</b></p><p><b>　　case +1:</b></p><p>　　根的平衡因子為-1;&

14、lt;/p><p>　　根左孩子的平衡因子為0; </p><p><b>　　break;</b></p><p><b>　　case 0:</b></p><p>　　令根和根左孩子的平衡因子為0;</p><p><b>　　break;</b>&l

15、t;/p><p><b>　　case -1:</b></p><p><b>　　根平衡因子為0;</b></p><p>　　根左孩子平衡因子為1; </p><p><b>　　break;</b></p><p><b>　　}</b

16、></p><p>　　根右孩子的平衡因子為0;</p><p>　　對(duì)*T的左子樹(shù)作左旋平衡處理;</p><p>　　對(duì)*T作右旋平衡處理;</p><p><b>　　}</b></p><p><b>　　break;</b></p><p&

17、gt;　　case 0: </p><p>　　令根的平衡因子為+1;</p><p><b>　　break;</b></p><p>　　case -1: </p><p>　　令根的平衡因子為-1;</p><p><b>　　break;</b

18、></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　2.輸出：</b></p><p><b>　?。?）中序輸出</b></p><p>　　采用遞歸算法對(duì)二叉

19、樹(shù)進(jìn)行遍歷。</p><p><b>　　if（結(jié)點(diǎn)不為空）</b></p><p><b>　　{</b></p><p>　　If(遍歷左孩子成功）</p><p>　　If（遍歷結(jié)點(diǎn)成功）</p><p>　　If（遍歷右孩子成功）</p><p&g

20、t;<b>　　返回 真</b></p><p><b>　　返回假</b></p><p><b>　　}</b></p><p>　　else（結(jié)點(diǎn)為空）</p><p><b>　　返回假</b></p><p><b&

21、gt;　　(2)按層次輸出</b></p><p>　　根據(jù)隊(duì)列先進(jìn)先出的特點(diǎn)，先將第一層結(jié)點(diǎn)進(jìn)隊(duì)a，對(duì)其出出隊(duì)并輸出，同時(shí)將其不為空的孩子指針入另一隊(duì)列b，當(dāng)a為空時(shí)，隊(duì)b進(jìn)行出對(duì)并輸出處理，將結(jié)點(diǎn)的不為空的左右孩子入隊(duì)a，直到b 為空............如此直到兩隊(duì)均為空。</p><p><b>　　根節(jié)點(diǎn)入隊(duì)；</b></p>&

22、lt;p>　　While（a，b不同時(shí)為空）</p><p><b>　　{</b></p><p><b>　　If（i為奇數(shù)）</b></p><p><b>　　{</b></p><p>　　While（a隊(duì)不空）</p><p><

23、b>　　{</b></p><p>　　a中結(jié)點(diǎn)出隊(duì)并輸出；</p><p><b>　　If（左孩子不空）</b></p><p><b>　　左孩子入隊(duì)b；</b></p><p><b>　　If(有孩子不空）</b></p><p&

24、gt;<b>　　右孩子入隊(duì)b；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　If（i為偶數(shù)）</b></p><p><b>　　{</b></p>

25、<p>　　While（b隊(duì)不空）</p><p><b>　　{</b></p><p>　　b中結(jié)點(diǎn)出隊(duì)并輸出；</p><p><b>　　If（左孩子不空）</b></p><p><b>　　左孩子入隊(duì)a；</b></p><p>

26、;<b>　　If(有孩子不空）</b></p><p><b>　　右孩子入隊(duì)a；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　I++;// 同時(shí)記錄樹(shù)的深度&

27、lt;/p><p><b>　　}</b></p><p><b>　　3.銷(xiāo)毀二叉樹(shù)</b></p><p>　　銷(xiāo)毀二叉樹(shù)的算法根據(jù)遞歸遍歷而來(lái)，算法大體相識(shí)。</p><p><b>　　If(根節(jié)點(diǎn)不空）</b></p><p><b>　

28、　{</b></p><p><b>　　If（左子樹(shù)不空）</b></p><p><b>　　銷(xiāo)毀左子樹(shù)；</b></p><p><b>　　If（右子樹(shù)不空）</b></p><p><b>　　銷(xiāo)毀右子樹(shù)；</b></p>

29、<p><b>　　銷(xiāo)毀相對(duì)根節(jié)點(diǎn)；</b></p><p>　　根節(jié)點(diǎn)賦空；//留下來(lái)以便再次創(chuàng)建二叉樹(shù)時(shí)使用</p><p><b>　　}</b></p><p><b>　　4.退出</b></p><p>　　退出時(shí)詢問(wèn)是否確認(rèn)退出，確認(rèn)則退出，否則返回

30、到主菜單</p><p><b>　　調(diào)試分析</b></p><p><b>　　遇到的問(wèn)題：</b></p><p>　　1）對(duì)平衡二叉樹(shù)的刪除的算法設(shè)計(jì)程序存在很大問(wèn)題。刪除節(jié)點(diǎn)后需要對(duì)新的排序樹(shù)平衡化，改變節(jié)點(diǎn)的信息，使之形成一棵新的平衡二叉樹(shù)。</p><p>　?。?）主函數(shù)中的實(shí)參和子

31、函數(shù)中的實(shí)參相等，造成調(diào)用該子函數(shù)時(shí)，雖然沒(méi)有錯(cuò)誤，但其功能不能正確的實(shí)現(xiàn)。改變?cè)撟兞亢蟪绦虺晒?shí)現(xiàn)各種功能。</p><p>　?。?）一些邏輯邏輯運(yùn)算符書(shū)寫(xiě)不正確，造成實(shí)現(xiàn)的功能不正確或程序死循環(huán)。</p><p><b>　　2.用戶手冊(cè)</b></p><p>　　1.了解程序清單上給出的功能，并根據(jù)提示依次進(jìn)行操作。</p>

32、;<p>　　2.創(chuàng)建二叉樹(shù)，輸入的數(shù)據(jù)元素為整數(shù)，當(dāng)輸入-123時(shí)，停止創(chuàng)建。并顯示平衡二叉樹(shù)的中序凹入樹(shù)形圖。</p><p>　　3.查找（輸入你要查找的元素）。</p><p>　　4.插入（輸入要插入的數(shù)據(jù)元素，并輸出）</p><p>　　5.刪除（刪除指定的元素，并輸出）</p><p><b>　　6.

33、結(jié)束</b></p><p>　　說(shuō)明：其中每一個(gè)功能實(shí)現(xiàn)后都會(huì)提示是否繼續(xù)：選擇y繼續(xù)，否則，終止。</p><p><b>　　3.測(cè)試過(guò)程</b></p><p>　　1.創(chuàng)建平衡二叉樹(shù)：（中序凹入輸出）</p><p><b>　　2.查找</b></p><

34、p><b>　　查找成功或失敗時(shí)：</b></p><p><b>　　3.插入</b></p><p><b>　　4.刪除,結(jié)束</b></p><p><b>　　五．課程設(shè)計(jì)總結(jié)</b></p><p>　　由于指針處理不當(dāng)，調(diào)試過(guò)程中經(jīng)常出

35、現(xiàn)指針出錯(cuò)的情況，導(dǎo)致程序終止，經(jīng)過(guò)仔細(xì)修改后才得以改正。在程序整體設(shè)計(jì)過(guò)程中，由于忽視&的作用而導(dǎo)致程序無(wú)法正常運(yùn)行。通過(guò)此次課程設(shè)計(jì)，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)的重要學(xué)習(xí)內(nèi)容有了更加深刻的了解，同時(shí)也意識(shí)到自己還存在很大的不足，還有很多的知識(shí)需要完善。在編程的過(guò)程中錯(cuò)誤時(shí)在所難免的，處了要修改錯(cuò)誤外還有了解錯(cuò)誤的原因。而不是僅僅修改而已。</p><p><b>　　六．參考文獻(xiàn)</b>&l

36、t;/p><p>　　[1] 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 嚴(yán)蔚寬 吳偉民 編著</p><p>　　[2] C語(yǔ)程序設(shè)計(jì) 白燕 尹業(yè)安 編著</p><p><b>　　七.附錄：程序清單</b></p><p>　　#include<stdio.h></p><p>　　#include&l

37、t;stdlib.h></p><p>　　#define ERROR 0</p><p>　　#define TRUE 1</p><p>　　#define OK 1</p><p>　　#define FALSE 0</p><p>　　#define LH 1</p><p>　　

38、#define RH -1</p><p>　　#define EH 0</p><p>　　#define EQ(a,b) ((a)==(b))</p><p>　　#define LT(a,b) ((a)<(b))</p><p>　　#define LQ(a,b) ((a)<=(b))</p><p>

39、;　　typedef int KeyType;</p><p>　　typedef struct ElemType</p><p><b>　　{</b></p><p>　　KeyType Key;</p><p>　　char info[20];</p><p>　　}ElemType;<

40、;/p><p>　　typedef struct BSTNode</p><p><b>　　{</b></p><p>　　ElemType data;</p><p><b>　　int bf;</b></p><p>　　struct BSTNode *lchild,

41、*rchild;</p><p>　　}BSTNode,*BSTree;</p><p>　　typedef struct QNode</p><p><b>　　{</b></p><p><b>　　BSTree e;</b></p><p>　　struct QNode

42、 *next;</p><p>　　}QNode,*QNodeP;</p><p>　　typedef struct </p><p><b>　　{ </b></p><p>　　QNodeP front;</p><p>　　QNodeP rear;</p><p>　

43、　}LinkQueue;</p><p>　　void CreatBalanceTree(BSTree &T);</p><p>　　void R_Rotate(BSTree &p);</p><p>　　void L_Rotate(BSTree &p);</p><p>　　int InsertAVL(BSTree

44、&T,ElemType e);</p><p>　　void LeftBalance(BSTree &T);</p><p>　　void RightBalance(BSTree &T);</p><p>　　int Print_Mid(BSTree T);</p><p>　　int Visit(BSTree T);

45、</p><p>　　int WideTraverse(BSTree T);</p><p>　　void Destory(BSTree &T);</p><p>　　int flag=0;</p><p>　　bool taller;</p><p>　　int number;//計(jì)數(shù)變量</p&g

46、t;<p>　　void main()</p><p><b>　　{</b></p><p>　　BSTree T=NULL;</p><p>　　int chose;</p><p>　　ElemType e;</p><p>　　printf("\n=======平衡

47、二叉樹(shù)=======\n");</p><p><b>　　do{</b></p><p>　　printf("||功能菜單： ||\n");</p><p>　　printf("|| 1--創(chuàng)建平衡二叉樹(shù) ||\n");</p><p>　　prin

48、tf("|| 2--按 要 求 輸 出 ||\n");</p><p>　　printf("|| 3--插 入 元 素 ||\n");</p><p>　　printf("|| 4--銷(xiāo)毀 二 叉 樹(shù) ||\n");</p><p>　　printf("|| 5--退

49、 出 ||\n");</p><p>　　printf("\n請(qǐng)選擇：");</p><p><b>　　do{</b></p><p>　　scanf("%d",&chose);</p><p>　　}while(flag==0&&chose

50、!=1&&chose!=5&&printf("尚未創(chuàng)建，必須先創(chuàng)建\n請(qǐng)選擇："));</p><p>　　system("cls");</p><p>　　switch(chose)</p><p><b>　　{</b></p><p><

51、b>　　default:</b></p><p>　　printf("輸入出錯(cuò)\n");</p><p><b>　　case 1:</b></p><p><b>　　number=0;</b></p><p>　　CreatBalanceTree(T);&l

52、t;/p><p><b>　　flag=1;</b></p><p>　　system("cls");</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　printf

53、("共有%d個(gè)結(jié)點(diǎn)\n",number);</p><p>　　printf("有序輸出：");</p><p>　　Print_Mid(T);</p><p>　　printf("\n\n按層輸出：");</p><p>　　WideTraverse(T);</p>

54、<p>　　printf("\n\n\n");</p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　printf("插入元素：\n");</p><p>　　printf(&quo

55、t;請(qǐng)輸入關(guān)鍵字(輸入0停止)：");</p><p>　　scanf("%d",&e.Key);</p><p>　　flushall();</p><p>　　printf("輸入相關(guān)信息(0-20字符):");</p><p>　　scanf("%s",e.i

56、nfo);</p><p>　　InsertAVL(T,e);</p><p><b>　　break;</b></p><p><b>　　case 4:</b></p><p>　　printf("已銷(xiāo)毀平衡二叉樹(shù)\n");</p><p>　　Des

57、tory(T);</p><p><b>　　break;</b></p><p><b>　　case 5:</b></p><p>　　printf("確認(rèn)退出? 1--YES 2--NO\n");</p><p>　　if(scanf("%d",&a

58、mp;chose),chose==1) </p><p><b>　　exit(1);</b></p><p>　　system("cls");</p><p><b>　　}</b></p><p>　　}while(1);</p><p><b&

59、gt;　　}</b></p><p>　　void CreatBalanceTree(BSTree &T)</p><p><b>　　{</b></p><p>　　ElemType e;</p><p>　　printf("\n\n創(chuàng)建平衡二叉樹(shù)\n");</p>

60、<p>　　printf("請(qǐng)輸入關(guān)鍵字(輸入0停止)：");</p><p>　　scanf("%d",&e.Key);</p><p>　　while(e.Key)</p><p><b>　　{</b></p><p>　　flushall();</

61、p><p>　　printf("輸入相關(guān)信息(0-20字符):");</p><p>　　scanf("%s",e.info);</p><p>　　printf("\n");</p><p>　　if(InsertAVL(T,e))</p><p><b&

62、gt;　　number++;</b></p><p>　　printf("請(qǐng)輸入關(guān)鍵字(輸入0停止)：");</p><p>　　scanf("%d",&e.Key);</p><p><b>　　}</b></p><p><b>　　}</b

63、></p><p>　　int Print_Mid(BSTree T)</p><p><b>　　{</b></p><p><b>　　if(T)</b></p><p><b>　　{</b></p><p>　　if(Print_Mid(T

64、->lchild))</p><p>　　if(Visit(T))</p><p>　　if(Print_Mid(T->rchild))</p><p>　　return OK;</p><p>　　return ERROR;</p><p><b>　　}</b></p>

65、<p>　　else return OK;</p><p><b>　　}</b></p><p>　　int Visit(BSTree T)</p><p><b>　　{</b></p><p>　　printf("%d ",T->data.Key);&

66、lt;/p><p>　　return OK;</p><p><b>　　}</b></p><p>　　int InitQueue(LinkQueue &Q)</p><p><b>　　{</b></p><p>　　Q.front=Q.rear=(QNodeP)ma

67、lloc(sizeof(QNode));</p><p>　　if(!Q.front)</p><p>　　return ERROR;</p><p>　　Q.front->next=NULL;</p><p>　　return OK;</p><p><b>　　}</b></p&g

68、t;<p>　　int QueueEmpty(LinkQueue Q)</p><p><b>　　{</b></p><p>　　if(Q.front==Q.rear)</p><p>　　return TRUE;</p><p>　　else return FALSE;</p><p

69、><b>　　}</b></p><p>　　int EnQueue(LinkQueue &Q,BSTree p)</p><p><b>　　{</b></p><p>　　QNodeP q=NULL;</p><p>　　q=(QNodeP)malloc(sizeof(QNode)

70、);</p><p><b>　　if(!q)</b></p><p>　　return ERROR;</p><p><b>　　q->e=p;</b></p><p>　　q->next=NULL;</p><p>　　Q.rear->next=q;&l

71、t;/p><p><b>　　Q.rear=q;</b></p><p>　　return OK;</p><p><b>　　}</b></p><p>　　int DeQueue(LinkQueue &Q,BSTree &p)</p><p><b>

72、;　　{</b></p><p>　　QNodeP q=NULL;</p><p>　　if(Q.front==Q.rear)</p><p>　　return ERROR;</p><p>　　q=Q.front->next;</p><p><b>　　p=q->e;</b&

73、gt;</p><p>　　Q.front->next=q->next;</p><p>　　if(!q->next)</p><p>　　Q.rear=Q.front;</p><p><b>　　free(q);</b></p><p>　　return OK;</p&

74、gt;<p><b>　　}</b></p><p>　　int WideTraverse(BSTree T)</p><p><b>　　{</b></p><p>　　LinkQueue Q1,Q2;</p><p>　　BSTree p=NULL;</p><

75、p><b>　　int i=1;</b></p><p>　　InitQueue(Q1);</p><p>　　InitQueue(Q2);</p><p>　　printf("\n按層輸出：\n");</p><p><b>　　if(T)</b></p>

76、<p>　　EnQueue(Q1,T);</p><p>　　while((!QueueEmpty(Q1))||(!QueueEmpty(Q2)))</p><p><b>　　{</b></p><p>　　printf("第%d層:",i);</p><p><b>　　if(

77、i%2)</b></p><p>　　while(!QueueEmpty(Q1))</p><p><b>　　{</b></p><p>　　DeQueue(Q1,p);</p><p><b>　　Visit(p);</b></p><p>　　if(p-&g

78、t;lchild)</p><p>　　EnQueue(Q2,p->lchild);</p><p>　　if(p->rchild)</p><p>　　EnQueue(Q2,p->rchild);</p><p><b>　　}</b></p><p><b>　　e

79、lse</b></p><p>　　while(!QueueEmpty(Q2))</p><p><b>　　{</b></p><p>　　DeQueue(Q2,p);</p><p><b>　　Visit(p);</b></p><p>　　if(p->

80、;lchild)</p><p>　　EnQueue(Q1,p->lchild);</p><p>　　if(p->rchild)</p><p>　　EnQueue(Q1,p->rchild);</p><p><b>　　}</b></p><p>　　printf(&quo

81、t;\n");</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　printf("該樹(shù)共有%d層\n",i-1);</p><p>　　return OK;</p><p><b>

82、;　　}</b></p><p>　　int InsertAVL(BSTree &T,ElemType e)</p><p><b>　　{</b></p><p><b>　　if(!T)</b></p><p><b>　　{</b></p>

83、<p>　　T=(BSTree)malloc(sizeof(BSTNode));</p><p><b>　　if(!T) </b></p><p>　　exit(ERROR);</p><p>　　T->data=e;</p><p>　　T->lchild=T->rchild=NULL

84、;</p><p><b>　　T->bf=EH;</b></p><p>　　taller=TRUE;</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b&

85、gt;</p><p>　　if(EQ(e.Key,T->data.Key))</p><p><b>　　{</b></p><p>　　taller=FALSE;</p><p>　　printf("樹(shù)中存在此關(guān)鍵字\n");</p><p>　　return ERR

86、OR;</p><p><b>　　}</b></p><p>　　if(LT(e.Key,T->data.Key))</p><p><b>　　{</b></p><p>　　if(!InsertAVL(T->lchild,e))</p><p>　　retu

87、rn ERROR;</p><p>　　if(taller)</p><p><b>　　{</b></p><p>　　switch(T->bf)</p><p><b>　　{</b></p><p><b>　　case LH:</b><

88、;/p><p>　　LeftBalance(T);</p><p>　　taller=FALSE;</p><p><b>　　break;</b></p><p><b>　　case EH:</b></p><p><b>　　T->bf=LH;</b&

89、gt;</p><p>　　taller=TRUE;</p><p><b>　　break;</b></p><p><b>　　case RH:</b></p><p><b>　　T->bf=EH;</b></p><p>　　taller=

90、FALSE;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else

91、</b></p><p><b>　　{</b></p><p>　　if(!InsertAVL(T->rchild,e))</p><p>　　return ERROR;</p><p>　　if(taller)</p><p><b>　　{</b>&l

92、t;/p><p>　　switch(T->bf)</p><p><b>　　{</b></p><p><b>　　case LH:</b></p><p><b>　　T->bf=EH;</b></p><p>　　taller=FALSE;

93、</p><p><b>　　break;</b></p><p><b>　　case EH:</b></p><p><b>　　T->bf=RH;</b></p><p>　　taller=TRUE;</p><p><b>　　b

94、reak;</b></p><p><b>　　case RH:</b></p><p>　　RightBalance(T);</p><p>　　taller=FALSE;</p><p><b>　　break;</b></p><p><b>　　

95、}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return OK;</p><p><b>　　}</b><

96、/p><p>　　void LeftBalance(BSTree &T)</p><p><b>　　{</b></p><p>　　BSTree lc=NULL,rd=NULL;</p><p>　　lc=T->lchild;</p><p>　　switch(lc->bf)&l

97、t;/p><p><b>　　{</b></p><p><b>　　case LH:</b></p><p>　　T->bf=lc->bf=EH;</p><p>　　R_Rotate(T);</p><p><b>　　break;</b>&

98、lt;/p><p><b>　　case RH:</b></p><p>　　rd=lc->rchild;</p><p>　　switch(rd->bf)</p><p><b>　　{</b></p><p><b>　　case LH:</b&g

99、t;</p><p><b>　　T->bf=RH;</b></p><p>　　lc->bf=EH;</p><p><b>　　break;</b></p><p><b>　　case EH:</b></p><p>　　T->b

100、f=lc->bf=EH;</p><p><b>　　break;</b></p><p><b>　　case RH:</b></p><p><b>　　T->bf=EH;</b></p><p>　　lc->bf=LH;</p><p

101、><b>　　break;</b></p><p><b>　　}</b></p><p>　　rd->bf=EH;</p><p>　　L_Rotate(T->lchild);</p><p>　　R_Rotate(T);</p><p><b>

102、;　　}</b></p><p><b>　　}</b></p><p>　　void RightBalance(BSTree &T)</p><p><b>　　{</b></p><p>　　BSTree lc=NULL,rd=NULL;</p><p&g

103、t;　　rd=T->rchild;</p><p>　　switch(rd->bf)</p><p><b>　　{</b></p><p><b>　　case RH:</b></p><p>　　T->bf=rd->bf=EH;</p><p>　

104、　L_Rotate(T);</p><p><b>　　break;</b></p><p><b>　　case LH:</b></p><p>　　lc=rd->lchild;</p><p>　　switch(lc->bf)</p><p><b>

105、;　　{</b></p><p><b>　　case RH:</b></p><p><b>　　T->bf=LH;</b></p><p>　　rd->bf=EH;</p><p><b>　　break;</b></p><p&

106、gt;<b>　　case EH:</b></p><p>　　T->bf=rd->bf=EH;</p><p><b>　　break;</b></p><p><b>　　case LH:</b></p><p><b>　　T->bf=EH;&

107、lt;/b></p><p>　　rd->bf=RH;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　lc->bf=EH;</p><p>　　R_Rotate(T->rchild);&l

108、t;/p><p>　　L_Rotate(T);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void R_Rotate(BSTree &p)//右旋</p><p><b>　　{</b><

109、;/p><p>　　BSTree lc=NULL;</p><p>　　lc=p->lchild;</p><p>　　p->lchild=lc->rchild;</p><p>　　lc->rchild=p;</p><p><b>　　p=lc;</b></p>

110、<p><b>　　}</b></p><p>　　void L_Rotate(BSTree &p)</p><p><b>　　{</b></p><p>　　BSTree rc=NULL;</p><p>　　rc=p->rchild;</p><

111、p>　　p->rchild=rc->lchild;</p><p>　　rc->lchild=p;</p><p><b>　　p=rc;</b></p><p><b>　　}</b></p><p>　　void Destory(BSTree &T)</p&

112、gt;<p><b>　　{</b></p><p><b>　　if(T)</b></p><p><b>　　{</b></p><p>　　if(T->lchild)</p><p>　　Destory(T->lchild);</p>

113、<p>　　if(T->rchild)</p><p>　　Destory(T->rchild);</p><p>　　free(T);//必須先銷(xiāo)毀左右孩子</p><p><b>　　T=NULL;</b></p><p><b>　　}</b></p>