【文章內(nèi)容簡介】 ype x)的功能是輸出二叉樹T中值為x的結點的所有祖先結點的值。函數(shù)的實現(xiàn)過程是通過多次調(diào)用函數(shù)BiTree Parent(BiTree T,EType x)，從其雙親結點開始輸出，逐步上升到根結點。void Ancestor(BiTree T,EType x){ BiTree p。 cout結點x的祖先為:\n。 while(p=Parent(T,x)){ x=pdata。 coutx 。} coutendl。}8．刪除子樹并釋放空間的操作（1）函數(shù)void DelBiTree(BiTree amp。T)的功能是，刪除一棵二叉樹T，并釋放所有結點所占的存儲空間。該算法的實現(xiàn)過程是，通過使用隊列作為輔助存儲空間，按層次順序遍歷的次序從根結點開始逐個釋放每個結點的存儲空間，并輸出相應結點的值。void DelBiTree(BiTree amp。T){ int f=0,r=0,n=100。 BiTree Q[100],t。 if(!(Q[r++]=T))return。 while(f!=r) { t=Q[f++]。f%=n。 if(tlchild) //如果有左孩子則左孩子入隊 { Q[r++]=tlchild。 r%=n。 } if(trchild) //如果有右孩子則右孩子入隊 { Q[r++]=trchild。 r%=n。 } cout刪除結點：tdataendl。 delete t。 } T=NULL。}（2）函數(shù)void DelSubTree(BiTree amp。T,EType x)的功能是，刪除T中以根結點值為x的子樹中的所有結點，并釋放相應的空間。void DelSubTree(BiTree amp。T,EType x){ if(!T)return。 else if(Tdata==x) //如果x為根結點則刪除整棵樹 { DelBiTree(T)。 return。 } else { DelSubTree(Tlchild,x)。 //通過遞歸調(diào)用在T的左子樹中完成刪除操作 DelSubTree(Trchild,x)。 //通過遞歸調(diào)用在T的右子樹中完成刪除操作 }}9．二叉樹基本操作演示主函數(shù)函數(shù)要求按先序遍歷全序列來創(chuàng)建二叉樹T1。其功能是：1）輸出T1的三種遍歷序列、深度、葉結點數(shù)；2）復制T1到二叉樹T2，并輸出T2的深度、以及交換T2中所有結點的左右孩子結點后，T2的三種遍歷序列和深度，并釋放T2的存儲空間；3）根據(jù)輸入的結點值x輸出T1中x的所有祖先結點的值；4）刪除T1中所有以x為根的子樹，并釋放空間。void main(){ void DelSubTree(BiTree amp。T,EType x)。 void DelBiTree(BiTree amp。T)。 BiTree T1,T2。 cout先序建立一棵二叉樹:\n。 Create_BiT(T1)。 PtTree(T1)。 cout深度為: Depth_BiT(T1)endl。 cout葉結點的個數(shù)為: Leaf_BiT(T1)endl。 T2=CopyTree(T1)。 cout復制后的二叉樹為:\n。PtTree(T2)。 cout深度為: Depth_BiT(T2)endl。 Change(T2)。 cout交換后的二叉樹T2為:\n。PtTree(T2)。 cout深度為: Depth_BiT(T2)endl。 EType x。 cout輸入結點值x:。cinx。 Ancestor(T1,x)。 cout銷毀T1中所有根為x的子樹!\n。 DelSubTree(T1,x)。 cout刪除后的T1為:\n。PtTree(T1)。 cout銷毀二叉樹T2:\n。 DelBiTree(T2)。}程序運行過程為：先序建立一棵二叉樹:ABDG**HJ**K**E**C*F*DM***先序遍歷序列為:A B D G H J K E C F D M中序遍歷序列為:G D J H K B E A C F M D后序遍歷序列為:G J K H D E B M D F C A深度為: 5葉結點的個數(shù)為: 5復制后的二叉樹為:先序遍歷序列為:A B D G H J K E C F D M中序遍歷序列為:G D J H K B E A C F M D后序遍歷序列為:G J K H D E B M D F C A深度為: 5交換后的二叉樹T2為:先序遍歷序列為:A C F D M B E D H K J G中序遍歷序列為:D M F C A E B K H J D G后序遍歷序列為:M D F C E K J H G D B A深度為: 5輸入結點值x:D↙結點D的祖先為:B A銷毀T1中所有根為D的子樹!刪除結點：D刪除結點：G刪除結點：H刪除結點：J刪除結點：K刪除結點：D刪除結點：M刪除后的T1為:先序遍歷序列為:A B E C F中序遍歷序列為:B E A C F后序遍歷序列為:E B F C A銷毀二叉樹T2:刪除結點：A刪除結點：C刪除結點：B刪除結點：F刪除結點：E刪除結點：D刪除結點：D刪除結點：H刪除結點：G刪除結點：M刪除結點：K刪除結點：J【】設計一個算法，判斷兩棵二叉樹T1和T2是否為相似二叉樹。所謂二叉樹T1和T2是相似的所指的是：T1和T2都是空二叉樹，或者T1和T2均為非空二叉樹并且T1的左子樹與T2的左子樹相似，T1的右子樹與T2的右子樹也相似。解：由于相似的概念是通過遞歸來定義的，所以本題采用遞歸調(diào)用的算法來完成兩棵二叉樹是否相似的判斷過程。算法思想是，當T1和T2的根結點、左子樹、右子樹均相似時表示T1和T2相似，此時函數(shù)返回1，否則T1和T2不相似此時函數(shù)返回0。算法實現(xiàn)如下：int LikeTree(BiTree T1,BiTree T2){ int like1,like2。 if(!T1amp。amp。!T2)return(1)。 else if(!T1||!T2)return(0)。 else { like1=LikeTree(T1lchild,T2lchild)。 like2=LikeTree(T1rchild,T2rchild)。 return(like1*like2)。 }}【】編寫遞歸算法，輸出在二叉樹的先序遍歷序列中第k個位置上的結點的值。解：本題的算法思想是，通過先序遍歷二叉樹的遞歸調(diào)用方法，在執(zhí)行過程中每訪問一次結點前先執(zhí)行操作“k?！币淮?，并判斷k的值是否為0。如果在某次訪問結點時k的值為0，那么該結點即為所求結點，輸出該結點的值結束操作。算法實現(xiàn)如下：void PreOrder_k (BiTree T,int amp。k){//由于在函數(shù)調(diào)用過程中的參數(shù)k為值傳遞是單向的，所以此處的參數(shù)k應定義為引用參數(shù)amp。k。 if(T) { k。 if(k==0){ coutTdataendl。 return。 } else { PreOrder_k(Tlchild,k)。 PreOrder_k(Trchild,k)。 } }}【】編寫按層次順序遍歷一棵二叉樹T的算法TraverseLevel(T)。解：按層次遍歷二叉樹的過程是，由根結點開始，按照從上到下從左到右的次序依次訪問樹中的每一個結點。為此，先建立一個初始僅有根結點的隊列Q，每次提取一個隊首元素，并在訪問該結點的值后將其左、右孩子結點（如果存在）依次入隊，直至隊列為空為止。其程序實現(xiàn)過程如下：void TraverseLevel(BiTree T){ int f=0,r=0,n=100。 // r 為隊尾指針,f為隊首指針，n為最大隊列長度 BiTree Q[100],t。 //Q為存放樹T中結點的隊列 if(!(Q[r++]=T))return。 while(f!=r) { t=Q[f++]。 f%=n。 //t出隊 couttdata39。 39。 //輸出t的值 if(tlchild) //如果t有左孩子則左孩子入隊 { Q[r++]=tlchild。 r%=n。 } if(trchild) //如果t有右孩子則右孩子入隊 { Q[r++]=trchild。 r%=n。 } } coutendl。}【】設計算法，判斷一棵二叉樹是否為完全二叉樹。解：判斷一棵二叉樹T是否為完全二叉樹的算法思想是，通過使用隊列輔助空間實現(xiàn)對二叉樹T的層次順序遍歷，在遍歷過程中考查每個結點的度m。如果m的值是由2到0的遞減變化過程（可以相同），其中數(shù)字1最多只能出現(xiàn)一次而且相應的結點僅有左子樹時表明二叉樹T為完全二叉樹，此時函數(shù)返回1，否則不是完全二叉樹函數(shù)返回0。算法實現(xiàn)如下：int CompleteBiTree(BiTree T){ int h=1,leaf=0,f=0,r=0,n=100。 BiTree Q[100],t。 if(!T||(!Tlchildamp。amp。!Trchild))return 1。 Q[r++]=T。 while((r!=f)amp。amp。(!leaf)) { t=Q[f++]。 f%=n。 if(tlchildamp。amp。trchild) //結點t的度為2時繼續(xù) { Q[r++]=tlchild。 r%=n。 Q[r++]=trchild。 r%=n。 } else if(tlchild) //結點t的度為1且僅有左孩子時以后均為葉結點 { Q[r++]=tlchild。 r%=n。 leaf=1。 } else if(trchild) //結點t的度為1時不能有右孩子結點 { h=0。 break。 } else leaf=1。 //結點t的度為0時以后結點的度均為0 } while(hamp。amp。(f!=r)) //在剩下的結點中均為葉結點 { t=Q[f++]。 f%=n。 if(tlchild||trchild)h=0。 } return h。}【】設計算法，通過由順序表存儲的完全二叉樹ST[n]建立該完全二叉樹的二叉鏈表結構T。解：本問題的算法思想是，通過遞歸調(diào)用的方法來逐步完成對二叉樹T中各個結點的建立操作。即先建立根結點，再依次建立根結點的左子樹根結點和右子樹的根結點，…，直至完成所有結點的建立。算法實現(xiàn)如下：void TreeSqToL(BiTreeamp。 T,EType ST[],int n,int i=1) //i為根結點的序號，n為結點總數(shù){ if(in) { T=NULL。 return。} else { T=new BiTNode。 Tdata=ST[i1]。 TreeSqToL(Tlchild,ST,n,i*2)。 TreeSqToL(Trchild,ST,n,i*2+1)。 }}【】設計一個算法，由二叉樹T的先序遍歷序列preoder[]和中序遍歷序列inoder[]來構造二叉樹T。解：根據(jù)二叉樹的遞歸定義和遍歷過程可知，在先序遍歷序列preoder[]中的第一個數(shù)據(jù)元素必為樹的根結點，根結點后面的前一部分為其左子樹的先序遍歷序列，后一部分為其右子樹的先序遍歷序列；在中序遍歷序列inoder[]中，根結點前面的元素序列為其左子樹的中序遍歷序列，而在根結點后面的元素序列為其右子樹的中序遍歷序列。所以本問題可以采用遞歸調(diào)用的方法，先建立根結點，再分別建立根結點的左子樹和右子樹。算法實現(xiàn)代碼如下：BiTree BiTreeCreate(EType* preoder,EType* inoder,int n ) { // preoder為先序首地址，inoder為中序首地址，n為結點總數(shù) BiTree T。 int k。 EType* p。 if(n1)return NULL。 T=new BiTNode。 Tdata=*preoder。 //建立根結點 for(p=inoder。pinoder+n。p++) //查找根結點在中序遍歷序列中的位置 if(*p==*preoder)break。 k=pinode