平衡二叉樹AVL的查找、插入和刪除

1、平衡二叉樹AVL查找、插入和刪除小組成員：陳 靜101070009陳丹璐101070006陳 嬌101070008第2頁共 38 頁目錄平衡二叉樹AVL .1.查找、插入和刪除 .1.問題描述.2.設(shè)計(jì)說明.3.一.ADT3.二.算法思想5.三.數(shù)據(jù)結(jié)構(gòu).12四. 程序結(jié)構(gòu)與流程 .13運(yùn)行平臺及開發(fā)工具 .15I/O格式.1.5算法復(fù)雜度分析 .1.8源代碼.1.8小結(jié).37問題描述利用平衡二叉樹實(shí)現(xiàn)一個(gè)動(dòng)態(tài)查找表。平衡二叉樹的查找、插入和刪除第3頁共 38 頁平衡二叉樹的查找、插入和刪除1)實(shí)現(xiàn)動(dòng)態(tài)查找表的三種根本功能：查找、插入和刪除。(2)初始時(shí)，平衡二叉樹為空樹，操作界面給出創(chuàng)立、查

2、找、插入和刪除和退出五種操作供選擇。每種操作均要提示輸入關(guān)鍵字。創(chuàng)立時(shí)，根據(jù)提示輸入數(shù)據(jù)，以-1為輸入數(shù)據(jù)的結(jié)束標(biāo)志，假設(shè)輸入數(shù)據(jù)重復(fù)，那么給出已存在相同關(guān)鍵字的提示，并不將其插入到二叉樹中。在查找時(shí)，如果查找的關(guān)鍵字不存在，那么顯示不存在查找的關(guān)鍵字，假設(shè)存在那么顯示存在要查找的關(guān)鍵字。插入時(shí)首先檢驗(yàn)原二叉樹中是否已存在相同第3頁共38頁-3-的關(guān)鍵字，假設(shè)沒有那么進(jìn)行插入并輸出二叉樹，假設(shè)有那么給出已有相同關(guān)鍵字的提醒。刪除時(shí)首先檢驗(yàn)原二叉樹中是否存在要?jiǎng)h除的關(guān)鍵字，假設(shè)有那么進(jìn)行刪除后并輸出二叉樹，假設(shè)沒有那么給出不存在要?jiǎng)h除的關(guān)鍵字的提醒。(3)平衡二叉樹的顯示采用中序遍歷的方法輸出，

3、還可以根據(jù)輸出數(shù)據(jù)是否有序驗(yàn)證 對平衡二叉樹的操作是否正確。設(shè)計(jì)說明(一)ADTADT BalancedBinaryTree(數(shù)據(jù)對象D : D是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)志的數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合。根本操作P:void R_Rotate(BSTree &p);第4頁共 38 頁初始條件：二叉樹存在，且關(guān)鍵字插入到以*p為根的二叉樹的左子樹的左孩子上；操作結(jié)果：對以*p為根的二叉排序樹作右旋處理第5頁共 38 頁初始條件：二叉樹存在，且關(guān)鍵字插入到以*p為根的二叉樹的右子樹的右孩子上；操作結(jié)果：對以*p為根的二叉排序樹

4、作左旋處理void LeftBalance(BSTree &T);初始條件：二叉樹存在，且關(guān)鍵字插入到T所指節(jié)點(diǎn)為根的二叉樹的左子樹的右孩子上;操作結(jié)果：對以指針T所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理void RightBalance(BSTree &T);初始條件：二叉樹存在，且關(guān)鍵字插入到T所指節(jié)點(diǎn)為根的二叉樹的右子樹的左孩子上;操作結(jié)果：對以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理bool InsertAVL(BSTree &T,int e,bool &taller);初始條件：T存在，且e與二叉樹的原有關(guān)鍵字不同；操作結(jié)果：插入結(jié)點(diǎn)e平且平衡化；boo

