二叉樹(shù)習(xí)題集(answer)

1、空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。（應(yīng)當(dāng)是二叉排序樹(shù)的特點(diǎn)）、下面是有關(guān)二叉樹(shù)的敘述，請(qǐng)判斷正誤（）若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有 n 1個(gè)非空指針域。二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)（若存在的話）.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹(shù)的深度。（應(yīng)2i-1 ）i層上最多能有2i 1個(gè)結(jié)點(diǎn)。（應(yīng)2i-1）二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，則不存在非空右子樹(shù)。對(duì)于一棵非空二叉樹(shù)，它的根結(jié)

2、點(diǎn)作為第一層，則它的第用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的 2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹(shù)中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針。）即有后繼鏈接的指針僅 n-1個(gè)。（V ） 10.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)=n/2=6，再求n2=n 0-1=5二、填空（）1 .由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有5 種形態(tài)。2.一棵深度為6的滿二叉樹(shù)有n1+ n 2=0+ n 2= n o-1=

3、31個(gè)分支結(jié)點(diǎn)和 26-1 =32 個(gè)葉子。注：滿二叉樹(shù)沒(méi)有度為 1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。一棵具有2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為注：用 log 2(n) +1= 8.xx +1 =94.設(shè)一棵完全二叉樹(shù)有 700個(gè)結(jié)點(diǎn)，則共有350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=n/2 = 3505.設(shè)一棵完全二叉樹(shù)具有 1000個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有500 個(gè)葉子結(jié)點(diǎn),有 499 個(gè)度為2的結(jié)點(diǎn)，有 1 個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。答：最快方法：用葉子數(shù)=n/2=500 , n2=n 0-1=499 。 另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所

4、以有1個(gè)非空左子樹(shù)。完全二叉樹(shù)的特點(diǎn)決定不可能有左空右不空的情況,所以非空右子樹(shù)數(shù)=0.6. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù),可能達(dá)到的最大深度為n ，最小深度為 2 。答：當(dāng)k=1（單叉樹(shù)）時(shí)應(yīng)該最深,深度=n （層）；當(dāng)k=n-1 （n-1叉樹(shù)）時(shí)應(yīng)該最淺，深度= 2 （層），但不包括n=0或1時(shí)的特例情況。教材答案是“完全 k叉樹(shù)”，未定量。7.二叉樹(shù)的基本組成部分是：根（ N ）、左子樹(shù)（L）和右子樹(shù)（R）。因而二叉樹(shù)的遍歷次序有六種。最常用的是三種：前序法（即按 N L R次序），后序法（即按法，即按L N R次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹(shù)的前序序列是 BEFCGDH，

5、中序序列是FEBGCHD，則它的后序序列必是解：法1:先由已知條件畫(huà)圖，再后序遍歷得到結(jié)果;次序）和中序法（也稱對(duì)稱序root，由中序先確定左法2 :不畫(huà)圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定子樹(shù)。例如，前序遍歷 BEFCGDH中，根結(jié)點(diǎn)在最前面，是 B ;則后序遍歷中B 一定在最后面。，則在后序中法3 :遞歸計(jì)算。如B在前序序列中第一，中序中在中間(可知左右子樹(shù)上有哪些元素)必為最后。如法對(duì) B的左右子樹(shù)同樣處理，則問(wèn)題得解。8.中序遍歷的遞歸算法平均空間復(fù)雜度為0(n) o答：即遞歸最大嵌套層數(shù)， 即棧的占用單元數(shù)。 精確值應(yīng)為樹(shù)的深度 k+1 ,包括葉子的空域也遞歸了

6、一次。9.用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼(Huffman )樹(shù)的帶權(quán)路徑長(zhǎng)度是33 o解：先構(gòu)造哈夫曼樹(shù)，得到各葉子的路徑長(zhǎng)度之后便可求出WPL =( 4 + 5 + 3)X2 +( 1 + 2 )X3=33/(15K(9)(注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一)(注：合并值應(yīng)排在葉子值之后)(注：原題為選擇題:A. 32B. 33C. 34D. 15 )三、單項(xiàng)選擇題()(C ) 1 .不含任何結(jié)點(diǎn)的空樹(shù)是一棵樹(shù)；(B) 是一棵二叉樹(shù)；是一棵樹(shù)也是一棵二叉樹(shù)(D)既不是樹(shù)也不是二叉樹(shù)答：以前的標(biāo)答是B,因?yàn)槟菚r(shí)樹(shù)的定義是n >1(C ) 2 二叉樹(shù)

