數(shù)據(jù)結(jié)構(gòu)大作業(yè)平衡二叉樹

1、數(shù)學(xué)與計算機學(xué)院計算機系數(shù)據(jù)結(jié)構(gòu)程序設(shè)計報告平衡二叉樹學(xué)生姓名：*學(xué)好：1004681028班級：計算機系102指導(dǎo)老師：*報告日期：2011/6/26目錄1 .平衡二叉樹31.1 平衡二叉樹的定義.31.2 平衡二叉樹的構(gòu)造.31.3 平衡二叉樹查找的分析.32 .程序功能33 .程序結(jié)構(gòu)類型34 .程序函數(shù)45 .算法思想55.1 判斷二叉樹的旋轉(zhuǎn)方法.55.2 平衡旋轉(zhuǎn)處理.55.3 在平衡二叉樹中插入元素.55.4 在平衡二叉樹中刪除元素.55.5 輸由平衡二叉樹樹形.55.6 銷毀平衡二叉樹.56 .程序設(shè)計總結(jié).97 .結(jié)束語108 .附錄：程序清單10.平衡二叉樹平衡二叉樹的定義

2、平衡二叉樹(BalancedBinaryTree或Height-BalancedTree)又稱AVL樹。它或者是一顆空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。若將二叉樹上結(jié)點的平衡因子BF(BalancedFactor)定義為該結(jié)點的左子樹的深度減去它的右子樹的深度，則平衡二叉樹上所有結(jié)點的平衡因子之可能是-1、0和1。只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于1,則該二叉樹就是不平衡的。平衡二叉樹的構(gòu)造構(gòu)造一顆平衡二叉樹的過程就是將一顆空樹從根結(jié)點起，逐步插入或刪除結(jié)點并不斷對此樹進(jìn)行平衡化。在構(gòu)造平衡二叉樹的過程中有插

3、入和刪除兩大操作。在樹中進(jìn)行插入和刪除操作都可使樹失去平衡，然而要讓二叉排序樹由不平衡轉(zhuǎn)化為平衡，操作就是對二叉樹進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)的過程將在算法思想中詳細(xì)介紹。平衡二叉樹查找的分析在平衡二叉樹上進(jìn)行查找的過程和二叉排序樹相同，因此，在查找過程中和給定值進(jìn)行比較的關(guān)鍵字個數(shù)不超過樹的深度。因此，在平衡二叉樹上進(jìn)行查找的時間復(fù)雜度為O(logn).程序功能:創(chuàng)建二叉樹、插入數(shù)據(jù)、本程序的功能就是將二叉排序樹轉(zhuǎn)變?yōu)槠胶舛鏄?，其操作有刪除數(shù)據(jù)、輸出、銷毀二叉樹和退出。1創(chuàng)建二叉樹2插入數(shù)據(jù)3刪除數(shù)據(jù)4輸出5銷毀二叉樹0退出請選擇：.程序結(jié)構(gòu)類型在本程序中主要用到兩個結(jié)構(gòu)類型：結(jié)構(gòu)體和隊列。二叉樹是鏈?zhǔn)?/p>

4、存儲結(jié)構(gòu)，故用結(jié)構(gòu)體來定義其結(jié)構(gòu)。隊列是用作輸出二叉樹的樹形(層序輸出)。.程序函數(shù)main()函數(shù)：(1)函數(shù)原形：voidmain()(2)功能：顯示總菜單，調(diào)用子函數(shù)Create()函數(shù)：(1)函數(shù)原形：voidCreate(BSTree&T)(2)功能：實現(xiàn)二叉樹的創(chuàng)建Insert()函數(shù):(1)函數(shù)原形：voidInsert(BSTree&T)(2)功能：實現(xiàn)在二叉樹中插入數(shù)據(jù)InsertAVL()函數(shù)：(1)函數(shù)原形：intInsertAVL(BSTree&T,inte,int&taller)(2)功能：插入結(jié)點，并將二叉樹平衡化DeleteMenu