5、l SearchBST(BSTree &T,int key);初始條件：T存在且元素key與某關(guān)鍵字相同；操作結(jié)果：查找元素key是否在樹T中void PrintBST(BSTree T);初始條件：T存在操作結(jié)果：按中序遍歷輸出二叉樹的元素void CreatBST(BSTree &T);初始條件：T為空操作結(jié)果：創(chuàng)立平衡二叉樹,(注意:以輸入-1為二叉樹建立的結(jié)束)void LeftBalance_div(BSTree &p,int &shorter);平衡二叉樹的查找、插入和刪除第6頁共 38 頁平衡二叉樹的查找、插入和刪除初始條件：T存在操作結(jié)果：刪除結(jié)

6、點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理void RightBalance_div(BSTree &p,int &shorter);初始條件：T存在操作結(jié)果：刪除結(jié)點(diǎn)時(shí)右平衡旋轉(zhuǎn)處理void Delete(BSTree q,BSTree &r,int &shorter);初始條件：T存在且節(jié)點(diǎn)刪除成功操作結(jié)果：刪除結(jié)點(diǎn)int DeleteAVL(BSTree &p,int x,int &shorter);初始條件：操作結(jié)果：平衡二叉樹的刪除操作 ADT BalancedBinaryTree(二)算法思想1、查找在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)

7、據(jù)元素，假設(shè)查找成功,那么返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針 ，否那么返回空指針。如果樹T為空，那么查找不成功，返回空指針；當(dāng)樹T非空時(shí)，如果根指針T所指數(shù)據(jù)元素的關(guān)鍵字等于key，那么查找成功，返回 根指針T,否那么在左子樹中繼續(xù)查找，假設(shè)還未找到，那么繼續(xù)在右子樹中進(jìn)行查找，直到找到 該數(shù)據(jù)元素或樹T為空為止。第7頁共 38 頁查找元素key是否在樹T中bool SearchBST(BSTree &T,int key)(if(!T) return false;else if(EQ(key,T-data) return true;else if(LT(key,T-data) return

8、SearchBST(T-lchild,key);else return SearchBST(T-rchild,key);2、插入一假設(shè)T為空樹，那么插入一個(gè)數(shù)據(jù)元素為e的新節(jié)點(diǎn)作為T的根節(jié)點(diǎn)，樹長高，樹的深度增加1。二假設(shè)待插入的數(shù)據(jù)元素e與T的根節(jié)點(diǎn)的關(guān)鍵字相同，那么不進(jìn)行插入。三假設(shè)待插入的數(shù)據(jù)元素e小于根節(jié)點(diǎn)的關(guān)鍵字，且在T的左子樹上不存在與e相 等的數(shù)據(jù)元素，那么將e插入到T的左子樹上。下面就插入到左子樹之后，就不同的情況進(jìn)行處理：1假設(shè)之前T的根節(jié)點(diǎn)的平衡因子為-1 ,將根節(jié)點(diǎn)的平衡因子變?yōu)? , T的深度不變；2假設(shè)之前T的根節(jié)點(diǎn)的平衡因子為0,就將根節(jié)點(diǎn)的平衡因子變?yōu)? , T的

9、深度增加；3假設(shè)之前的T的根節(jié)點(diǎn)的平衡因子為1,那么當(dāng)其左子樹的根節(jié)點(diǎn)的平衡因子為1的時(shí)候，需要進(jìn)行單向右旋處理， 并且在右旋處理之后， 將根節(jié)點(diǎn)和其右子樹根節(jié)點(diǎn)的平衡因子 改為0,平衡二叉樹的查找、插入和刪除第8頁共 38 頁樹的深度不變；當(dāng)其左子樹的根節(jié)點(diǎn)的平衡因子為-1的時(shí)候，要進(jìn)行先左后右的雙向旋轉(zhuǎn)平衡，并在旋轉(zhuǎn)之后，修改根節(jié)點(diǎn)和其左右子樹的根節(jié)點(diǎn)的平衡因子，樹的深度不平衡二叉樹的查找、插入和刪除變。(四)假設(shè)待插入的數(shù)據(jù)元素e大于根節(jié)點(diǎn)的關(guān)鍵字，且在T的右子樹上不存在與e相等的數(shù)據(jù)元素，那么將e插入到T的右子樹上。下面就插入到右子樹之后，就不同的情況進(jìn)行處理：1假設(shè)之前T的根節(jié)點(diǎn)的平

10、衡因子為1 ,將根節(jié)點(diǎn)的平衡因子變?yōu)? , T的深度不變；2假設(shè)之前T的根節(jié)點(diǎn)的平衡因子為0,就將根節(jié)點(diǎn)的平衡因子變?yōu)? , T的深度增加；3假設(shè)之前的T的根節(jié)點(diǎn)的平衡因子為-1 ,那么當(dāng)其右子樹的根節(jié)點(diǎn)的平衡因子為-1的時(shí)候，需要進(jìn)行單向左旋處理，并且在左旋處理之后， 將根節(jié)點(diǎn)和其左子樹根節(jié)點(diǎn)的平衡因子改為0 ,樹的深度不變；當(dāng)其右子樹的根節(jié)點(diǎn)的平衡因子為1的時(shí)候，要進(jìn)行先右后左的雙向旋轉(zhuǎn)平衡，并在旋轉(zhuǎn)之后，修改根節(jié)點(diǎn)和其左右子樹的根節(jié)點(diǎn)的平衡因子，樹的深度不變。插入結(jié)點(diǎn)e,假設(shè)T中不存在和e相同關(guān)鍵字的結(jié)點(diǎn)，那么插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1，否那么返回0bool InsertAV