7、是非線性數(shù)據(jù)結(jié)構(gòu)，所以(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)(B)它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)(C) 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)(D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用(D ) log 2(n)+1它們與含義不同!注2 :選(A )是錯(cuò)誤的。例如當(dāng) n為2的整數(shù)幕時(shí)就會(huì)少算一層。似乎log 2(n) +1 是對(duì)的?(C ) 3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(A) log 2(n)(B ) log 2(n)(C ) log 2(n) +1表示不小于x的最小整數(shù)； x表示不大于x的最大整數(shù),6.從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄4

8、.把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是(B)有多種(A)唯一的(C)有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子(D) 有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子5.從供選擇的答案中，選出應(yīng)填入下面敘述內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。樹(shù)是結(jié)點(diǎn)的有限集合，它A_根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為 m (m >0 )個(gè)_B的集合T1 , T2，Tm，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)(1 <i <m )。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的供選擇的答案A :有0個(gè)或有0個(gè)或多個(gè)有且只有1個(gè)有1個(gè)或1個(gè)以上B:互不相交允許相交允許葉結(jié)點(diǎn)相交允許樹(shù)枝結(jié)點(diǎn)相交C: 權(quán)維數(shù)

9、次數(shù)(或度)答案：ABC = 1 , 1 , 3內(nèi)。二叉樹(shù)A 。在完全的二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有B，則它必定是葉結(jié)點(diǎn)。每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。 由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里， 一個(gè)結(jié)點(diǎn)N的左子女是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的C而N的右子女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的供選擇的答案A :是特殊的樹(shù)不是樹(shù)的特殊形式是兩棵樹(shù)的總稱有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)B:左子結(jié)點(diǎn) 右子結(jié)點(diǎn)左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)兄弟CD :最左子結(jié)點(diǎn)最右子結(jié)點(diǎn)最鄰近的右兄弟最鄰近的左兄弟最左的兄弟最右的兄弟答案：A=B=C=答案：ABCDE = 2 , 1 , 1 , 3四、簡(jiǎn)答題()1. 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別?答：度

10、為2的樹(shù)從形式上看與二叉樹(shù)很相似，但它的子樹(shù)是無(wú)序的，而二叉樹(shù)是有序的。即，在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而在二叉樹(shù)中即使是一個(gè)孩子也有左右之分。2.設(shè)如下圖所示的二叉樹(shù) B的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，root為根指針,結(jié)點(diǎn)結(jié)構(gòu)為：(lchild,data,rchild )。其中l(wèi)child , rchild 分別為指向C的結(jié)點(diǎn)類型定義如下：struct nodechar data;struct node * Ichild, rchild;左右孩子的指針，data為字符型，root為根指針，試回答下列問(wèn)題:1.對(duì)下列二叉樹(shù) B，執(zhí)行下列算法traversal(root)，試指

11、出其輸出結(jié)果;C算法如下：void traversal(struct node *root) if (root)printf(“ c -,>daa);traversal(root->lchild); printf(“ c ->data);traversal(root->rchild);2.假定二叉樹(shù)B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù)雜度。(共8 分)二叉樹(shù)B/AZB、CF GE解：這是“先根再左再根再右”，比前序遍歷多打印各結(jié)點(diǎn)一次，輸出結(jié)果為:A B C C E E B A D F F D G特點(diǎn)：每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次；但出現(xiàn)的順序

12、不同，其規(guī)律是：凡是有左子樹(shù)的結(jié)點(diǎn)，必間隔左子樹(shù)的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；如A，B，D等結(jié)點(diǎn)。反之馬上就會(huì)重復(fù)出現(xiàn)。如C，E, F, G等結(jié)點(diǎn)。時(shí)間復(fù)雜度以訪問(wèn)結(jié)點(diǎn)的次數(shù)為主，精確值為2*n，時(shí)間漸近度為 0(n).3.給定二叉樹(shù)的兩種遍歷序列，分別是:前序遍歷序列： D，A，C，E，B，H，F(xiàn)，G，I ； 中序遍歷序列： D，C，B, E，H，A，G，I，F(xiàn)，試畫(huà)出二叉樹(shù) B，并簡(jiǎn)述由任意二叉樹(shù) B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定r

13、oot的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。4.給定如圖所示二叉樹(shù)T,請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù)。解：要遵循中序遍歷的軌跡來(lái)畫(huà)出每個(gè)前驅(qū)和后繼。中序遍歷序列:5540256028083354405N60 085455五、閱讀分析題（）1. 試寫(xiě)出如圖所示的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答: DLR : A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD: J F K G D B H L M I E C A2.(P60 4-27 )把如圖所示的樹(shù)轉(zhuǎn)化成二叉樹(shù)。

