數(shù)據(jù)結(jié)構(gòu) C語言版 第二版(嚴(yán)蔚敏) 第5章樹和二叉樹 答案

1、第5章 樹和二叉樹1選擇題（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A唯一的 有多種C有多種，但根結(jié)點都沒有左孩子 有多種，但根結(jié)點都沒有右孩子答案：A 解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（2）由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ ）A2 B3 C4 D5 答案：D解釋：五種情況如下： （3）一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）。A250 B 500 C254 D501 答案：D解釋：設(shè)度為0結(jié)點（葉子結(jié)點）個數(shù)為A，度為1的結(jié)點個數(shù)為B，度為2的結(jié)點個數(shù)為C，有A=C+1，A+B+C=1001

2、，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因為C為整數(shù)，所以B=0，C=500，A=501，即有501個葉子結(jié)點。（4）一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（ ）。A11 B10 C11至1025之間 D10至1024之間答案：C解釋：若每層僅有一個結(jié)點，則樹高h(yuǎn)為1025；且其最小樹高為 ëlog21025û + 1=11，即h在11至1025之間。（5）深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=<k=<h) Amk-1 Bmk-1 Cmh-1 Dmh-1答案：A解釋：深度為h的滿m叉樹共有mh-1個結(jié)

3、點，第k層有mk-1個結(jié)點。（6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空答案：C解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結(jié)點，因為根節(jié)點沒有兄弟結(jié)點，故根節(jié)點的右指針指向空。（7）對二叉樹的結(jié)點從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（ ）遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷答案：C解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點的順序遍歷二叉樹，即后序遍歷二叉樹。（8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支

4、結(jié)點左、右子樹的位置，利用（ ）遍歷方法最合適。A前序 B中序 C后序 D按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實現(xiàn)左右子樹的交換，不過層次遍歷的實現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。（9）在下列存儲形式中，（ ）不是樹的存儲形式？A雙親表示法 B孩子鏈表表示法 C孩子兄弟表示法 D順序存儲表示法答案：D解釋：樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進(jìn)行存儲。（10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）。A所有的結(jié)點均無左孩子 B所有的結(jié)點均無右孩子C

5、只有一個葉子結(jié)點 D是任意一棵二叉樹答案：C解釋：因為先序遍歷結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒有左子樹時，就是“中右”和“右中”；當(dāng)沒有右子樹時，就是“中左”和“左中”。則所有的結(jié)點均無左孩子或所有的結(jié)點均無右孩子均可，所以A、B不能選，又所有的結(jié)點均無左孩子與所有的結(jié)點均無右孩子時，均只有一個葉子結(jié)點，故選C。（11）設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（ ）個葉子結(jié)點。A99B100C101D102答案：B解釋：在哈夫曼樹中沒有度為1的結(jié)點，只有度為0（葉子結(jié)點）和度為2的結(jié)點。設(shè)葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結(jié)點

6、數(shù)n= n0+n2=2*n0-1，得到n0=100。（12）若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（ ）。AX的雙親 BX的右子樹中最左的結(jié)點 CX的左子樹中最右結(jié)點 DX的左子樹中最右葉結(jié)點答案：C（13）引入二叉線索樹的目的是（ ）。A加快查找結(jié)點的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一答案：A（14）設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（ ）個。An1BnCn + 1Dn + 2答案：C（15）n（n2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于

7、該樹的敘述中，錯誤的是（ ）。A該樹一定是一棵完全二叉樹B樹中一定沒有度為1的結(jié)點C樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值答案：A解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為1的結(jié)點、兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點、任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值。2應(yīng)用題（1）試找出滿足下列條件的二叉樹 先序序列與后序序列相同 中序序列與后序序列相同 先序序列與中序序列相同 中序序列與層次遍歷序列相同答案：先序遍歷二叉樹的順序是“根左子樹右子樹”，中序遍歷“左子樹根右子樹”

8、，后序遍歷順序是：“左子樹右子樹根，根據(jù)以上原則有 或為空樹，或為只有根結(jié)點的二叉樹  或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹  或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹 或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹（2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。答案： ABFDCEHG         （3） 假設(shè)用于通信的電文僅由8個字母組成

9、，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個字母設(shè)計赫夫曼編碼。 試設(shè)計另一種由二進(jìn)制表示的等長編碼方案。 對于上述實例，比較兩種方案的優(yōu)缺點。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32（100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 方

10、案比較：字母編號對應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進(jìn)

11、制編碼 （4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。答案：初態(tài): weightparentlchildrchild13000212000370004400052000680007110008 0009 00010 00011 00012 00013 000 終態(tài)： weightparentlchildrchild1380021212003710004490052800681000711110085951

12、9911481015123611201397122713210134701112 3算法設(shè)計題以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法：（1）統(tǒng)計二叉樹的葉結(jié)點個數(shù)。題目分析如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時為空，返回左子樹中葉子節(jié)點個數(shù)加上右子樹中葉子節(jié)點個數(shù)。算法描述 int LeafNodeCount(BiTree T)if(T=NULL)return 0; /如果是空樹，則葉子結(jié)點個數(shù)為0else if(T->lchild=NULL&&T->rchild=NULL)return 1; /判斷