11、L(BSTree &T,int e,bool &taller) (if(!T)/插入新結(jié)點(diǎn)，樹長高，置taller為true(T = (BSTree)malloc(sizeof(BSTNode);T-data = e;第9頁共 38 頁T-lchild = T-rchild =NULL;T-bf = EH; taller = true;第10頁共 38 頁平衡二叉樹的查找、插入和刪除else(if(EQ(e,T-data) /樹中已存在和有相同關(guān)鍵字的結(jié)點(diǎn)那么不再插入(taller = false;printf(已存在相同關(guān)鍵字的結(jié)點(diǎn)n);return 0;if(LT(e,T-

12、data) /應(yīng)繼續(xù)在*T的左子樹中進(jìn)行搜索(if(!InsertAVL(T-lchild,e,taller)return 0;/未插入if(taller) /已插入到*T的左子樹中且左子樹長高(switch(T-bf) /檢查*T的平衡度(case LH: /原本左子樹比右子樹高，需要作左平衡處理LeftBalance(T);taller = false; break;case EH: /原本左子樹、右子等高，現(xiàn)因左子樹增高而使樹增高T-bf = LH;頁共 38 頁平衡二叉樹的查找、插入和刪除taller = true; break;case RH: /原本右子樹比左子樹高，現(xiàn)左、右子樹等

13、高T-bf = EH;taller = false; break;else /應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索if(!InsertAVL(T-rchild,e,taller)return 0;/未插入if(taller) /已插入到*T的右子樹中且右子樹長高switch(T-bf) /檢查*T的平衡度case LH: /原本左子樹比右子樹高，現(xiàn)左、右子樹等高T-bf = EH; taller = false; break;case EH: /原本左子樹、右子等高，現(xiàn)因右子樹增高而使樹增高T-bf = RH; taller = true; break;case RH: /原本右子樹比左子樹高，需要

14、作右平衡處理RightBalance(T); taller = false; break;平衡二叉樹的查找、插入和刪除第12頁共 38 頁return 1;/InsertAVL3、刪除元素的刪除，有三種情況，分別是：(1)被刪除的結(jié)點(diǎn)是葉子；(2)被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；(3)被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。具體實(shí)現(xiàn)如下：int DeleteAVL(BSTree &p,int x,int &shorter)(int k;BSTree q;if(p=NULL)(printf(不存在要?jiǎng)h除的關(guān)鍵字！!n);return 0;else if(xdata)/在p的左子

15、樹中進(jìn)行刪除(平衡二叉樹的查找、插入和刪除第13頁共 38 頁k=DeleteAVL(p-lchild,x,shorter);if(shorter=1)LeftBalance_div(p,shorter);return k;else if(xp-data)/在p的右子樹中進(jìn)行刪除(k=DeleteAVL(p-rchild,x,shorter);if(shorter=1)RightBalance_div(p,shorter);return k;else(q=p;if(p-rchild=NULL) /右子樹空那么只需重接它的左子樹(p=p-lchild;free(q);shorter=1;第14頁

16、共 38 頁平衡二叉樹的查找、插入和刪除else if(p-lchild=NULL)/左子樹空那么只需重接它的右子樹(p=p-rchild;free(q);shorter=1;else/左右子樹均不空(Delete(q,q-lchild,shorter);if(shorter=1)LeftBalance_div(p,shorter);p=q;return 1;三數(shù)據(jù)結(jié)構(gòu)本實(shí)驗(yàn)中平衡二叉樹采用二叉鏈表的方式進(jìn)行存儲(chǔ)。定義如下:typedef struct BSTNodeint data;第15頁共 38 頁平衡二叉樹的查找、插入和刪除int bf; /結(jié)點(diǎn)的平衡因子struct BSTNode

17、*lchild,*rchild;/左、右孩子指針BSTNode,*BSTree;四程序結(jié)構(gòu)與流程本程序包括四個(gè)模塊，分別為主函數(shù)、AVL的創(chuàng)立、AVL的查找函數(shù)、AVL數(shù)、AVL的刪除函數(shù)。流程圖如下:主函數(shù)void main()主函數(shù)定義如下:是插入。void main()int input,search;bool taller=false;int shorter=0;BSTree T,T1,T2;主函數(shù)主要是根據(jù)輸入的數(shù)字選擇要對平衡二叉樹進(jìn)行的操作,創(chuàng)立、查找、 刪除或者的插入函AVL的創(chuàng)立rAVL的查找AVL的插入AVL的刪除平衡二叉樹的查找、插入和刪除第16頁共 38 頁T=(BST

18、ree)malloc(sizeof(BSTNode);T=T1=T2=NULL;while(1)printf(1.創(chuàng)立t2.查找t3.插入t4.刪除t5.退出*n);printf(請輸入您所需的操作功能：t);scanf(%d,&input);getchar();switch(input)case 1:CreatBST(T); break;case 2:printf(請輸入你要查找的關(guān)鍵字);scanf(%d,&search); getchar();if(SearchBST(T,search) printf(該二叉樹 中存在關(guān)鍵字%d ,查找成 功!n,search);else

19、 printf(查找失敗!n);break;case 3:printf(請輸入你要插入的關(guān)鍵字);scanf(%d,&search); getchar();第17頁共 38 頁平衡二叉樹的查找、插入和刪除InsertAVL(T,search,taller);PrintBST(T); break;case 4:printf請輸入你要?jiǎng)h除的關(guān)鍵字;scanf(%d,&search); getchar();DeleteAVL(T,search,shorter);PrintBST(T); break;case 5:break;default:printf輸入錯(cuò)誤，請重新選擇。;brea

20、k;printf(tt按任意鍵繼續(xù).)； getchar();運(yùn)行平臺及開發(fā)工具該程序在Windows XP/07上運(yùn)行良好，使用Microsoft Visual C+ 6.0I/O格式輸入：該程序要求輸入數(shù)據(jù)為整型數(shù)據(jù)，并以-1作為輸入數(shù)據(jù)的結(jié)束標(biāo)志,輸入相同的數(shù)據(jù)只會(huì)生成一個(gè)關(guān)鍵字并給出輸入數(shù)據(jù)相同的提示。開發(fā)。創(chuàng)立過程中假設(shè)第18頁共 38 頁平衡二叉樹的查找、插入和刪除輸出：該程序?qū)τ趯ζ胶舛鏄涞妮敵霾捎弥行虮闅v的方法。因?yàn)橹行虮闅v平衡二叉樹的得到的結(jié)果肯定為有序的，所以可以據(jù)此判斷對于平衡二叉樹操作的正確性。測試數(shù)據(jù)：1、創(chuàng)立輸入數(shù)據(jù)：34、45、12、22、34、56、76、11

21、、-45、23、-1 ;進(jìn)行平衡二叉樹的創(chuàng)立，運(yùn)行結(jié)果如下列圖：成C:Program FilesMicrosoft Visual StudioMyPrajectsAVLWDebugAVLW.exe2.杏找3.插入4.fi請輸:X您所需麗操作功能：1請輸入關(guān)鍵字?以 T 結(jié)束建立平衡二叉樹?34請輸入關(guān)鍵字?以 T 結(jié)束建立平衡二叉樹?45請輸入關(guān)鍵字?以 T 結(jié)束建立平衡二叉樹?說 請輸入關(guān)鍵字?以 T 結(jié)束建立平衡二叉樹?22；字 ：34關(guān)鍵字的結(jié)點(diǎn)請輸入關(guān)鍵字以 T 結(jié)束建立平衡二叉樹:弱請輸入關(guān)鍵字以 T 結(jié)束建立平衡二叉樹2、查找查找在原有二叉樹上已存在的關(guān)鍵字:【查找23】運(yùn)行結(jié)果：

22、 |xs.退出*請輸入關(guān)鍵字以 T 結(jié)束建立平衡二叉樹HI請輸入關(guān)鍵字以 T 結(jié)束建立平衡二叉樹-45請輸入關(guān)鍵字?以 T 結(jié)束建立平衡二叉樹?23 入關(guān)鍵字?以 T 結(jié)棗建立平建二叉樹 二叉樹創(chuàng)立結(jié)束-由序遍歷卑衡二叉樹：HEi,.一一 _ 一_ _ 一 . r-45 11 12 22 23 34 45 56 76:井*li .按任意鍵繼續(xù)第19頁共 38 頁IXIX能字2323，2 23 3播功檀字來皓2222盈美樹星中只1111您你樹二建入入又加創(chuàng)輸輸二遍遍 衡二叉樹衡二叉樹. .34 4S SG4蛛 5 退出*技任楚橫維域23.奩找成功，第20頁共 38 頁4、刪除刪除在原有平衡二叉樹

23、上已存在的關(guān)鍵字:【刪除22】運(yùn)行結(jié)果如下：-45 1112 22 創(chuàng)立創(chuàng)立探出罪俏的挽K咨入你要切蛛的-4S 1112 23刪除在原有平衡二叉樹上不存在的數(shù)據(jù):平衡二叉樹的查找、插入和刪除查找在原有二叉樹上不存在的數(shù)據(jù):【查找24】運(yùn)行結(jié)果:清恿入何所耕爵置備入毋要查找 查淺失麗按任意握繼續(xù)一.3、插入在1的根底上進(jìn)行插入，分兩種情況：插入與原二叉樹關(guān)鍵字不重復(fù)的數(shù)【插入99】運(yùn)行結(jié)果如下:天孳r r插助鍵2323W作美曹2222蓄入杏需播W W 2.2.所要S S你建入入一4 3*!插入已存在原二叉樹中的數(shù)據(jù):【插入22】運(yùn)行結(jié)果如下：入熊菱萼蕾2323普字2222菌入槌WJ1關(guān)1212

24、2.2.所青建入入在務(wù)關(guān)務(wù)關(guān)4545清請己一昭.1.1按任慧健彌;線.帝ff4 4入草第21頁共 38 頁【刪除98】運(yùn)行結(jié)果如下:第22頁共 38 頁平衡二叉樹的查找、插入和刪除算法復(fù)雜度分析在平衡二叉樹上進(jìn)行查找的過程和二叉排序樹相同，因此，在查找的過程中與給定值進(jìn)行比擬的關(guān)鍵字個(gè)數(shù)不會(huì)超過數(shù)的深度。因此平衡二叉樹查找的時(shí)間復(fù)雜度主要由樹的深度決定。我們首先分析深度為h的平衡樹所具有的最少結(jié)點(diǎn)數(shù)。假設(shè)以N (h )表示深度為h的平衡樹含有的最少結(jié)點(diǎn)數(shù)，顯然，N (0) =0 , N(1)=1 ,N(2)=2，并且N(h)=N(h-1)+N( h-2)，在通過歸納法可以求出這個(gè)N(h),反之

25、，在知道n的情況我們也可以推導(dǎo)出h的最大值，所以最后可以得到在平衡二叉樹上查找的時(shí)間復(fù)雜度是T(n)=O(log2n)。同樣的插入和刪除的時(shí)間復(fù)雜度也為0(log2n)。源代碼#include #include #include #define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LH +1 /左高#define EH 0 /等高#define RH -1 /右高5勺入能字n n藹功w w字3434 2 23 3普美56 7S * LiH 除孔退出 4S6 7t 99按任意神筮建，2 21111E E你建入入45創(chuàng)票創(chuàng)票第23頁共 38 頁

26、平衡二叉樹的查找、插入和刪除#define NULL 0 typedef struct BSTNode int data;int bf; /結(jié)點(diǎn)的平衡因子BSTNode,*BSTree;struct BSTNode *lchild,*rchild;/左、右孩子指針void R_Rotate(BSTree &p); /對以*p為根的二叉排序樹作右旋處理void L_Rotate(BSTree &p); /對以*p為根的二叉排序樹作左旋處理void LeftBalance(BSTree &T); /對以指針T所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理void RightBalan

27、ce(BSTree &T);/對以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理bool InsertAVL(BSTree &T,int e,bool &taller);/插入結(jié)點(diǎn)ebool SearchBST(BSTree &T,int key);/查找元素key是否在樹T中void PrintBST(BSTree T);/按中序遍歷輸出二叉樹的元素void CreatBST(BSTree &T); /創(chuàng)立平衡二叉樹，(注意:以輸入-1為二叉樹建立的結(jié)束)void LeftBalance_div(BSTree &p,int &shorter

28、);/刪除結(jié)點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理void RightBalance_div(BSTree &p,int &shorter);/刪除結(jié)點(diǎn)時(shí)右平衡旋轉(zhuǎn)處理void Delete(BSTree q,BSTree &r,int &shorter);/刪除結(jié)點(diǎn)int DeleteAVL(BSTree &p,int x,int &shorter);/平衡二叉樹的刪除操作第24頁共 38 頁平衡二叉樹的查找、插入和刪除void main()(int input,search;bool taller=false;int shorter=0;BSTree T,T1,

29、T2;T=(BSTree)malloc(sizeof(BSTNode);T=T1=T2=NULL;while(1)(printf(1.創(chuàng)立t2.查找t3.插入t4.刪除t5.printf(請輸入您所需的操作功能:t);scanf(%d,&input);getchar();switch(input)(case 1:CreatBST(T); break;case 2:printf(請輸入你要查找的關(guān)鍵字);scanf(%d,&search); getchar();退出*n);平衡二叉樹的查找、插入和刪除第25頁共 38 頁if(SearchBST(T,search) printf(

30、該二叉樹 中存在關(guān)鍵字%d ,查找成 功!n,search);else printf(查找失敗!n);break;case 3:printf(請輸入你要插入的關(guān)鍵字);scanf(%d,&search); getchar();InsertAVL(T,search,taller);PrintBST(T); break;case 4:printf(請輸入你要?jiǎng)h除的關(guān)鍵字);scanf(%d,&search); getchar();DeleteAVL(T,search,shorter);PrintBST(T); break;case 5:break;default:printf(輸入

31、錯(cuò)誤，請重新選擇。);break;printf(tt按任意鍵繼續(xù).); getchar();第26頁共 38 頁平衡二叉樹的查找、插入和刪除/對以*p為根的二叉排序樹作右旋處理,LL型平衡旋轉(zhuǎn)法void R_Rotate(BSTree &p)(BSTree 1c;1c = p-lchild; /lc指向的*p左子樹根結(jié)點(diǎn)p-lchild = lc-rchild; /lc的右子樹掛接為*p的左子樹lc-rchild = p;p = lc; /p指向新的結(jié)點(diǎn)/對以*p為根的二叉排序樹作左旋處理，RR型平衡旋轉(zhuǎn)法void L_Rotate(BSTree &p)(BSTree rc;r

32、c = p-rchild; /rc指向的*p右子樹根結(jié)點(diǎn)p-rchild = rc-lchild; /rc的左子樹掛接為*p的右子樹rc-lchild = p;p = rc; /p指向新的結(jié)點(diǎn)第27頁共 38 頁平衡二叉樹的查找、插入和刪除/對以指針T所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，LR型平衡旋轉(zhuǎn)法void LeftBalance(BSTree &T)(BSTree lc,rd;1c = T-lchild; /lc指向*T的左子樹根結(jié)點(diǎn)switch(lc-bf) /檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理(case LH: /新結(jié)點(diǎn)插入在*T的左孩子的左子樹上，要作單右旋處理T

33、-bf = lc-bf = EH;R_Rotate(T); break;case RH: /新結(jié)點(diǎn)插入在*T的左孩子的右子樹上，要作雙旋處理rd = lc-rchild; /rd指向*T的左孩子的右子樹根switch(rd-bf) /修改*T及其左孩子的平衡因子(case LH:T-bf = RH; lc-bf = EH; break;case EH:T-bf = lc-bf = EH; break;case RH:T-bf = EH; lc-bf = LH; break;rd-bf = EH;L_Rotate(T-lchild); /對*丁的左子樹作左旋平衡處理R_Rotate(T); /對

34、*T作右旋平衡處理第28頁共 38 頁平衡二叉樹的查找、插入和刪除/對以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，RL型平衡旋轉(zhuǎn)法void RightBalance(BSTree &T)(BSTree rc,ld;rc = T-rchild; /rc指向*丁的右子樹根結(jié)點(diǎn)switch(rc-bf) /檢查*T的右子樹的平衡度，并作相應(yīng)平衡處理(case RH: /新結(jié)點(diǎn)插入在*T的右孩子的右子樹上，要作單左旋處理T-bf = rc-bf =EH;L_Rotate(T); break;case LH: /新結(jié)點(diǎn)插入在*T的右孩子的左子樹上，要作雙旋處理ld = rc-lchild; /

35、ld指向*T的右孩子的左子樹根switch(ld-bf) /修改*T及其右孩子的平衡因子(case LH: T-bf = EH; rc-bf = RH; break;case EH: T-bf = rc-bf =EH; break;case RH: T-bf = LH; rc-bf = EH; break;第29頁共 38 頁平衡二叉樹的查找、插入和刪除ld-bf = EH;R_Rotate(T-rchild);/對*丁的右子樹作左旋平衡處理L_Rotate(T); /對*丁作左旋平衡處理插入結(jié)點(diǎn)e,假設(shè)T中不存在和e相同關(guān)鍵字的結(jié)點(diǎn)，那么插入一個(gè)數(shù)據(jù)元素為e并返回1，否那么返回0bool I

36、nsertAVL(BSTree &T,int e,bool &taller)if(!T)/插入新結(jié)點(diǎn)，樹長高，置taller為trueT = (BSTree)malloc(sizeof(BSTNode);T-data = e;T-lchild = T-rchild =NULL;T-bf = EH; taller = true;elseif(EQ(e,T-data) /樹中已存在和有相同關(guān)鍵字的結(jié)點(diǎn)那么不再插入的新結(jié)點(diǎn),第30頁共 38 頁平衡二叉樹的查找、插入和刪除taller = false;printf(已存在相同關(guān)鍵字的結(jié)點(diǎn)n);return 0;if(LT(e,T-da

37、ta) /應(yīng)繼續(xù)在*T的左子樹中進(jìn)行搜索(if(!InsertAVL(T-lchild,e,taller)return 0;/未插入if(taller) /已插入到*T的左子樹中且左子樹長高(switch(T-bf) /檢查*T的平衡度(case LH: /原本左子樹比右子樹高，需要作左平衡處理LeftBalance(T);taller = false; break;case EH: /原本左子樹、右子等高，現(xiàn)因左子樹增高而使樹增高T-bf = LH;taller = true; break;case RH: /原本右子樹比左子樹高，現(xiàn)左、右子樹等高T-bf = EH;taller = fal

38、se; break;第31頁共 38 頁平衡二叉樹的查找、插入和刪除else /應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索(if(!InsertAVL(T-rchild,e,taller)return 0;/未插入if(taller) /已插入到*T的右子樹中且右子樹長高(switch(T-bf) /檢查*T的平衡度(case LH: /原本左子樹比右子樹高，現(xiàn)左、右子樹等高T-bf = EH; taller = false; break;case EH: /原本左子樹、右子等高，現(xiàn)因右子樹增高而使樹增高T-bf = RH; taller = true; break;case RH: /原本右子樹比左子樹

39、高，需要作右平衡處理RightBalance(T); taller = false; break;return 1;/InsertAVL第32頁共 38 頁平衡二叉樹的查找、插入和刪除查找元素key是否在樹T中bool SearchBST(BSTree &T,int key)(if(!T) return false;else if(EQ(key,T-data) return true;else if(LT(key,T-data) return SearchBST(T-lchild,key);else return SearchBST(T-rchild,key);/中序遍歷平衡二叉樹vo

40、id PrintBST(BSTree T)(if(T)(PrintBST(T-lchild);printf( %d ,T-data);PrintBST(T-rchild);第33頁共 38 頁平衡二叉樹的查找、插入和刪除/創(chuàng)立平衡二叉樹，(注意：以輸入-1為二叉樹建立的結(jié)束)void CreatBST(BSTree &T)(int e;bool taller=false;T = NULL;printf(n請輸入關(guān)鍵字(以-1結(jié)束建立平衡二叉樹):);scanf(%d,&e);getchar();while(e != -1)(InsertAVL(T,e,taller);print

41、f(n請輸入關(guān)鍵字(以-1結(jié)束建立平衡二叉樹):);scanf(%d,&e);getchar();taller=false;printf(平衡二叉樹創(chuàng)立結(jié)束，中序遍歷平衡二叉樹：n);if(T) PrintBST(T);else printf(這是一棵空樹.n);第34頁共 38 頁平衡二叉樹的查找、插入和刪除/刪除結(jié)點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理 void LeftBalance_div(BSTree &p,int &shorter)BSTree p1,p2;if(p-bf=1) /p結(jié)點(diǎn)的左子樹高，刪除結(jié)點(diǎn)后p的bf減1,樹變矮p-bf=0; shorter=1;結(jié)點(diǎn)左、右子樹

42、等高，刪除結(jié)點(diǎn)后p的bf減1,樹高不變p-bf=-1; shorter=0;else /p結(jié)點(diǎn)的右子樹高p1=p-rchild;/p1指向p的右子樹結(jié)點(diǎn)左、右子樹等高，刪除結(jié)點(diǎn)后p的bf為-2,進(jìn)行左旋處理,樹高不變L_Rotate(p);p1-bf=1;p-bf=-1;shorter=0;else if(p-bf=0)/pif(p1-bf=0)/p1第35頁共 38 頁應(yīng)else if(p1-bf=-1)/p1的右子樹高，左旋處理后，樹變矮(L_Rotate(p);p1-bf=p-bf=0; shorter=1;else /p1的左子樹高，進(jìn)行雙旋處理(先右旋后左旋)，樹變矮(p2=p1-l

43、child;p1-lchild=p2-rchild;p2-rchild=p1;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)(p-bf=0; p1-bf=0;else if(p2-bf=-1)(p-bf=1;p1-bf=0;else(p-bf=0;平衡二叉樹的查找、插入和刪除第36頁共 38 頁平衡二叉樹的查找、插入和刪除p1-bf=-1;p2-bf=0;P=P2； shorter=1;/刪除結(jié)點(diǎn)時(shí)右平衡旋轉(zhuǎn)處理void RightBalance_div(BSTree &p,int &shorter)(BSTree p1,p2;if(p-bf=-1)(p-bf=0; shorter=1;else if(p-bf=0)(p-bf=1; shorter=0;第37頁共 38 頁else(p1=p-lchild;if(p1-bf=0)(R_Rotate(p);p1-bf=-1; p-bf=1; shorter=0;else if(p1-bf=1)(R_Rot