14、HADHM答：注意全部兄弟之間都要連線 （包括度為2的兄弟），并注意原有連線結(jié)點(diǎn)一律歸入左子樹(shù)，新添連線結(jié)點(diǎn)一律歸入右子樹(shù)。3./ 應(yīng)改 為答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)誤。注：當(dāng)rtag= 1時(shí)說(shuō)明內(nèi)裝后繼指針，可 直接返回，第一句無(wú)錯(cuò)。當(dāng)rtag= 0時(shí)說(shuō)明內(nèi)裝右孩子指針，但孩 子未必是后繼，需要計(jì)算。中序遍歷應(yīng)當(dāng) 先左再根再右，所以應(yīng)當(dāng)找左子樹(shù)直到葉 子處。r=r->lchild; 直到 LTag=1; 閱改下列算法"若>錯(cuò)皺正之。child;BiTree In Succ(BiTree q)/已知q是指向中序線索二叉樹(shù)上某個(gè)結(jié)點(diǎn)的指針, 本函數(shù)返回指向*q的后

15、繼的指針。r=q->rchild;/應(yīng)改為 r=q ；if(!r->rtag)while(!r->rtag)r=r->rchild;while(!r->Ltag) r=r->Lchild;return r;應(yīng)改為 return r->rchild ；4. 畫(huà)出和下列二叉樹(shù)相應(yīng)的森林。答：注意根右邊的子樹(shù)肯定是森林,而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。int LeafCou nt_BiTree(Bitree T)/求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目六、算法設(shè)計(jì)題()1.編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。解：思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷遞歸算法，凡是左

16、右指針均空者，則為葉子，將其打 印出來(lái)。法一：核心部分為:DLR(liuyu *root)/*中序遍歷遞歸函數(shù)*/if(root!=NULL)if(root->lchild=NULL)&&(root->rchild=NULL)sum+; prin tf(”dn",root->data);DLR(root->lchild);DLR(root->rchild); return(O);法二:if(!T) return 0; /空樹(shù)沒(méi)有葉子else if(!T->lchild&&!T->rchild) return 1

17、; /葉子結(jié)點(diǎn)else return Leaf_Cou nt(T->lchild)+Leaf_Cou nt(T->rchild);/左子樹(shù)的葉子數(shù)加上右子樹(shù)的葉子數(shù)/LeafCou nt_BiTree注：上機(jī)時(shí)要先建樹(shù)！例如實(shí)驗(yàn)二的方案一。 打印葉子結(jié)點(diǎn)值（并求總數(shù)）思路：先建樹(shù)，再?gòu)谋闅v過(guò)程中打印結(jié)點(diǎn)值并統(tǒng)計(jì)。步驟1 鍵盤輸入序列12，8 , 17, 11 ,16，2,13，9，21，4，構(gòu)成一棵二叉排序樹(shù)。葉子結(jié)點(diǎn)值應(yīng)該是4，9, 13, 21,總數(shù)應(yīng)該是 4.121116 2113編程：生成二叉樹(shù)排序樹(shù)之后，再中序遍歷排序查找結(jié)點(diǎn)的完整程序如下:說(shuō)明部分為:#in clude

18、 <stdio.h>#in clude <stdlib.h>typ edef struct liuyui nt data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;int m=sizeof(test);void insert_data(int x)/* 如何生成二叉排序樹(shù)？參見(jiàn)教材 P43C 程序 */ liuyu *p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)root=s;

19、return; p=root;while(p)/* 如何接入二叉排序樹(shù)的適當(dāng)位置 */q=p;if(p->data=x)printf("data already exist! n");return;else p=p->rchild;else if(x<p->data)p=p->lchild;if(x<q->data)q->lchild=s;else q->rchild=s;DLR(liuyu *root)/* 中序遍歷 遞歸函數(shù) */if(root!=NULL)if(root->lchild=NULL)&&

