【正文】 Link s。 system(cls)。 break。:{ system(cls)。//增高標(biāo)識(shí)，1為增高，0為不增高 InsertTree(t,e,taller)。 cinn。 cink。 if(a==39。 cout endl。 InitL(l)。 return 1。 )。 )。 )。 )。/*雙向鏈表操作函數(shù)聲明*/int InitL(Linkamp。}QNode,*QP。define NAME_LENGTH 20define LH 1 //樹(shù)的左部比右部高1define EH 0 //樹(shù)的左右一般高define RH 1 //樹(shù)的右部比左部高1typedef struct Type{//數(shù)據(jù)類型結(jié)構(gòu) float num。//若該點(diǎn)為空，則它的孩子也為空，入隊(duì)列 EnQ(q,NULL)。 } if(t!=NULL){ coutt(tbf) 。} int i=0,level=0,j,num。 } } } return 1。 LeftBalance(t)。 break。 RightBalance(t)。即查找q的值 if(shorter){ switch(tbf){ case LH: tbf=EH。 t=tlchild。 t,Type e,intamp。 t=l。 } rlbf=EH。 switch(rlbf){ case LH: tbf=EH。 switch(rbf){ case RH://新節(jié)點(diǎn)插在T的右孩子的右子樹(shù)上，要做單左旋處理 tbf=rbf=EH。 lbf=LH。 break。 t){//左部平衡化處理 AVL l,lr。然而遞歸調(diào)用的過(guò)程卻是非常復(fù)雜不容易理解的，稍不留神就有可能出現(xiàn)錯(cuò)誤的調(diào)用，由于是層層遞歸，所以對(duì)函數(shù)運(yùn)行情況的跟蹤并不容易，十分容易出現(xiàn)錯(cuò)誤。 } } DeQ(q,t)。trchild==NULL){//T為空時(shí)進(jìn)行判斷，當(dāng)平衡樹(shù)中出現(xiàn)層數(shù)不同的空結(jié)點(diǎn)時(shí)，終止輸出 if(!level){//首次出現(xiàn)兩個(gè)孩子都空的結(jié)點(diǎn)，將其孩子的層數(shù)賦給level level=num+1。 while(j=i){ num++。 t2){//將樹(shù)t2合并到t1上 while(t2!=NULL){//t2不為空時(shí) InsertTree(t1,t2data,taller)。shorter=0。 RightBalance(t)。 } if(shorter){ switch(tbf){ case LH:tbf=EH。 case EH:tbf=RH。 } else{//左右子樹(shù)都存在 q=tlchild。}（5）int DeleteTree(AVLamp。//將t的左孩子給l tlchild=lrchild。break。break。break。R_Rotate(t)。 struct LNode* prior,* next。/*隊(duì)列結(jié)構(gòu)聲明*/typedef struct QNode{//隊(duì)列 AVL tree。通過(guò)平衡二叉樹(shù)，能夠使樹(shù)時(shí)刻保持平衡，從而提高在樹(shù)中遍歷數(shù)據(jù)的速度，具有重要意義。實(shí)驗(yàn)四 平衡二叉樹(shù)演示1. 問(wèn)題定義及需求分析問(wèn)題描述：利用平衡二叉樹(shù)設(shè)計(jì)動(dòng)態(tài)查找表。創(chuàng)建平衡二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，通過(guò)平衡因子，使二叉排序樹(shù)達(dá)到平衡，提供平衡二叉樹(shù)的創(chuàng)建、查找和刪除，樹(shù)中元素的查找、插入和刪除等基本功能，可以實(shí)現(xiàn)創(chuàng)建多棵平衡二叉樹(shù)，并且能夠進(jìn)行兩棵樹(shù)的合并。//左右孩子}AVLTree,*AVL。 char tree_name[NAME_LENGTH]。 case EH://deleteAVL需要，insertAVL用不著 調(diào)整平衡因子。 case RH: 調(diào)整平衡因子。L_Rotate(t)。 case EH: 調(diào)整平衡因子。 t){//以T為根節(jié)點(diǎn)的二叉排序樹(shù)進(jìn)行右旋轉(zhuǎn) l=tlchild。 t=r。 shorter=1。break。 } } } } else if(etdata){//左子樹(shù)中繼續(xù)查找 if(!DeleteTree(tlchild,e,shorter)){ return 0。 else shorter=1。 case EH:tbf=LH。 t1,AVLamp。 j=1。amp。}//用*代表空 if(j==i+1){ coutendl。遞歸調(diào)用對(duì)于平衡樹(shù)的平衡調(diào)節(jié)具有非常重要的作用，這大大減少了代碼量，并且使得代碼更加簡(jiǎn)潔。6. 測(cè)試結(jié)果（截屏）（1） 原樹(shù)t2的結(jié)構(gòu)圖：（2） t2刪除結(jié)點(diǎn)7后，層次遍歷輸出樹(shù)的結(jié)構(gòu)圖：（3） 樹(shù)t1的結(jié)構(gòu)圖：（4） 將t2合并到t1后，輸出樹(shù)的結(jié)構(gòu)圖：7. 附錄void LeftBalance(AVLamp。 R_Rotate(t)。 case RH: tbf=EH。 r=trchild。 case LH://新節(jié)點(diǎn)插在T的右孩子的左子樹(shù)上，要做雙旋處理 rl=rlchild。 break。 lrchild=t。}int DeleteTree(AVLamp。 } else if(trchild==NULL){//右子樹(shù)為空 q=t。//在左子樹(shù)中遞歸刪除前驅(qū)結(jié)點(diǎn)。 else shorter=1。 shorter=0。 else shorter=1。 break。}includeconst int PrintTreeStructure(AVL t){//利用層次遍歷，輸出樹(shù)的形狀 if(!t){return 0。//num為記層標(biāo)志，記錄當(dāng)前T所在層數(shù) j=2*j。 } } } else{ EnQ(q,NULL)。 }//while}/**/ifndef H_H_INCLUDEDdefine H_H_INCLUDEDincludeincludeincludeincludeiostreamusing namespace std。 struct QNode* next。}LNode,*Link。const int SearchL(Link ,char* ,Linkamp。 ,AVLamp。void RightBalance(AVLamp。const int SearchTree(AVL ,Type ,AVLamp。endif // H_H_INCLUDED/**/includeint main(){ Menu()。} Link l。 cout endl。} else{ a=i[0]。 int j,k。 int m,n。 int taller=0。239。 system(cls)。} system(pause)。 cinname。 cinn。 } cout插入成功！endl。 char name[NAME_LENGTH]。 int m,n。//降低表示，1為降低，0為不降低 DeleteTree(st,e,shorter)。 cout請(qǐng)輸入你想要訪問(wèn)的樹(shù)名：endl。 } if(st!=NULL){ coutstree_name樹(shù)現(xiàn)在的形狀為(39。 system(cls)。 Link s1。 if(!SearchL(l,name2,s2)){ cout未找到該名字的平衡樹(shù)！endl。 system(cls)。 Link s。 system(pause)。 break。 break。 R_Rotate(t)。 rbf=LH。 break。 t,Type e,intamp。 } if(t){//應(yīng)在T的左子樹(shù)中搜尋 if(!InsertTree(tlchild,e,taller))return 0。 taller=0。 break。//刪除失敗 } else if(==t){//找到元素結(jié)點(diǎn) AVL q=NULL。 shorter=1。 break。 } } } } else if(t){//左子樹(shù)中繼續(xù)查找 if(!DeleteTree(tlchild,e,shorter)){ return 0。 else shorter=1。 case EH: tbf=LH。 t){//遞歸銷毀二叉平衡樹(shù) if(t==NULL){ return 0。 lt=NULL。//將平衡樹(shù)的樹(shù)名保存 pnext=lnext。 return 1。 free(l)。}/**/includeconst int PrintTreeStructure(AVL t){//利用層次遍歷，輸出樹(shù)的形狀 if(!t){return 0。//num為記層標(biāo)志，記錄當(dāng)前T所在層數(shù) j=2*j。 } } } else{ EnQ(q,NULL)。 }//while}/**/include int InitQ(LinkQamp。 if(!p)return 0。 e){//出隊(duì)列 if(==)return 0。}/**/includevoid R_Rotate(AVLamp。 r=trchild