數(shù)據(jù)結(jié)構(gòu) 第6章習(xí)題答案

1、第6章 樹和二叉樹 習(xí)題解答一、下面是有關(guān)二叉樹的敘述，請(qǐng)判斷正誤（每小題1分，共10分）（ ）1. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n1個(gè)非空指針域。（ ）2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。 （ ）3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。 （ ）4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。 （ ）5.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （應(yīng)當(dāng)是二叉排序樹的特點(diǎn)）（ ）6.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。（應(yīng)2i-1） （ ）7.二叉

2、樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。 （ ）8.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i1個(gè)結(jié)點(diǎn)。（應(yīng)2i-1）（ ）9.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針。）即有后繼鏈接的指針僅n-1個(gè)。（ ）10. 01年考研題具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)n/26，再

3、求n2=n0-1=5 二、填空（每空1分，共15分）1 由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 5 種形態(tài)。 2. 【計(jì)算機(jī)研2000】 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個(gè)分支結(jié)點(diǎn)和 26-1 =32 個(gè)葉子。注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。3 一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 9 。（ 注：用 log2(n) +1= 8.xx +1=94. 【全國專升本統(tǒng)考題】設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有 350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)n/2350 5. 設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有 500 個(gè)葉子結(jié)點(diǎn)，有

4、 499 個(gè)度為2的結(jié)點(diǎn)，有 1 個(gè)結(jié)點(diǎn)只有非空左子樹，有 0 個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)n/2500 ，n2=n0-1=499。 另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)0.6. 【嚴(yán)題集6.7】 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為 n ，最小深度為 2 。答：當(dāng)k=1(單叉樹)時(shí)應(yīng)該最深，深度n（層）；當(dāng)k=n-1（n-1叉樹）時(shí)應(yīng)該最淺，深度2（層），但不包括n=0或1時(shí)的特例情況。教材答案是“完全k叉樹”，未定量。)7. 【試題1】 二叉樹的基本組成部分是：根（N）

5、、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按N L R次序），后序法（即按 L R N 次序）和中序法（也稱對(duì)稱序法，即按L N R次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 F E G H D C B 。 解：法1：先由已知條件畫圖，再后序遍歷得到結(jié)果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹。例如，前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計(jì)算。如B在前序序列中第一，中序

6、中在中間（可知左右子樹上有哪些元素），則在后序中必為最后。如法對(duì)B的左右子樹同樣處理，則問題得解。8.【全國專升本統(tǒng)考題】中序遍歷的遞歸算法平均空間復(fù)雜度為 O(n) 。答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹的深度k+1，包括葉子的空域也遞歸了一次。9. 【計(jì)算機(jī)研2001】 用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度是 33 。解：先構(gòu)造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL（453）2（12）3=33 (15)(9) (6) （注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一） 4 5 3 (3) （注：合并值應(yīng)排在

7、葉子值之后）1 2（注：原題為選擇題：32 33 34 15）三、單項(xiàng)選擇題（每小題1分，共11分）（ C ）1 不含任何結(jié)點(diǎn)的空樹 。（）是一棵樹; （）是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹答：以前的標(biāo)答是B，因?yàn)槟菚r(shí)樹的定義是n1（ C ）2二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。（）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); （）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 （ C ）3. 01年計(jì)算機(jī)研題 具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。() log2(n) () log2(n) () log2(n

8、) +1 () log2(n)+1注1：x 表示不小于x的最小整數(shù)； x表示不大于x的最大整數(shù)，它們與 含義不同！注2：選（A）是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)冪時(shí)就會(huì)少算一層。似乎 log2(n) +1是對(duì)的？（ A ）4把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。（）唯一的 （）有多種（）有多種，但根結(jié)點(diǎn)都沒有左孩子 （）有多種，但根結(jié)點(diǎn)都沒有右孩子5. 【P11】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。樹是結(jié)點(diǎn)的有限集合，它A 根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m0）個(gè) B 的集合T1，T2，Tm，每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的