20、amp;(root->rchild=NULL)sum+; printf("%dn",root->data);DLR(root->lchild);DLR(root->rchild); return(0);main()/* 先生成二叉排序樹(shù)，再調(diào)用中序遍歷遞歸函數(shù)進(jìn)行排序輸出*/int i,x;i=1;root=NULL;/* 千萬(wàn)別忘了賦初值給 root!*/doprintf("please input data%d:",i);i+;scanf("%d",&x);/* 從鍵盤采集數(shù)據(jù)，以 -9999 表示

21、輸入結(jié)束 */if(x=-9999)DLR(root);printf("nNow output count value:%dn",sum);return(0); else insert_data(x);/* 調(diào)用插入數(shù)據(jù)元素的函數(shù) */while(x!=-9999);return(0);input input input input input input input input input input inputdBtfll；12 data?:B dataS!IT detaMJlclBtae；2 clataT：13!9cJata1O：M若一開(kāi)始運(yùn)行就輸入-9999，則無(wú)葉

22、子輸出,sum=0 。please pleasepitas* picas? pleadspltB9»431321Noli output count Ualu#:4 執(zhí)行結(jié)果:()2. 寫(xiě)出求二叉樹(shù)深度的算法，先定義二叉樹(shù)的抽象數(shù)據(jù)類型。編寫(xiě)遞歸算法，求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。1 ;否則函數(shù)返回。答；設(shè)計(jì)思路：只查后繼鏈表指針，若左或右孩子的左或右指針?lè)强?，則層次數(shù)加但注意，遞歸時(shí)應(yīng)當(dāng)從葉子開(kāi)始向上計(jì)數(shù)，否則不易確定層數(shù)。int dep th(liuyu*root)/*統(tǒng)計(jì)層數(shù)*/int d,p;/*注意每一層的局部變量d,p都是各自獨(dú)立的*/p=0；if(root

23、=NULL)return( p);/*找到葉子之后才開(kāi)始統(tǒng)計(jì)*/elsed=de pth(root->lchild);if(d> p) p=d;/*向上回朔時(shí)，要挑出左右子樹(shù)中的相對(duì)大的那個(gè)深度值*/d=de pth(root->rchild);if(d> p)p=d;p=p+1;return(p);法二：int Get_Sub_Depth(Bitree T,int x)/求二叉樹(shù)中以值為 x 的結(jié)點(diǎn)為根的子樹(shù)深度if(T->data=x)printf("%dn",Get_Depth(T); / 找到了值為 x 的結(jié)點(diǎn) ,求其深度exit 1;

24、else在左右子樹(shù)中繼續(xù)尋找if(T->lchild) Get_Sub_Depth(T->lchild,x);if(T->rchild) Get_Sub_Depth(T->rchild,x); /Get_Sub_Depth int Get_Depth(Bitree T)/ 求子樹(shù)深度的遞歸算法if(!T) return 0;elsem=Get_De pth(T->lchild);n=Get_De pth(T->rchild);return (m>n?m:n )+1;/Get_De pth附：上機(jī)調(diào)試過(guò)程步驟1 鍵盤輸入 序列12，8，17, 11，16

25、，2，13，9，21，4，構(gòu)成一棵二叉排序樹(shù)。層數(shù)應(yīng)當(dāng)為4128172 11 16 214913步驟2:執(zhí)行求深度的函數(shù)，并打印統(tǒng)計(jì)出來(lái)的深度值。完整程序如下:#in clude <stdio.h>#in clude <stdlib.h> typ edef struct liuyui nt data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;i nt m=sizeof(test);void in sert_data(i nt x)/*如何生成二叉排序樹(shù)？參見(jiàn)教材P43C程序*/ liuyu *p ,*

26、q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)root=s; return;p=root;while(p)/* 如何接入二叉排序樹(shù)的適當(dāng)位置*/q=p;if(p->data=x)printf("data already exist! n");return;else p=p->rchild;else if(x<p->data)p=p->lchild;if(x<q->data)q->lchild=s;else q-

27、>rchild=s;int depth(liuyu*root)/* 統(tǒng)計(jì)層數(shù) */int d,p;/* 注意每一層的局部變量 d,p都是各自獨(dú)立的 */p=0;if(root=NULL)return(p);/* 找到葉子之后才開(kāi)始統(tǒng)計(jì)*/elsed=depth(root->lchild);if(d>p) p=d;/* 向上回朔時(shí)，要挑出左右子樹(shù)中的相對(duì)大的那個(gè)深度值*/d=depth(root->rchild);if(d>p)p=d;p=p+1;return(p);void main()/* 先生成二叉排序樹(shù)，再調(diào)用深度遍歷遞歸函數(shù)進(jìn)行統(tǒng)計(jì)并輸出*/int i,x

