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

2、入關(guān)鍵字。創(chuàng)建時(shí)，根據(jù)提示輸入數(shù)據(jù)，以-1為輸入數(shù)據(jù)的結(jié)束標(biāo)志，若輸入數(shù)據(jù)重復(fù)，則給出已存在相同關(guān)鍵字的提示，并不將其插入到二叉樹(shù)中。在查找時(shí)，如果查找的關(guān)鍵字不存在，則顯示不存在查找的關(guān)鍵字，若存在則顯示存在要查找的關(guān)鍵字。插入時(shí)首先檢驗(yàn)原二叉樹(shù)中是否已存在相同第3頁(yè)共38頁(yè)-3-的關(guān)鍵字，若沒(méi)有則進(jìn)行插入并輸出二叉樹(shù)，若有則給出已有相同關(guān)鍵字的提醒。刪除時(shí)首先檢驗(yàn)原二叉樹(shù)中是否存在要?jiǎng)h除的關(guān)鍵字，若有則進(jìn)行刪除后并輸出二叉樹(shù)，若沒(méi)有則給出不存在要?jiǎng)h除的關(guān)鍵字的提醒。(3)平衡二叉樹(shù)的顯示采用中序遍歷的方法輸出，還可以根據(jù)輸出數(shù)據(jù)是否有序驗(yàn)證對(duì)平衡二叉樹(shù)的操作是否正確。設(shè)計(jì)說(shuō)明ADTADTB

3、alancedBinaryTree數(shù)據(jù)象D:D是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)志的數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱌:voidR_Rotate(BSTree&p);初始條件：二叉樹(shù)存在，且關(guān)鍵字插入到以*p為根的二叉樹(shù)的左子樹(shù)的左孩子上；操作結(jié)果：對(duì)以*p為根的二叉排序樹(shù)作右旋處理平衡二叉樹(shù)的查找、插入和刪除voidL_Rotate(BSTree&p);初始條件：二叉樹(shù)存在，且關(guān)鍵字插入到以*p為根的二叉樹(shù)的右子樹(shù)的右孩子上；操作結(jié)果：對(duì)以*p為根的二叉排序樹(shù)作左旋處理voidLeftBalance(BSTree&T);初始條件：

4、二叉樹(shù)存在，且關(guān)鍵字插入到T所指節(jié)點(diǎn)為根的二叉樹(shù)的左子樹(shù)的右孩子上;操作結(jié)果：又以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理voidRightBalance(BSTree&T);初始條件：二叉樹(shù)存在，且關(guān)鍵字插入到T所指節(jié)點(diǎn)為根的二叉樹(shù)的右子樹(shù)的左孩子上;操作結(jié)果：又以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理boolInsertAVL(BSTree&T,inte,bool&taller);初始條件：T存在，且e與二叉樹(shù)的原有關(guān)鍵字不同；操作結(jié)果：才1入結(jié)點(diǎn)e平且平衡化；boolSearchBST(BSTree&T,intkey);初始條件：T存在且元素key與某關(guān)鍵字相同；操作結(jié)果：查找元素

5、key是否在樹(shù)T中voidPrintBST(BSTreeT);初始條件：T存在操作結(jié)果：按中序遍歷輸出二叉樹(shù)的元素voidCreatBST(BSTree&T);初始條件：T為空操作結(jié)果：創(chuàng)建平衡二叉樹(shù),(注意:以輸入-1為二叉樹(shù)建立的結(jié)束)voidLeftBalance_div(BSTree&p,int&shorter);平衡二叉樹(shù)的查找、插入和刪除初始條件：T存在操作結(jié)果：刪除結(jié)點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理voidRightBalance_div(BSTree&p,int&shorter);初始條件：T存在操作結(jié)果：刪除結(jié)點(diǎn)時(shí)右平衡旋轉(zhuǎn)處理voidDelete(BSTreeq,BSTree&r,int

6、&shorter);初始條件：T存在且節(jié)點(diǎn)刪除成功操作結(jié)果：刪除結(jié)點(diǎn)intDeleteAVL(BSTree&p,intx,int&shorter);初始條件：操作結(jié)果：平衡二叉樹(shù)的刪除操作ADTBalancedBinaryTree(二)算法思想1、查找在根指針T所指二叉排序樹(shù)中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功,則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否則返回空指針。如果樹(shù)T為空，則查找不成功，返回空指針；當(dāng)樹(shù)T非空時(shí)，如果根指針T所指數(shù)據(jù)元素的關(guān)鍵字等于key,則查找成功，返回根指針T,否則在左子樹(shù)中繼續(xù)查找，若還未找到，則繼續(xù)在右子樹(shù)中進(jìn)行查找，直到找到該數(shù)據(jù)元素或樹(shù)T為空為止。平