13、結(jié)點是否是葉子結(jié)點（左孩子右孩子都為空），若是則返回1elsereturn LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);（2）判別兩棵樹是否相等。題目分析先判斷當(dāng)前節(jié)點是否相等(需要處理為空、是否都為空、是否相等)，如果當(dāng)前節(jié)點不相等，直接返回兩棵樹不相等;如果當(dāng)前節(jié)點相等，那么就遞歸的判斷他們的左右孩子是否相等。算法描述int compareTree(TreeNode* tree1, TreeNode* tree2)/用分治的方法做，比較當(dāng)前根，然后比較左子樹和右子樹bool tree1IsNull = (tree1=NUL

14、L);bool tree2IsNull = (tree2=NULL);if(tree1IsNull != tree2IsNull)return 1;if(tree1IsNull && tree2IsNull)/如果兩個都是NULL，則相等return 0;/如果根節(jié)點不相等，直接返回不相等，否則的話，看看他們孩子相等不相等if(tree1->c != tree2->c)return 1;return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2-&g

15、t;right) (compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left);/算法結(jié)束（3）交換二叉樹每個結(jié)點的左孩子和右孩子。題目分析如果某結(jié)點左右子樹為空，返回，否則交換該結(jié)點左右孩子，然后遞歸交換左右子樹。算法描述void ChangeLR(BiTree &T)BiTree temp;if(T->lchild=NULL&&T->rchild=NULL)return;elsetemp = T->lchild;T->l

16、child = T->rchild;T->rchild = temp;/交換左右孩子ChangeLR(T->lchild); /遞歸交換左子樹ChangeLR(T->rchild); /遞歸交換右子樹（4）設(shè)計二叉樹的雙序遍歷算法（雙序遍歷是指對于二叉樹的每一個結(jié)點來說，先訪問這個結(jié)點，再按雙序遍歷它的左子樹，然后再一次訪問這個結(jié)點，接下來按雙序遍歷它的右子樹）。題目分析若樹為空，返回；若某結(jié)點為葉子結(jié)點，則僅輸出該結(jié)點；否則先輸出該結(jié)點，遞歸遍歷其左子樹，再輸出該結(jié)點，遞歸遍歷其右子樹。算法描述void DoubleTraverse(BiTree T)if(T = N

17、ULL)return;else if(T->lchild=NULL&&T->rchild=NULL)cout<<T->data; /葉子結(jié)點輸出elsecout<<T->data;DoubleTraverse(T->lchild); /遞歸遍歷左子樹cout<<T->data; DoubleTraverse(T->rchild); /遞歸遍歷右子樹（5）計算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點個數(shù)的最大值）。題目分析 求二叉樹高度的算法見上題。求最大寬度可采用層次遍歷的方法，記下各

18、層結(jié)點數(shù)，每層遍歷完畢，若結(jié)點數(shù)大于原先最大寬度，則修改最大寬度。算法描述int Width(BiTree bt)/求二叉樹bt的最大寬度if (bt=null) return (0); /空二叉樹寬度為0else BiTree Q;/Q是隊列，元素為二叉樹結(jié)點指針，容量足夠大front=1;rear=1;last=1;/front隊頭指針,rear隊尾指針,last同層最右結(jié)點在隊列中的位置temp=0; maxw=0; /temp記局部寬度, maxw記最大寬度Qrear=bt; /根結(jié)點入隊列while(front<=last)p=Qfront+; temp+; /同層元素數(shù)加1i

19、f (p->lchild!=null) Q+rear=p->lchild; /左子女入隊if (p->rchild!=null) Q+rear=p->rchild; /右子女入隊if (front>last) /一層結(jié)束， last=rear;if(temp>maxw) maxw=temp;/last指向下層最右元素, 更新當(dāng)前最大寬度 temp=0; /if /whilereturn (maxw);/結(jié)束width（6）用按層次順序遍歷二叉樹的方法，統(tǒng)計樹中具有度為1的結(jié)點數(shù)目。題目分析若某個結(jié)點左子樹空右子樹非空或者右子樹空左子樹非空，則該結(jié)點為度為1的

20、結(jié)點算法描述int Level(BiTree bt) /層次遍歷二叉樹，并統(tǒng)計度為1的結(jié)點的個數(shù)int num=0; /num統(tǒng)計度為1的結(jié)點的個數(shù) if(bt)QueueInit(Q); QueueIn(Q,bt);/Q是以二叉樹結(jié)點指針為元素的隊列while(!QueueEmpty(Q)p=QueueOut(Q); cout<<p->data; /出隊,訪問結(jié)點if(p->lchild && !p->rchild |!p->lchild && p->rchild)num+;/度為1的結(jié)點if(p->lchild

21、) QueueIn(Q,p->lchild); /非空左子女入隊if(p->rchild) QueueIn(Q,p->rchild); /非空右子女入隊 / while(!QueueEmpty(Q)/if(bt) return(num); /返回度為1的結(jié)點的個數(shù) （7）求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點的值。題目分析因為后序遍歷棧中保留當(dāng)前結(jié)點的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結(jié)點，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。算法描述void LongestPath(BiTree bt)/求二叉樹中的第一條最長路徑長度BiTree p=bt,l,s; /l, s是棧，元素是二叉樹結(jié)點指針，l中保留當(dāng)前最長路徑中的結(jié)點int i，top=0,tag,longest=0;while(p | top>0)while(p) s+top=p；tagtop=0; p=p->Lc; /沿左分枝向下if(tagtop=1) /當(dāng)前結(jié)點的右分枝已遍歷if(!stop->Lc && !stop->Rc) /只有到葉子結(jié)點時，才查看路徑長度if(