28、;i=1;root=NULL;/* 千萬(wàn)別忘了賦初值給root!*/doprintf("please input data%d:",i);i+;scanf("%d",&x);/* 從鍵盤采集數(shù)據(jù)，以 -9999 表示輸入結(jié)束 */if(x=-9999)printf("nNow output depth value=%dn", depth (root); return; while(x!=-9999);else insert_data(x);/* 調(diào)用插入數(shù)據(jù)元素的函數(shù) */return;執(zhí)行結(jié)果：plMC«plAAf

29、l*pl«415«plee«pleaseinput input input input input input irpMt input input input inputdaital 1 data2； dAtA3dotflS； 如aC dataS； datdS： dataie： datall :-Iph,Mom output cl»pth3. 編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法?；颍喊磳哟屋敵龆鏄?shù)中所有結(jié)點(diǎn);解：思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好辦法。這是一個(gè)循環(huán)算法，用while語(yǔ)句不斷循環(huán)，直到隊(duì)空

30、之后自然退出該函數(shù)。技巧之處：當(dāng)根結(jié)點(diǎn)入隊(duì)后，會(huì)自然使得左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又會(huì)立即使得它的左右孩子結(jié)點(diǎn)入隊(duì),以此產(chǎn)生了按層次輸出的效果。level(liuyu*T)/* liuyu *T,* p,*q100;假設(shè)max已知*/f=0; r=0;qr=T;while(f!=r)/*隊(duì)列不空*/int f,r;/*置空隊(duì)*/r=(r+1)%max;/*根結(jié)點(diǎn)進(jìn)隊(duì)*/prin tf("%d", p->data);/*打印根結(jié)點(diǎn)*/f=(f+1%max);p=qf;/*出隊(duì)*/if(p->lchild)r=(r+1)%max; qr=p->lchi

31、ld;/* 若左子樹(shù)不空，則左子樹(shù)進(jìn)隊(duì)*/if(p->rchild)r=(r+1)%max; qr=p->rchild;/* 若右子樹(shù)不空，則右子樹(shù)進(jìn)隊(duì) */return(0);法二：void LayerOrder(Bitree T)/層序遍歷二叉樹(shù)InitQueue(Q); / 建立工作隊(duì)列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild);/LayerOrde

32、r可以用前面的函數(shù)建樹(shù)，然后調(diào)用這個(gè)函數(shù)來(lái)輸出。完整程序如下（已上機(jī)通過(guò)）#include <stdio.h> #include <stdlib.h> #define max 50 typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root,*p,*qmax;int sum=0;int m=sizeof(test);void insert_data(int x)/* 如何生成二叉排序樹(shù)？參見(jiàn)教材 P43C 程序 */ liuyu *p,*q,*s;s=(test*)malloc(m

33、);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)root=s; return;p=root;while(p)/* 如何接入二叉排序樹(shù)的適當(dāng)位置 */q=p;if(p->data=x)printf("data already exist! n");return;else p=p->rchild;else if(x<p->data)p=p->lchild;if(x<q->data)q->lchild=s;else q->rchild=s;level(li

34、uyu*T)/* liuyu *T,*p,*q100;假設(shè) max 已知 */int f,r;f=0; r=0;/* 置空隊(duì) */r=(r+1)%max;qr=T;while(f!=r)/* 隊(duì)列不空 */* 根結(jié)點(diǎn)進(jìn)隊(duì) */printf("%d",p->data);/* 打印根結(jié)點(diǎn)*/if(p->lchild)r=(r+1)%max; qr=p->lchild;/* 若左子樹(shù)不空，則左子樹(shù)進(jìn)隊(duì) */if(p->rchild)r=(r+1)%max; qr=p->rchild;/* 若右子樹(shù)不空，則右子樹(shù)進(jìn)隊(duì) */f=(f+1%max);p=q

35、f;/* 出隊(duì) */return(0);void main()/* 先生成二叉排序樹(shù)，再調(diào)用深度遍歷遞歸函數(shù)進(jìn)行統(tǒng)計(jì)并輸出*/int i,x;i=1;doprintf("please input data%d:",i);i+;scanf("%d",&x);/* 從鍵盤采集數(shù)據(jù)，以 -9999 表示輸入結(jié)束 */if(x=-9999)printf("nNow output data value:n", level(root); return; else insert_data(x);/* 調(diào)用插入數(shù)據(jù)元素的函數(shù) */while(x!=-9999);return;4. 已知一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)被順序存儲(chǔ)于一維數(shù)組 A 中，試編寫(xiě)一個(gè)算法打印出編號(hào)為 i 的結(jié)null 的情況。點(diǎn)的雙親和所有的孩子。答：首先， 由于是完全二