9、父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1im）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 C 。供選擇的答案A： 有0個(gè)或1個(gè) 有0個(gè)或多個(gè) 有且只有1個(gè) 有1個(gè)或1個(gè)以上 B: 互不相交 允許相交 允許葉結(jié)點(diǎn)相交 允許樹枝結(jié)點(diǎn)相交C： 權(quán) 維數(shù) 次數(shù)（或度） 序答案：ABC1，1，36. 【P13】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。二叉樹 A 。在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒有 B ，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個(gè)結(jié)點(diǎn)N的左子女是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)的 C ，而N的右子女是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)的 D 。供

10、選擇的答案A： 是特殊的樹 不是樹的特殊形式 是兩棵樹的總稱 有是只有二個(gè)根結(jié)點(diǎn)的樹形結(jié)構(gòu) B: 左子結(jié)點(diǎn) 右子結(jié)點(diǎn) 左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn) 兄弟CD： 最左子結(jié)點(diǎn) 最右子結(jié)點(diǎn) 最鄰近的右兄弟 最鄰近的左兄弟 最左的兄弟 最右的兄弟答案：A= B= C= D 答案：ABCDE2，1，1，3四、簡答題（每小題4分，共20分）1. 【嚴(yán)題集6.2】一棵度為2的樹與一棵二叉樹有何區(qū)別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結(jié)點(diǎn)只有一個(gè)孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個(gè)孩子也有左右之分。C的結(jié)點(diǎn)類型定義如下：struct no

11、dechar data;struct node *lchild, rchild;C算法如下：void traversal(struct node *root)if (root) printf(“%c”, root-data); traversal(root-lchild); printf(“%c”, root-data);traversal(root-rchild);2.01年計(jì)算機(jī)研題設(shè)如下圖所示的二叉樹B的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，root為根指針，結(jié)點(diǎn)結(jié)構(gòu)為：（lchild,data,rchild）。其中l(wèi)child，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試

12、回答下列問題：1. 對(duì)下列二叉樹B，執(zhí)行下列算法traversal(root)，試指出其輸出結(jié)果；2. 假定二叉樹B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù)雜度。（共8分）AB D C F G E二叉樹B解：這是“先根再左再根再右”，比前序遍歷多打印各結(jié)點(diǎn)一次，輸出結(jié)果為：A B C C E E B A D F F D G G特點(diǎn)：每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次；但出現(xiàn)的順序不同，其規(guī)律是：凡是有左子樹的結(jié)點(diǎn)，必間隔左子樹的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；如A，B，D等結(jié)點(diǎn)。反之馬上就會(huì)重復(fù)出現(xiàn)。如C，E，F(xiàn)，G等結(jié)點(diǎn)。時(shí)間復(fù)雜度以訪問結(jié)點(diǎn)的次數(shù)為主，精確值為2*n，時(shí)間漸近度為O(n

13、).3. 01年計(jì)算機(jī)研題【嚴(yán)題集6.27】給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。 D A C FE GB H I2825 3340 60 08 54 554.【計(jì)算機(jī)研200

14、0】給定如圖所示二叉樹T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。解：要遵循中序遍歷的軌跡來畫出每個(gè)前驅(qū)和后繼。中序遍歷序列：55 40 25 60 28 08 33 54282540555560330854NILNIL 2825 33 40 60 08 54 55五、閱讀分析題（每題5分，共20分）1. （P60 4-26）試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(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）把如圖所

15、示的樹轉(zhuǎn)化成二叉樹。答：注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結(jié)點(diǎn)一律歸入左子樹，新添連線結(jié)點(diǎn)一律歸入右子樹。 A B E C K F H D L G I M J答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)誤。注：當(dāng)rtag1時(shí)說明內(nèi)裝后繼指針，可直接返回，第一句無錯(cuò)。當(dāng)rtag0時(shí)說明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計(jì)算。中序遍歷應(yīng)當(dāng)先左再根再右，所以應(yīng)當(dāng)找左子樹直到葉子處。r=r-lchild; 直到LTag=1； 應(yīng)改為：while(!r-Ltag)r=r-Lchild;BiTree InSucc(BiTree q)/已知q是指向中序線索二叉樹上某個(gè)結(jié)點(diǎn)的指針，/本函

