二叉樹練習(xí)題答案

1、一、下面是有關(guān)二叉樹的敘述，請判斷正誤(V ) 1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在 n個結(jié)點(diǎn)的二叉樹鏈表中 只有n-1個非空指針域。(X ) 2.二叉樹中每個結(jié)點(diǎn)的兩棵子樹的高度差等于1。(V ) 3.二叉樹中每個結(jié)點(diǎn)的兩棵子樹是有序的。(X ) 4.二叉樹中每個結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。(X ) 5.二叉樹中所有結(jié)點(diǎn)個數(shù)是2k1-1 ,其中k是樹的深度。(X ) 6.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。(X ) 7.對于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i 1個結(jié)點(diǎn)。(V ) 8.用二叉鏈表法存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n

2、個指針區(qū)域 中有n+1個為空指針。(X ) 9.具有12個結(jié)點(diǎn)的完全二叉樹有5個度為2的結(jié)點(diǎn)。二、填空1 .由3個結(jié)點(diǎn)所構(gòu)成的二叉樹有 5 種形態(tài)。2 . 一棵深度為 6的滿二叉樹有2 6-33 個分支結(jié)點(diǎn)和32個葉子。3 . 一棵具有2 5 7個結(jié)點(diǎn)的完全二叉樹，它的深度為 _9。4 .設(shè)一棵完全二叉樹具有1000個結(jié)點(diǎn)，則此完全二叉樹有 500個葉子結(jié)點(diǎn)，有 499 個度為2的結(jié)點(diǎn)，有個結(jié)點(diǎn)只有非空左子樹，有 0 個結(jié)點(diǎn)只有非空右子樹。（分析：完全二叉樹中三種節(jié)點(diǎn)個數(shù)n0, n1, n2,其中n1 為 0 或 1; n0=n2+1;總節(jié)點(diǎn)個數(shù) N=n0+n1+n2=n0+n1+n0-1=2

3、*n0-1+n1.由此推 出當(dāng)完全二叉樹中節(jié)點(diǎn)個數(shù)為偶數(shù)時(shí) n1為1,否則為0,則可計(jì)算本題）5 .二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉 樹的遍歷次序有六種。最常用的是三種：前序法（即按NL R次序），后序法（即按LRN 次序）和中序法（也稱對稱序法，即按 L N R次序）。這三種方法 相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH中序序列是FEBGCH D則它的后序序列必是FEGHDCB。6 .用5個權(quán)值3, 2, 4, 5, 1 構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度 是（1+2）*3+3*2+（4+5）*2= 33。7 .一個深度為h

4、的二叉樹最多有 2 h-1結(jié)點(diǎn),最少有結(jié)點(diǎn)。三、選擇題1 .二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。（A）它不能用順序存儲結(jié)構(gòu)存儲；（B）它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲；（C）順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲；（D）順序存儲結(jié)構(gòu)和 鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用2 .具有n（n>0）個結(jié)點(diǎn)的完全二叉樹的深度為。（A） 1og2（n） 1 （ B） Jog2（n）（C） Jog2（n） >1（ D）log 2（n）+13 .把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。（A）唯一的（B）有2種（C）有多種，但根結(jié)點(diǎn)都沒有左孩子（D）有多種，但根結(jié)點(diǎn)都沒有右孩子4 .樹是結(jié)點(diǎn)的有限集合，它 A 根結(jié)點(diǎn)，記

5、為T。其余的結(jié)點(diǎn)分成為m （m>0）個 B的集合T1, T2,，Tm每個集合又都是樹，此時(shí)結(jié)點(diǎn) T稱為T的父結(jié)點(diǎn)，Ti 稱為T的子結(jié)點(diǎn)（iwi wm）。一個結(jié)點(diǎn)的子結(jié)點(diǎn)個數(shù)為該結(jié)點(diǎn)的 C。供選擇的答案A: 有0個或1個有0個或多個有且只有1個 有1 個或1個以上B:互不相交允許相交允許葉結(jié)點(diǎn)相交允許樹枝結(jié)點(diǎn)相交C:權(quán)度次數(shù)序答案:A B= C= 四、簡答題1 .給定如圖所示二叉樹T,請畫出與其對應(yīng)的中序線向二叉樹。12.25 -33/ / 40 6008 545，2 .把如圖所示的樹轉(zhuǎn)化成二叉樹，分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。3 . 假設(shè)用于通信的電文僅由8 個字母組成，字

6、母在電文中出現(xiàn)的頻率分別為0.07， 0.19， 0.02， 0.06， 0.32， 0.03， 0.21 ， 0.10。試為這8 個字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對于上述實(shí)例，比 較兩種方案的優(yōu)缺點(diǎn)。4 . 敘述二叉樹的性質(zhì)3，并證明五、算法1 .寫出對二叉樹的先序，中序，后序遍歷的算法2 .編寫求一棵二叉樹葉子結(jié)點(diǎn)個數(shù)的算法。3 .編寫求一棵二叉樹深度的算法六.算法填空題1.下面是對二叉樹進(jìn)行中序線索化，請?zhí)畛渎涞舻恼Z句typedef struct node int data;int It, rt;struct node *lc, *rc; *JD;status midindex(JD bt) p=bt ; pr=NULL;if (!p) return 0;initstack(S);while () if (p)push(S,p);p=p->lchild; else P=p