7、衡二叉樹(shù)的查找、插入和刪除查找元素key是否在樹(shù)T中boolSearchBST(BSTree&T,intkey)(if(!T)returnfalse;elseif(EQ(key,T-data)returntrue;elseif(LT(key,T-data)returnSearchBST(T-lchild,key);elsereturnSearchBST(T-rchild,key);2、插入（一）若T為空樹(shù)，則插入一個(gè)數(shù)據(jù)元素為e的新節(jié)點(diǎn)作為T(mén)的根節(jié)點(diǎn)，樹(shù)長(zhǎng)高，樹(shù)的深度增加1。（二）若待插入的數(shù)據(jù)元素e與T的根節(jié)點(diǎn)的關(guān)鍵字相同，則不進(jìn)行插入。（三）若待插入的數(shù)據(jù)元素e小于根節(jié)點(diǎn)的關(guān)鍵字，且在T的

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

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

10、節(jié)點(diǎn)的平衡因子，樹(shù)的深度不變。插入結(jié)點(diǎn)e,若T中不存在和e相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1,否則返回0boolInsertAVL(BSTree&T,inte,bool&taller)(if(!T)/插入新結(jié)點(diǎn)，樹(shù)長(zhǎng)高，置taller為true(T=(BSTree)malloc(sizeof(BSTNode);T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;平衡二叉樹(shù)的查找、插入和刪除else(if(EQ(e,T-data)/樹(shù)中已存在和有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入(taller=false;printf(已存在相

11、同關(guān)鍵字的結(jié)點(diǎn)n);return0;)if(LT(e,T-data)/應(yīng)繼續(xù)在*T的左子樹(shù)中進(jìn)行搜索(if(!InsertAVL(T-lchild,e,taller)return0;/未插入if(taller)/已插入到*T的左子樹(shù)中且左子樹(shù)長(zhǎng)高(switch(T-bf)/檢查*T的平衡度(caseLH:/原本左子樹(shù)比右子樹(shù)高，需要作左平衡處理LeftBalance(T);taller=false;break;caseEH:/原本左子樹(shù)、右子等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高T-bf=LH;平衡二叉樹(shù)的查找、插入和刪除taller=true;break;caseRH:/原本右子樹(shù)比左子樹(shù)高，現(xiàn)左、

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

13、T);taller=false;break;)elseif(xdata)平衡二叉樹(shù)的查找、插入和刪除)return1;/InsertAVL3、刪除元素的刪除，有三種情況，分別是：(1)被刪除的結(jié)點(diǎn)是葉子；(2)被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)；(3)被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)。具體實(shí)現(xiàn)如下：intDeleteAVL(BSTree&p,intx,int&shorter)(intk;BSTreeq;if(p=NULL)(printf(不存在要?jiǎng)h除的關(guān)鍵字！!n);return0;在p的左子樹(shù)中進(jìn)行刪除平衡二叉樹(shù)的查找、插入和刪除k=DeleteAVL(p-lchild,x,shorte

14、r);if(shorter=1)LeftBalance_div(p,shorter);returnk;elseif(xp-data)在p的右子樹(shù)中進(jìn)行刪除(k=DeleteAVL(p-rchild,x,shorter);if(shorter=1)RightBalance_div(p,shorter);returnk;else(q=p;if(p-rchild=NULL)/右子樹(shù)空則只需重接它的左子樹(shù)(p=p-lchild;free(q);shorter=1;平衡二叉樹(shù)的查找、插入和刪除elseif(p-lchild=NULL)/左子樹(shù)空則只需重接它的右子樹(shù)(p=p-rchild;free(q);

15、shorter=1;)else/左右子樹(shù)均不空(Delete(q,q-lchild,shorter);if(shorter=1)LeftBalance_div(p,shorter);p=q;)return1;)（三）數(shù)據(jù)結(jié)構(gòu)本實(shí)驗(yàn)中平衡二叉樹(shù)采用二叉鏈表的方式進(jìn)行存儲(chǔ)。定義如下:typedefstructBSTNode（intdata;平衡二叉樹(shù)的查找、插入和刪除左、右孩子指針intbf;/結(jié)點(diǎn)的平衡因子structBSTNode*lchild,*rchild;/BSTNode,*BSTree;(四)程序結(jié)構(gòu)與流程本程序包括四個(gè)模塊，分別為主函數(shù)、AVL的創(chuàng)建、AVL的查找函數(shù)、AVL的插入函

16、數(shù)、AVL的刪除函數(shù)。流程圖如下：AVL的創(chuàng)建AVL的查找AVL的插入AVL的刪除主函數(shù)定義如下：主函數(shù)主要是根據(jù)輸入的數(shù)字選擇要對(duì)平衡二叉樹(shù)進(jìn)行的操作，創(chuàng)建、查找、刪除或者是插入。voidmain()intinput,search;booltaller=false;intshorter=0;BSTreeT,T1,T2;平衡二叉樹(shù)的查找、插入和刪除T=(BSTree)malloc(sizeof(BSTNode);T=T1=T2=NULL;while(1)printf(1.創(chuàng)建t2.查找t3.插入t4.刪除t5.退出*n);printf(請(qǐng)輸入您所需的操作功能：t);scanf(%d,&inpu

17、t);getchar();switch(input)case1:CreatBST(T);break;case 2:printf(請(qǐng)輸入你要查找的關(guān)鍵字);scanf(%d,&search);getchar();if(SearchBST(T,search)printf(該二叉樹(shù)中存在關(guān)鍵字,查找成功!n,search);elseprintf(查找失敗!n);break;case 3:printf(請(qǐng)輸入你要插入的關(guān)鍵字);scanf(%d,&search);getchar();平衡二叉樹(shù)的查找、插入和刪除InsertAVL(T,search,taller);PrintBST(T);break;c

18、ase 4:printf（請(qǐng)輸入你要?jiǎng)h除的關(guān)鍵字）;scanf(%d,&search);getchar();DeleteAVL(T,search,shorter);PrintBST(T);break;case 5:break;default:printf（輸入錯(cuò)誤，請(qǐng)重新選擇。）;break;printf(tt按任意鍵繼續(xù).);getchar();運(yùn)行平臺(tái)及開(kāi)發(fā)工具該程序在WindowsXP/07上運(yùn)行良好，使用MicrosoftVisualC+6.0I/O格式輸入：該程序要求輸入數(shù)據(jù)為整型數(shù)據(jù)，并以-1作為輸入數(shù)據(jù)的結(jié)束標(biāo)志,開(kāi)發(fā)。創(chuàng)建過(guò)程中若輸入相同的數(shù)據(jù)只會(huì)生成一個(gè)關(guān)鍵字并給出輸入數(shù)據(jù)相

19、同的提示。平衡二叉樹(shù)的查找、插入和刪除輸出：該程序?qū)τ趯?duì)平衡二叉樹(shù)的輸出采用中序遍歷的方法。因?yàn)橹行虮闅v平衡二叉樹(shù)的得到的結(jié)果肯定為有序的，所以可以據(jù)此判斷對(duì)于平衡二叉樹(shù)操作的正確性。測(cè)試數(shù)據(jù):1、創(chuàng)建輸入數(shù)據(jù)：34、45、12、22、34、56、76、11、-45、23、-1;進(jìn)行平衡二叉樹(shù)的創(chuàng)建，運(yùn)行結(jié)果如下圖:c：C:ProgramFilesMicrosoftVisualStudioMyPrajectsAVLWDebugAVLW.exe_2.查找3.插入4.刪請(qǐng)輸入您所需而操作功能：15.退出*請(qǐng)輸入關(guān)鍵字（以T結(jié)束建立平衡二叉樹(shù)）：34請(qǐng)輸入關(guān)鍵字（以T結(jié)束建立平衡二叉樹(shù)）：站請(qǐng)輸入關(guān)

20、鍵字（以T結(jié)束建立平衡二叉樹(shù)）：12請(qǐng)輸入關(guān)鍵字（以T結(jié)束建立平衡二叉樹(shù)）：22II字以-1結(jié)束建立平衡二叉樹(shù)）：34關(guān)鍵字的結(jié)點(diǎn)請(qǐng)輸入關(guān)鍵字以T結(jié)束建立平衡二叉樹(shù):56請(qǐng)輸入關(guān)鍵字以T結(jié)束建立平衡二叉樹(shù):76請(qǐng)輸入關(guān)鍵字以T結(jié)束建立平衡二叉樹(shù):口請(qǐng)輸入關(guān)鍵字以T結(jié)束建立平衡二叉樹(shù):-45請(qǐng)輸入關(guān)鍵字（以T結(jié)束建立平衡二叉樹(shù)”23入關(guān)鍵字（以T結(jié)棗建立平置二叉樹(shù)”T二叉樹(shù)創(chuàng)建結(jié)束,巾序遍歷輦衡二叉樹(shù)：HEi-451112222334455676|x2、查找查找在原有二叉樹(shù)上已存在的關(guān)鍵字:【查找23】運(yùn)行結(jié)果：接任更欖繼續(xù)23.苣找成功，IX能字23，23插動(dòng)橫字來(lái)結(jié)22屠關(guān)建找Q柱在創(chuàng)12吉

21、需胃樹(shù)2.量中X11悠能料二建人人只嶇創(chuàng)箍輸二1.清清該查理失敗，3插入4刎除5.退出舞新按任意便繼諄.一.平衡二叉樹(shù)的查找、插入和刪除查找在原有二叉樹(shù)上不存在的數(shù)據(jù):【查找24】運(yùn)行結(jié)果:3、插入在1的基礎(chǔ)上進(jìn)行插入，分兩種情況：插入與原二叉樹(shù)關(guān)鍵字不重復(fù)的數(shù)據(jù):【插入99】運(yùn)行結(jié)果如下:建人人創(chuàng)輸輸必一插功梆23-344需22畜人堂喘2.所要您你口插入已存在原二叉樹(shù)中的數(shù)據(jù):【插入22】運(yùn)行結(jié)果如下：按任更覆拒續(xù).432-2入鎮(zhèn)會(huì)插動(dòng)魯3.蜚防雷宇翳人港查一播關(guān)122.所菁你布相11建人入在4、刪除刪除在原有平衡二叉樹(shù)上已存在的關(guān)鍵字:【刪除22】運(yùn)行結(jié)果如下：-45111222.創(chuàng)建限入

22、您所需的掩搭人你要拗除的-4S111223人能于23插功梭M34*4253*24刪除在原有平衡二叉樹(shù)上不存在的數(shù)據(jù):【刪除98】運(yùn)行結(jié)果如下:*噂*平衡二叉樹(shù)的查找、插入和刪除211E你建人入45創(chuàng)富入擎nM捻動(dòng)w字343,雪鍵23需美S爵”7SQR4.蒯除5.退出才567t99技任芭神雉薄算法復(fù)雜度分析在平衡二叉樹(shù)上進(jìn)行查找的過(guò)程和二叉排序樹(shù)相同，因此，在查找的過(guò)程中與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)不會(huì)超過(guò)數(shù)的深度。因此平衡二叉樹(shù)查找的時(shí)間復(fù)雜度主要由樹(shù)的深度決定。我們首先分析深度為h的平衡樹(shù)所具有的最少結(jié)點(diǎn)數(shù)。假設(shè)以N(h)表示深度為h的平衡樹(shù)含有的最少結(jié)點(diǎn)數(shù)，顯然，N(0)=0,N(1)=1

23、,N(2)=2,并且N(h)=N(h-1)+N(h-2),在通過(guò)歸納法可以求出這個(gè)N(h),反之，在知道n的情況我們也可以推導(dǎo)出h的最大值，所以最后可以得到在平衡二叉樹(shù)上查找的時(shí)間復(fù)雜度是T(n)=O(log2n)o同樣的插入和刪除的時(shí)間復(fù)雜度也為0(log2n)。源代碼#include#include#include#defineEQ(a,b)(a)=(b)#defineLT(a,b)(a)(b)# defineLH+1/左高# defineEH0/等高# defineRH-1/右高平衡二叉樹(shù)的查找、插入和刪除# defineNULL0typedefstructBSTNodeintdata;

24、structBSTNode*lchild,*rchild;/左、右孩子指針intbf;/結(jié)點(diǎn)的平衡因子BSTNode,*BSTree;voidR_Rotate(BSTree&p);對(duì)以*p為根的二叉排序樹(shù)作右旋處理voidL_Rotate(BSTree&p);/對(duì)以*p為根的二叉排序樹(shù)作左旋處理voidLeftBalance(BSTree&T);/對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理voidRightBalance(BSTree&T);對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理boolInsertAVL(BSTree&T,inte,bool&taller);/插入結(jié)點(diǎn)eboolS

25、earchBST(BSTree&T,intkey);/查找元素key是否在樹(shù)T中voidPrintBST(BSTreeT);/按中序遍歷輸出二叉樹(shù)的元素voidCreatBST(BSTree&T);/創(chuàng)建平衡二叉樹(shù)，(注意:以輸入-1為二叉樹(shù)建立的結(jié)束)voidLeftBalance_div(BSTree&p,int&shorter);/刪除結(jié)點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理voidRightBalance_div(BSTree&p,int&shorter);刪除結(jié)點(diǎn)時(shí)右平衡旋轉(zhuǎn)處理voidDelete(BSTreeq,BSTree&r,int&shorter);刪除結(jié)點(diǎn)intDeleteAVL(BSTre

26、e&p,intx,int&shorter);平衡二叉樹(shù)的刪除操作平衡二叉樹(shù)的查找、插入和刪除voidmain()(intinput,search;booltaller=false;intshorter=0;BSTreeT,T1,T2;T=(BSTree)malloc(sizeof(BSTNode);T=T1=T2=NULL;while(1)(printf(1.創(chuàng)建t2.查找t3.插入t4.刪除t5.退出*n);printf(請(qǐng)輸入您所需的操作功能：t);scanf(%d,&input);getchar();switch(input)(case 1:CreatBST(T);break;case

27、2:printf(請(qǐng)輸入你要查找的關(guān)鍵字);scanf(%d,&search);getchar();平衡二叉樹(shù)的查找、插入和刪除if(SearchBST(T,search)printf(該二叉樹(shù)中存在關(guān)鍵字,查找成功!n,search);elseprintf(查找失敗!n);break;case 3:printf(請(qǐng)輸入你要插入的關(guān)鍵字);scanf(%d,&search);getchar();InsertAVL(T,search,taller);PrintBST(T);break;case 4:printf(請(qǐng)輸入你要?jiǎng)h除的關(guān)鍵字);scanf(%d,&search);getchar();D

28、eleteAVL(T,search,shorter);PrintBST(T);break;case 5:break;default:printf(輸入錯(cuò)誤，請(qǐng)重新選擇。);break;printf(tt按任意鍵繼續(xù).)；getchar();平衡二叉樹(shù)的查找、插入和刪除/對(duì)以*p為根的二叉排序樹(shù)作右旋處理，LL型平衡旋轉(zhuǎn)法voidR_Rotate(BSTree&p)(BSTree1c;1c=p-lchild;/lc指向的*p左子樹(shù)根結(jié)點(diǎn)p-lchild=lc-rchild;/lc的右子樹(shù)掛接為*p的左子樹(shù)lc-rchild=p;p=lc;/p指向新的結(jié)點(diǎn)/對(duì)以*p為根的二叉排序樹(shù)作左旋處理，RR

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

30、右旋處理T-bf=lc-bf=EH;R_Rotate(T);break;caseRH:/新結(jié)點(diǎn)插入在*T的左孩子的右子樹(shù)上，要作雙旋處理rd=lc-rchild;/rd指向*T的左孩子的右子樹(shù)根switch(rd-bf)/修改*T及其左孩子的平衡因子(caseLH:T-bf=RH;lc-bf=EH;break;caseEH:T-bf=lc-bf=EH;break;caseRH:T-bf=EH;lc-bf=LH;break;rd-bf=EH;L_Rotate(T-lchild);/叮的左子樹(shù)作左旋平衡處理R_Rotate(T);/X*T作右旋平衡處理平衡二叉樹(shù)的查找、插入和刪除)/對(duì)以指針T所指

31、結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理，RL型平衡旋轉(zhuǎn)法voidRightBalance(BSTree&T)(BSTreerc,ld;rc=T-rchild;/rc指向*T的右子樹(shù)根結(jié)點(diǎn)switch(rc-bf)/檢查*T的右子樹(shù)的平衡度，并作相應(yīng)平衡處理(caseRH:/新結(jié)點(diǎn)插入在*T的右孩子的右子樹(shù)上，要作單左旋處理T-bf=rc-bf=EH;L_Rotate(T);break;caseLH:/新結(jié)點(diǎn)插入在*T的右孩子的左子樹(shù)上，要作雙旋處理ld=rc-lchild;/ld指向*T的右孩子的左子樹(shù)根switch(ld-bf)/修改*T及其右孩子的平衡因子(caseLH:T-bf=EH;rc-b

32、f=RH;break;caseEH:T-bf=rc-bf=EH;break;caseRH:T-bf=LH;rc-bf=EH;break;)的新結(jié)點(diǎn),平衡二叉樹(shù)的查找、插入和刪除ld-bf=EH;R_Rotate(T-rchild);/X*T的右子樹(shù)作左旋平衡處理L_Rotate(T);/X*T作左旋平衡處理插入結(jié)點(diǎn)e,若T中不存在和e相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為e并返回1,否則返回0boolInsertAVL(BSTree&T,inte,bool&taller)if(!T)/插入新結(jié)點(diǎn)，樹(shù)長(zhǎng)高，置taller為trueT=(BSTree)malloc(sizeof(BSTNode);

33、T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;elseif(EQ(e,T-data)/樹(shù)中已存在和有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入平衡二叉樹(shù)的查找、插入和刪除taller=false;printf(已存在相同關(guān)鍵字的結(jié)點(diǎn)n);return0;)if(LT(e,T-data)/應(yīng)繼續(xù)在*T的左子樹(shù)中進(jìn)行搜索(if(!InsertAVL(T-lchild,e,taller)return0;/未插入if(taller)/已插入到*T的左子樹(shù)中且左子樹(shù)長(zhǎng)高(switch(T-bf)/檢查*T的平衡度(caseLH:/原本左子樹(shù)比右子樹(shù)高，需要作左平

34、衡處理LeftBalance(T);taller=false;break;caseEH:/原本左子樹(shù)、右子等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高T-bf=LH;taller=true;break;caseRH:/原本右子樹(shù)比左子樹(shù)高，現(xiàn)左、右子樹(shù)等高T-bf=EH;taller=false;break;)平衡二叉樹(shù)的查找、插入和刪除)else/應(yīng)繼續(xù)在*T的右子樹(shù)中進(jìn)行搜索(if(!InsertAVL(T-rchild,e,taller)return0;/未插入if(taller)/已插入到*T的右子樹(shù)中且右子樹(shù)長(zhǎng)高(switch(T-bf)/檢查*T的平衡度(caseLH:/原本左子樹(shù)比右子樹(shù)高，現(xiàn)

35、左、右子樹(shù)等高T-bf=EH;taller=false;break;caseEH:/原本左子樹(shù)、右子等高，現(xiàn)因右子樹(shù)增高而使樹(shù)增高T-bf=RH;taller=true;break;caseRH:/原本右子樹(shù)比左子樹(shù)高，需要作右平衡處理RightBalance(T);taller=false;break;)return1;/InsertAVL平衡二叉樹(shù)的查找、插入和刪除查找元素key是否在樹(shù)T中boolSearchBST(BSTree&T,intkey)(if(!T)returnfalse;elseif(EQ(key,T-data)returntrue;elseif(LT(key,T-data

36、)returnSearchBST(T-lchild,key);elsereturnSearchBST(T-rchild,key);/中序遍歷平衡二叉樹(shù)voidPrintBST(BSTreeT)(if(T)(PrintBST(T-lchild);printf(%d,T-data);PrintBST(T-rchild);平衡二叉樹(shù)的查找、插入和刪除創(chuàng)建平衡二叉樹(shù)，(注意：以輸入-1為二叉樹(shù)建立的結(jié)束)voidCreatBST(BSTree&T)(inte;booltaller=false;T=NULL;printf(n請(qǐng)輸入關(guān)鍵字(以-1結(jié)束建立平衡二叉樹(shù)):);scanf(%d,&e);getc

37、har();while(e!=-1)(InsertAVL(T,e,taller);printf(n請(qǐng)輸入關(guān)鍵字(以-1結(jié)束建立平衡二叉樹(shù)):);scanf(%d,&e);getchar();taller=false;printf(平衡二叉樹(shù)創(chuàng)建結(jié)束，中序遍歷平衡二叉樹(shù)：n);if(T)PrintBST(T);elseprintf(這是一棵空樹(shù).n);平衡二叉樹(shù)的查找、插入和刪除/刪除結(jié)點(diǎn)時(shí)左平衡旋轉(zhuǎn)處理voidLeftBalance_div(BSTree&p,int&shorter)BSTreep1,p2;if(p-bf=1)/p結(jié)點(diǎn)的左子樹(shù)高，刪除結(jié)點(diǎn)后p的bf減1,樹(shù)變矮p-bf=0;sh

38、orter=1;elseif(p-bf=0)/p結(jié)點(diǎn)左、右子樹(shù)等高，刪除結(jié)點(diǎn)后p的bf減1,樹(shù)高不變p-bf=-1;shorter=0;else/p結(jié)點(diǎn)的右子樹(shù)高p1=p-rchild;/p1指向p的右子樹(shù)if(p1-bf=0)/p1結(jié)點(diǎn)左、右子樹(shù)等高，刪除結(jié)點(diǎn)后p的bf為-2,進(jìn)行左旋處理,樹(shù)高不變L_Rotate(p);p1-bf=1;p-bf=-1;shorter=0;平衡二叉樹(shù)的查找、插入和刪除)elseif(p1-bf=-1)/p1的右子樹(shù)高，左旋處理后，樹(shù)變矮(L_Rotate(p);p1-bf=p-bf=0;shorter=1;)else/p1的左子樹(shù)高，進(jìn)行雙旋處理(先右旋后左

39、旋),樹(shù)變矮(p2=p1-lchild;p1-lchild=p2-rchild;p2-rchild=p1;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)(p-bf=0;p1-bf=0;)elseif(p2-bf=-1)(p-bf=1;p1-bf=0;)else(p-bf=0;平衡二叉樹(shù)的查找、插入和刪除p1-bf=-1;)p2-bf=0;P=P2；shorter=1;/刪除結(jié)點(diǎn)時(shí)右平衡旋轉(zhuǎn)處理voidRightBalance_div(BSTree&p,int&shorter)(BSTreep1,p2;if(p-bf=-1)(p-bf=0;shorter=1;)elseif(p-bf=0)(p-bf=1;shorter=0;)p-lchild=p2-rchild;平衡二叉樹(shù)的查找、插入和刪除else(p1=p-lchild;if(p1-bf=0)(R_Rotate(p);p1-bf=-1;p-bf=1;shorter=0;elseif(p1-bf=1)(R_Rotate(p);p1-bf=p-b