16、數(shù)返回指向*q的后繼的指針。r=q-rchild; /應(yīng)改為r=q；if(!r-rtag) while(!r-rtag)r=r-rchild; /應(yīng)改為 while(!r-Ltag) r=r-Lchild;return r; /應(yīng)改為return r-rchild；/ISucc3.【嚴(yán)題集6.17】閱讀下列算法，若有錯(cuò)，改正之。4.【嚴(yán)題集6.21】畫出和下列二叉樹相應(yīng)的森林。答：注意根右邊的子樹肯定是森林，而孩子結(jié)點(diǎn)的右子樹均為兄弟。六、算法設(shè)計(jì)題（前5題中任選2題，第6題必做，每題8分，共24分）1.【嚴(yán)題集6.42】編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。解：思路：輸出葉子結(jié)點(diǎn)比較簡單

17、，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子，將其打印出來。法一：核心部分為：DLR(liuyu *root) /*中序遍歷 遞歸函數(shù)*/if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)sum+; printf(%dn,root-data); DLR(root-lchild); DLR(root-rchild); return(0);法二：int LeafCount_BiTree(Bitree T)/求二叉樹中葉子結(jié)點(diǎn)的數(shù)目 if(!T) return 0; /空樹沒有葉子 else if(!T-lchild&!T-rchi

18、ld) return 1; /葉子結(jié)點(diǎn) else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子樹的葉子數(shù)加 上右子樹的葉子數(shù) /LeafCount_BiTree 注：上機(jī)時(shí)要先建樹！例如實(shí)驗(yàn)二的方案一。 打印葉子結(jié)點(diǎn)值（并求總數(shù)）思路：先建樹，再從遍歷過程中打印結(jié)點(diǎn)值并統(tǒng)計(jì)。步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構(gòu)成一棵二叉排序樹。葉子結(jié)點(diǎn)值應(yīng)該是4，9, 13, 21, 總數(shù)應(yīng)該是4. 127 17 2 11 16 21 4 9 13編程： 生成二叉樹排序樹之后，再中序遍歷排序查找結(jié)點(diǎn)的完整程序如下

19、： 說明部分為：#include #include typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排

20、序樹的適當(dāng)位置*/ q=p;if(p-data=x)printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild; if(xdata)q-lchild=s;else q-rchild=s;DLR(liuyu *root) /*中序遍歷 遞歸函數(shù)*/if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)sum+; printf(%dn,root-data); DLR(root-lchild); DLR(root-rchild); return(0)