5、()函數(shù)：(1)函數(shù)原形：voidDeleteMenu(BSTree&T)(2)功能：實現(xiàn)在二叉樹中刪除數(shù)據(jù)DeleteA/L()函數(shù)：(1)函數(shù)原形：intDeleteAVL(BSTree&T,inte,int&shorter)(2)功能：刪除結(jié)點，并將二叉樹平衡化Delete()函數(shù)：(1)函數(shù)原形：intDelete(BSTree&p)(2)功能：實現(xiàn)刪除結(jié)點Search(尚數(shù)：(1)函數(shù)原形：voidSearch(BSTree&T,inte,intkey)(2)功能：在樹中查找和關(guān)鍵字相等的結(jié)點R_Rotate()函數(shù)：(1)函數(shù)原形：voidR

6、_Rotate(BSTree&p)(2)功能：對以*p為根結(jié)點的子樹進(jìn)行右旋平衡處理L_Rotate()函數(shù)：(1)函數(shù)原形：voidL_Rotate(BSTree&p)(2)功能：對以*p為根結(jié)點的子樹進(jìn)行左旋平衡處理RightBalance()S數(shù)：(1)函數(shù)原形：intRightBalance(BSTree&T)(2)功能：對以指針T所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理LeftBalance()函數(shù)：(1)函數(shù)原形：intLeftBalance(BSTree&T)(2)功能：對以指針T所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理Output()函數(shù)：(1)函數(shù)原形

7、：voidOutput(BSTreeT)(2)功能：將二叉樹按中序和層序輸出Inordertraverse()函數(shù)：(1)函數(shù)原形：voidInordertraverse(BSTreeT)(2)功能：將二叉樹按中序輸出Depth()函數(shù)：(1)函數(shù)原形：voidDepth(BSTreep,intn,int&num)(2)功能：求二叉樹的深度Levelordertraverse(尚數(shù)：(1)函數(shù)原形：intLevelordertraverse(Stack&Q)(2)功能：將二叉樹按層序輸出Initstack()函數(shù)：(1)函數(shù)原形：intInitstack(Stack&Q

8、)(2)功能：構(gòu)造一個空隊列Push()S數(shù)：(1)函數(shù)原形：intPush(Stack&Q,BSTreee)(2)功能：插入元素e為新的隊尾元素Pop()函數(shù)：(1)函數(shù)原形：intPop(Stack&Q,BSTree&q)(2)功能：刪除對頭元素Destroy(尚數(shù)：(1)函數(shù)原形：voidDestroy(BSTree&T)(2)功能：將隊列銷毀.算法思想判斷二叉樹的旋轉(zhuǎn)方法在一顆平衡二叉樹中插入或刪除一個結(jié)點后，若二叉樹失去平衡，則需將二叉樹進(jìn)行平衡化處理，簡而言之，就是對不平衡的二叉樹進(jìn)行旋轉(zhuǎn)處理。假設(shè)在二叉排序樹中插入或刪除結(jié)點而失去平衡的最小子樹根結(jié)

9、點的指針為T(即T是離插入或刪除結(jié)點最近，且平衡因子絕對值超過1的祖先結(jié)點),指針p指向結(jié)點T的左子樹的根結(jié)點，指針q指向結(jié)點T的右子樹的根結(jié)點，則判斷方法如下：(1)若結(jié)點T的平衡因子為2,結(jié)點p的平衡因子為1,則需對結(jié)點T進(jìn)行單向右旋平衡處理；(2)若結(jié)點T的平衡因子為-2,結(jié)點p的平衡因子為-1,則需對結(jié)點T進(jìn)行單向左旋平衡處理；(3)若結(jié)點T的平衡因子為2,結(jié)點p的平衡因子為-1,則需先對結(jié)點p進(jìn)行單向左旋平衡處理，再對結(jié)點T進(jìn)行單向右旋平衡處理，將這兩步簡稱為對結(jié)點T進(jìn)行雙向旋轉(zhuǎn)(先左后右)平衡處理；(4)若結(jié)點T的平衡因子為-2,結(jié)點p的平衡因子為1,則需先對結(jié)點p進(jìn)行單向右旋平衡

10、處理，再對結(jié)點T進(jìn)行單向左旋平衡處理，將這兩步簡稱為對結(jié)點T進(jìn)行雙向旋轉(zhuǎn)(先右后左)平衡處理；平衡旋轉(zhuǎn)處理假設(shè)由于在二叉排序樹上插入或刪除結(jié)點而失去平衡的最小子樹根結(jié)點的指針為T(即T為里插入結(jié)點最近，且平衡因子絕對值超過1的祖先結(jié)點)，則失去平衡后進(jìn)行平衡處理有如下4種情況：(1)單向右旋平衡處理：若指針p指向以*T為根的左子樹的根結(jié)點，將*p的右子樹作為*T的左子樹，再將以*T為根的樹作為*p的右子樹，如圖(a)所示。（2）單向左旋平衡處理：若指針p指向以*T為根的右子樹的根結(jié)點，將*p的左子樹作為*T的右子樹，再將以*T為根的樹作為*p的左子樹，如圖（b）所示。（3）雙向旋轉(zhuǎn)（先左后右）

11、平衡處理：若p指向以*T為根的左子樹的根結(jié)點，q以*p為根的右子樹的根結(jié)點，則先將以*p為根結(jié)點的樹進(jìn)行單向左旋，再將以*q為根結(jié)點的樹進(jìn)行單向右旋，如圖（c）所示。圖（4）雙向旋轉(zhuǎn)（先右后左）平衡處理：若p指向以*T為根的右子樹的根結(jié)點，q以*p為根的左子樹的根結(jié)點，則先將以*p為根結(jié)點的樹進(jìn)行單向右旋，再將以*q為根結(jié)點的樹進(jìn)行單向左旋，如圖（d）所示。2圖(d)在平衡二叉樹BBST中插入元素在平衡的二叉排序樹上插入一個新的數(shù)據(jù)元素e：（1）若BBST為空樹，則插入一個數(shù)據(jù)元素e的新結(jié)點作為BBST的根結(jié)點，樹的深度增1;（2）若e的關(guān)鍵字和BBST的根結(jié)點的關(guān)鍵字相等，則不進(jìn)行插入；（3

12、）若e的關(guān)鍵字小于BBST的根結(jié)點的關(guān)鍵字，而且在BBST的左子樹中不存在和e有相同關(guān)鍵字的結(jié)點，則將e插入在BBST的左子樹上，并且當(dāng)插入之后的左子樹深度增加（+1）時，分別就下列不同情況處理：BBST的根結(jié)點的平衡因子為-1（右子樹的深度大于左子樹的深度）：則將根結(jié)點的平衡因子更改為0,BBST的深度不變；BBST的根結(jié)點的平衡因子為0,（左、右子樹的深度相等）：則將根結(jié)點的平衡因子更改為1,BBST的深度增1;BBST的根結(jié)點的平衡因子為1（左子樹的深度大于右子樹的深度）：若BBST的左子樹的平衡因子為1,則需進(jìn)行單向右旋平衡處理，并且在右旋處理之后，將根結(jié)點和其右子樹根結(jié)點的平衡因子更

13、改為0,樹的深度不變；若BBST的左子樹根結(jié)點的平衡因子為-1,則需進(jìn)行先向左、后先向右的雙向旋轉(zhuǎn)平衡處理，并且在旋轉(zhuǎn)處理之后，修改根結(jié)點和其左、右子樹根結(jié)點的平衡因子，樹的深度不變；（4）若e的關(guān)鍵字大于BBST的根結(jié)點的關(guān)鍵字，而且BBST的右子樹不存在和e有相同關(guān)鍵字的結(jié)點，則將e插入在BBST的右子樹上，并且當(dāng)插入之后的右子樹深度增加（+1）時，分別就不同情況處理：BBST的根結(jié)點的平衡因子為1（左子樹的深度大于右子樹的深度）：則將根結(jié)點的平衡因子更改為0,BBST的深度不變；BBST的根結(jié)點的平衡因子為0,（左、右子樹的深度相等）：則將根結(jié)點的平衡因子更改為-1,BBST的深度增1;

14、BBST的根結(jié)點的平衡因子為-1（右子樹的深度大于左子樹的深度）：若BBST的左子樹的平衡因子為-1,則需進(jìn)行單向左旋平衡處理，并且在左旋處理之后，將根結(jié)點和其左子樹根結(jié)點的平衡因子更改為0,樹的深度不變；若BBST的左子樹根結(jié)點的平衡因子為1,則需進(jìn)行先向右、后先向左的雙向旋轉(zhuǎn)平衡處理，并且在旋轉(zhuǎn)處理之后，修改根結(jié)點和其左、右子樹根結(jié)點的平衡因子，樹的深度不變；平衡二叉樹中刪除元素假設(shè)在平衡二叉樹上刪除結(jié)點為*p（指向結(jié)點的指針為p）,其雙親結(jié)點為*f（結(jié)點指針為f）,且不失一般性，可設(shè)*p是*f的左孩子：（1）若*p結(jié)點為葉子結(jié)點，則直接將*p結(jié)點刪除，如圖（e）所示。圖（e）（2）若*p

15、結(jié)點只有左子樹或者只有右子樹，此時只要令*p的左子樹或右子樹成為其雙親結(jié)點*f的左子樹，如圖（f）所示；圖（2）若*p結(jié)點的左子樹和右子樹均不空，則令*p的直接前驅(qū)代替*p,然后再從二叉排序樹中刪去它的直接前驅(qū)，如圖（g）所示；在上述三種刪除*p結(jié)點的處理后，若二叉樹仍然平衡，則只需修改*f結(jié)點的平衡因子;否則，則需從*p結(jié)點回溯到根結(jié)點，找到回溯途中遇到的不平衡結(jié)點，并將其平衡化；將刪除結(jié)點后不平衡樹平衡化的具體處理方法如下：設(shè)p為回溯至根結(jié)點的路徑上的某一結(jié)點結(jié)點p的平衡因子為0,若刪除結(jié)點為p結(jié)點左子樹上的結(jié)點，則將結(jié)點p的平衡因子改為-1,并相應(yīng)將樹平衡化；若刪除結(jié)點為p結(jié)點右子樹上的

16、結(jié)點，則將結(jié)點p的平衡因子改為1,并相應(yīng)將樹平衡化。無論刪除結(jié)點為p結(jié)點左子樹或右子樹上的結(jié)點，都不需要再向根結(jié)點回溯，平衡處理結(jié)束；結(jié)點p的平衡因子為1,若刪除結(jié)點為p結(jié)點左子樹上的結(jié)點，則將結(jié)點p的平衡因子該為0,再從結(jié)點p向根結(jié)點回溯；若刪除結(jié)點為p結(jié)點右子樹上白結(jié)點，設(shè)q指向p的左子樹的根結(jié)點，則需將結(jié)點p進(jìn)行單向右旋處理，并相應(yīng)修改各結(jié)點的平衡因子，再從結(jié)點p向根結(jié)點回溯；結(jié)點p的平衡因子為-1,若刪除結(jié)點為p結(jié)點左子樹上的結(jié)點，設(shè)q指向p的右子樹的根結(jié)點，則需將結(jié)點p進(jìn)行單向左旋處理，并相應(yīng)修改各結(jié)點的平衡因子，再從結(jié)點p向根結(jié)點回溯；若刪除結(jié)點為p結(jié)點右子樹上的結(jié)點，則將結(jié)點p的

17、平衡因子該為0,再從結(jié)點p向根結(jié)點回溯；特別需要注意的是，在平衡二叉樹中刪除一個結(jié)點后使不平衡根結(jié)點的平衡因子變?yōu)?或-2,根結(jié)點的左或右孩子的平衡因子為0,此時需將根結(jié)點進(jìn)行單向右或左旋處理，然而旋轉(zhuǎn)處理后的樹的深度不變，如圖(h)所示。圖(h)輸出平衡二叉樹樹形將一顆平衡二叉樹按樹形輸出，要用到隊列，并且將此平衡二叉樹當(dāng)做滿二叉樹，孩子結(jié)點為空的用空字符代替。首先，應(yīng)先求出二叉樹的深度n,根據(jù)完全二叉樹的性質(zhì)知，第n層上的結(jié)點數(shù)至多為2n-1。此時，便可知道每層上應(yīng)輸出的空格數(shù)，并可以控制每層上結(jié)點之間的間距。此外，還要控制換行，記錄輸出的結(jié)點數(shù)num,若num等于i層的總結(jié)點數(shù)2i-1則

18、換行。若樹不為空，則將根結(jié)點插入到隊列中，接著將根結(jié)點從隊列中刪除并輸出，再把根結(jié)點的左、右孩子插入到隊列中，若孩子結(jié)點為空則用空字符代替，重復(fù)上述操作，直到當(dāng)num等于n層總結(jié)點數(shù)2n-1,則結(jié)束輸出。銷毀平衡二叉樹銷毀平衡二叉樹就是將二叉樹中的每一個結(jié)點用free()函數(shù)釋放，其具體過程采用遞歸：將平衡二叉樹的根結(jié)點的指針T傳到銷毀函數(shù)，如果*T結(jié)點的左孩子不為空，則將*T結(jié)點的左子樹的根結(jié)點進(jìn)行遞歸，直到結(jié)點的左孩子為空；再判斷結(jié)點的右孩子是否為空，若不為空則將結(jié)點的右子樹的根結(jié)點進(jìn)行遞歸，直到結(jié)點的右子樹為空；最后將結(jié)點的指針賦為空指針。.程序設(shè)計總結(jié)將一顆二叉排序樹轉(zhuǎn)變?yōu)槠胶舛鏄洳?/p>

19、將平衡樹按樹形輸出的算法，主要操作就是插入、刪除和輸出。本人在編寫插入算法，經(jīng)過陳老師的講解和課后的思考，根據(jù)書本上的算法編寫完成。然而，在二叉樹中刪除結(jié)點，本人是在網(wǎng)上以及圖書館書籍上查找的。很令人失望的是，網(wǎng)上和書籍里對于在二叉樹中刪除結(jié)點再將其平衡化的算法思想介紹很少，甚至有些書籍上根本就沒提及過。看著做的一點筆記，本人還是很是不知所措，不懂其算法思想，經(jīng)過三天的思索，終于有些頭緒，嘗試著編寫，盡管失敗了很多次，但總算勉強寫出了算法。（我所編寫的算法可能和書籍中講解的不同，只是換了一種實現(xiàn)方法。）至于將二叉樹按樹形輸出，是在陳老師的指導(dǎo)下寫出的，陳老師告訴我算法思想，之后就在思想的指導(dǎo)下

20、完成了算法。能完成這個程序，我還是感到挺高興的，在今后我也會一如既往，認(rèn)真努力學(xué)習(xí)，不斷提升自己，實現(xiàn)自己的理想。.結(jié)束語在此，我很是感謝陳老師，他在我學(xué)習(xí)的途中給了我很多的幫助，讓我懂得很多東西，學(xué)會很多，真心感謝他。同時，我也要對平時幫助我的同學(xué)表示感謝。在我人生的道路中,很多人在我失意時幫我走出陰霾，感謝他們。.附錄：程序清單#include<stdio.h>#include<stdlib.h>#include<math.h>defineOK1defineERROR0defineLH1defineEH0defineRH-1typedefstructBS

21、TNodeintdata;intbf;structBSTNode*lchild,*rchild;BSTNode,*BSTree;typedefstructBSTreep;elem,*Elem;typedefstructElembase;Elemtop;Stack;inth,num,m,k,t,key=0;BSTreew;voidCreate(BSTree&T);voidInsert(BSTree&T);intInsertAVL(BSTree&T,inte,int&taller);voidR_Rotate(BSTree&p);voidL_Rotate(BS

22、Tree&p);intLeftBalance(BSTree&T);intRightBalance(BSTree&T);voidDeleteMenu(BSTree&T);intDeleteAVL(BSTree&T,inte,int&shorter);intDelete(BSTree&p);voidSearch(BSTree&T,inte,intkey);voidOutput(BSTreeT);voidInordertraverse(BSTreeT);voidDepth(BSTreep,intn,int&num);intLev

23、elordertraverse(Stack&Q);intInitstack(Stack&Q);intPush(Stack&Q,BSTreee);intPop(Stack&Q,BSTree&q);voidDestroy(BSTree&T);voidmain()inta=1,flag=0;BSTreeT=NULL;while(a)system("cls");printf("nnnnntttt1創(chuàng)建二叉科nnnn");printf("tttt2-插入數(shù)據(jù)nnnn");printf("

24、tttt3一刪除數(shù)據(jù)nnnn");printf("tttt4-輸出nnnn");printf("tttt5銷毀二叉nnnn");printf("tttt0-退出nn");if(!flag)printf("nnnn請選擇:");elseprintf("nnnn你的輸入有誤，請重新輸入:");flag=0;scanf("%d",&a);switch(a)case1:system("cls");Create(T);break;case2:sys

25、tem("cls");Insert(T);break;case3:system("cls");DeleteMenu(T);break;case4:system("cls");if(T)Output(T);elseprintf("此二叉樹為空樹");printf("nnn按Enterf");getchar();getchar();)break;case5:system("cls");Destroy(T);printf("已將此二叉樹銷毀nnnn");prin

26、tf("nnn按Enterf");getchar();getchar();case0:system("cls");printf("nnnnnnnnnntttttTHANKSnnnnnnnnnnnn");break;default:flag=1;break;)voidCreate(BSTree&T)inta=1,s,taller=false;while(a)printf(“請輸入數(shù)據(jù)(0結(jié)束):");scanf("%d",&a);if(a)s=InsertAVL(T,a,taller);if

27、(!s)printf("%d已存在二叉樹中",a);)printf("nn");)voidInsert(BSTree&T)inta,s,taller=false;printf("請輸入數(shù)據(jù):");scanf("%d",&a);dos=InsertAVL(T,a,taller);if(s)printf("nn%d已插入到二叉樹中",a);elsesystem("cls");printf("%d已存在二叉樹中，請重新輸入：”,a);scanf("

28、;%d",&a);)while(!s);printf("nnnnnnn按Enterf");getchar();getchar();intInsertAVL(BSTree&T,inte,int&taller)if(!T)T=(BSTree)malloc(sizeof(BSTNode);if(!T)exit(-1);T->data=e;T->bf=EH;T->lchild=T->rchild=NULL;taller=true;elseif(e=T->data)taller=false;return0;elseif(

29、e<T->data)if(!InsertAVL(T->lchild,e,taller)return0;if(taller)switch(T->bf)caseLH:LeftBalance(T);taller=false;break;caseEH:T->bf=LH;taller=true;break;caseRH:T->bf=EH;taller=false;break;elseif(!InsertAVL(T->rchild,e,taller)return0;if(taller)switch(T->bf)caseLH:T->bf=EH;talle

30、r=false;break;caseEH:T->bf=RH;taller=true;break;caseRH:RightBalance(T);taller=false;break;return1;voidDeleteMenu(BSTree&T)inta,shorter=false,s;printf("請輸入要刪除的數(shù)據(jù):");scanf("%d",&a);dos=DeleteAVL(T,a,shorter);ifprintf("nn已將從二叉樹中刪除",a);elseif(key)DeleteAVL(T,key,

31、shorter);Search(T,a,key);printf("nn已將d從二叉樹中刪除",a);elsesystem("cls");printf("%d不在此二叉樹中，請重新輸入:",a);scanf("%d",&a);while(!s&&!key);key=0;printf("nnnnnnn按Enterf");getchar();getchar();intDeleteAVL(BSTree&T,inte,int&shorter)ints;if(!T)s

32、horter=0;return0;elseif(T->data=e)s=Delete(T);if(!s)return0;elseshorter=1;return1;elseif(e<T->data)if(!DeleteAVL(T->lchild,e,shorter)return0;if(shorter)switch(T->bf)caseLH:T->bf=EH;shorter=1;break;caseEH:T->bf=RH;shorter=0;break;caseRH:shorter=RightBalance(T);break;)elseif(!Dele

33、teAVL(T->rchild,e,shorter)return0;if(shorter)switch(T->bf)caseLH:shorter=LeftBalance(T);break;caseEH:T->bf=LH;shorter=0;break;caseRH:T->bf=EH;shorter=1;break;)return1;)intDelete(BSTree&p)BSTreeq,s;if(!p->rchild)q=p;p=p->lchild;free(q);)elseif(!p->lchild)q=p;p=p->rchild;fr

34、ee(q);)elseq=p;s=p->lchild;while(s->rchild)q=s;s=s->rchild;)key=s->data;return0;)return1;)voidSearch(BSTree&T,inte,intkey)if(T->data=e)T->data=key;elseif(e<T->data)Search(T->lchild,e,key);elseSearch(T->rchild,e,key);)voidR_Rotate(BSTree&p)BSTreelc;lc=p->lchil

35、d;p->lchild=lc->rchild;lc->rchild=p;p=lc;)voidL_Rotate(BSTree&p)BSTreerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;)intRightBalance(BSTree&T)BSTreerc,ld;rc=T->rchild;switch(rc->bf)caseLH:ld=rc->lchild;switch(ld->bf)caseLH:T->bf=EH;rc->bf=RH;br

36、eak;caseEH:T->bf=rc->bf=EH;break;caseRH:T->bf=LH;rc->bf=EH;break;)ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);break;caseEH:T->bf=RH;rc->bf=LH;L_Rotate(T);return0;break;caseRH:T->bf=rc->bf=EH;L_Rotate(T);break;)return1;)intLeftBalance(BSTree&T)BSTreelc,rd;lc=T->lchild;switch(lc->bf)caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;caseEH:T->bf=LH;lc->