21、; main() /*先生成二叉排序樹，再調(diào)用中序遍歷遞歸函數(shù)進(jìn)行排序輸出*/int i,x;i=1; root=NULL; /*千萬別忘了賦初值給root!*/doprintf(please input data%d:,i);i+;scanf(%d,&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結(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);執(zhí)行結(jié)果：若一

22、開始運(yùn)行就輸入-9999，則無葉子輸出，sum=0。2.【全國專升本統(tǒng)考題】寫出求二叉樹深度的算法，先定義二叉樹的抽象數(shù)據(jù)類型。 （10分）或【嚴(yán)題集6.44】編寫遞歸算法，求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度。答；設(shè)計(jì)思路：只查后繼鏈表指針，若左或右孩子的左或右指針非空，則層次數(shù)加1；否則函數(shù)返回。但注意，遞歸時(shí)應(yīng)當(dāng)從葉子開始向上計(jì)數(shù)，否則不易確定層數(shù)。 int depth(liuyu*root) /*統(tǒng)計(jì)層數(shù)*/int d,p; /*注意每一層的局部變量d,p都是各自獨(dú)立的*/p=0;if(root=NULL)return(p); /*找到葉子之后才開始統(tǒng)計(jì)*/else d=dep

23、th(root-lchild);if(dp) p=d; /*向上回朔時(shí)，要挑出左右子樹中的相對(duì)大的那個(gè)深度值*/d=depth(root-rchild);if(dp)p=d;p=p+1;return(p);法二：int Get_Sub_Depth(Bitree T,int x)/求二叉樹中以值為x的結(jié)點(diǎn)為根的子樹深度 if(T-data=x) printf(%dn,Get_Depth(T); /找到了值為x的結(jié)點(diǎn),求其深度 exit 1; else if(T-lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchi

24、ld,x); /在左右子樹中繼續(xù)尋找 /Get_Sub_Depth int Get_Depth(Bitree T)/求子樹深度的遞歸算法 if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; /Get_Depth 附：上機(jī)調(diào)試過程步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構(gòu)成一棵二叉排序樹。層數(shù)應(yīng)當(dāng)為4 12 8 17 2 11 16 21 4 9 13 步驟2： 執(zhí)行求深度的函數(shù)，并打印統(tǒng)計(jì)出來的深度值。完整程序如下：#include #inc

25、lude typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/ q=p;if(p-da

26、ta=x)printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild; if(xdata)q-lchild=s;else q-rchild=s;int depth(liuyu*root) /*統(tǒng)計(jì)層數(shù)*/int d,p; /*注意每一層的局部變量d,p都是各自獨(dú)立的*/p=0;if(root=NULL)return(p); /*找到葉子之后才開始統(tǒng)計(jì)*/else d=depth(root-lchild);if(dp) p=d; /*向上回朔時(shí)，要挑出左右子樹中的相對(duì)大的那個(gè)深度值*/d=depth

27、(root-rchild);if(dp)p=d;p=p+1;return(p);void main() /*先生成二叉排序樹，再調(diào)用深度遍歷遞歸函數(shù)進(jìn)行統(tǒng)計(jì)并輸出*/int i,x;i=1; root=NULL; /*千萬別忘了賦初值給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; else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素

28、的函數(shù)*/while(x!=-9999); return;執(zhí)行結(jié)果：3. 【嚴(yán)題集6.47】編寫按層次順序（同一層自左至右）遍歷二叉樹的算法?；颍喊磳哟屋敵龆鏄渲兴薪Y(jié)點(diǎn)；解：思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法。這是一個(gè)循環(huán)算法，用while語句不斷循環(huán)，直到隊(duì)空之后自然退出該函數(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已知*/int f,r;f=0; r=0; /*置空隊(duì)*/r

29、=(r+1)%max;qr=T; /*根結(jié)點(diǎn)進(jìn)隊(duì)*/while(f!=r) /*隊(duì)列不空*/f=(f+1%max);p=qf; /*出隊(duì)*/printf(%d,p-data); /*打印根結(jié)點(diǎn)*/if(p-lchild)r=(r+1)%max; qr=p-lchild; /*若左子樹不空，則左子樹進(jìn)隊(duì)*/ if(p-rchild)r=(r+1)%max; qr=p-rchild; /*若右子樹不空，則右子樹進(jìn)隊(duì)*/ return(0);法二：void LayerOrder(Bitree T)/層序遍歷二叉樹 InitQueue(Q); /建立工作隊(duì)列 EnQueue(Q,T); while(!

30、QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 可以用前面的函數(shù)建樹，然后調(diào)用這個(gè)函數(shù)來輸出。完整程序如下（已上機(jī)通過）#include #include #define max 50typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root,*p,*qmax;int sum=0;int m=sizeof(test);v

31、oid insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/ q=p;if(p-data=x)printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild; if(xdata)q-lchild=s;else

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

33、);void main() /*先生成二叉排序樹，再調(diào)用深度遍歷遞歸函數(shù)進(jìn)行統(tǒng)計(jì)并輸出*/int i,x;i=1; root=NULL; /*千萬別忘了賦初值給root!*/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)的完全二叉樹被順序存儲(chǔ)于一維數(shù)組A中，試編寫一個(gè)算法打印出編號(hào)為i的結(jié)點(diǎn)的雙親和所有的孩子。答：首先，由于是完全二叉樹，不必?fù)?dān)心中途會(huì)出現(xiàn)孩子為null的情況。其次分析：結(jié)點(diǎn)i的左孩子為2i，右孩子為2i+1;直接打印即可。Printf(“Left_child=”, %d, v2*i.data; “Right_child=”, %d, v2*i+1.data;);但其雙親是