【文章內(nèi)容簡介】 v的右子樹的結(jié)點中,其最小編號等于v左子樹上結(jié)點的最大編號加１，這是按（B）編號的。A． 中序遍歷序列 B． 先序遍歷序列 C． 后序遍歷序列 D． 層次順序 6．設F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點,B中右指針域為空的結(jié)點有（C）個。A．n1 B． n C． n+1 D．n+2 7．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（B）。A． 500 B． 501 C．490 D．4958．設森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為N1，N2和N3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（D）。A．N1 B．N1+N2 C．N2 D．N2+N39．任何一棵二叉樹的葉結(jié)點在先序、中序、后序遍歷序列中的相對次序（A）。A．不發(fā)生改變 B． 發(fā)生改變 C． 不能確定 D． 以上都不對10．若一棵二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為（D）。A．cbed B．decab C．deabc D．cedba11．若一棵二叉樹的先序遍歷序列為abdgcefh，中序遍歷的序列為dgbaechf，則后序遍歷的結(jié)果為（D）。 A． gcefha B． gdbecfha C． bdgaechf D． gdbehfca12．一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（AB）。A．所有的結(jié)點均無左孩子 B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點 D．是一棵滿二叉樹13．引入線索二叉樹的目的是（A）。A．加快查找結(jié)點的前驅(qū)或后繼的速度 B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親 D．使二叉樹的遍歷結(jié)果唯一 14．設高度為h的二叉樹上只有度為０和度為２的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（B）。A．2*h B． 2*h1 C． 2*h+1 D．h+115．一個具有567個結(jié)點的二叉樹的高h為（D）。A．9 B．10 C．9至566之間 D．10至567之間16．給一個整數(shù)集合{3，5，6，7，9}，與該整數(shù)集合對應的哈夫曼樹是（B）。A． B． C． D．93765 356797953676539 判斷題1．二叉樹是樹的特殊形式。（√）2．由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。（√）3．先根遍歷一棵樹和先序遍歷與該樹對應的二叉樹，其結(jié)果不同。（）4．先根遍歷森林和先序遍歷與該森林對應的二叉樹，其結(jié)果不同。（）5．完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是葉子。（√）6．對于有N個結(jié)點的二叉樹，其高度為235。log2N＋1。（）7．若一個結(jié)點是某二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的先序遍歷序列中的最后一個結(jié)點。（√）8．若一個結(jié)點是某二叉樹子樹的中序遍歷序列中的第一個結(jié)點，則它必是該子樹的后序遍歷序列中的第一個結(jié)點。（√）9．不使用遞歸也可實現(xiàn)二叉樹的先序、中序和后序遍歷。（√）10．先序遍歷二叉樹的序列中，任何結(jié)點的子樹的所有結(jié)點不一定跟在該結(jié)點之后。（）11．先序和中序遍歷用線索樹方式存儲的二叉樹，不必使用棧。（）12．在后序線索二叉樹中，在任何情況下都能夠很方便地找到任意結(jié)點的后繼。（）13．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。（√）14．在哈夫曼編碼中，出現(xiàn)頻率相同的字符編碼長度也一定相同。（）15．用一維數(shù)組存放二叉樹時，總是以先序遍歷存儲結(jié)點。（）16．由先序序列和后序序列能唯一確定一棵二叉樹。（）17．由先序序列和中序序列能唯一確定一棵二叉樹。（√）18．對一棵二叉樹進行層次遍歷時，應借助于一個棧。（）19．完全二叉樹可采用順序存儲結(jié)構(gòu)實現(xiàn)存儲，非完全二叉樹則不能。（）20．滿二叉樹一定是完全二叉樹，反之未必。（√） 簡答題1．一棵度為2的樹與一棵二叉樹有何區(qū)別？樹與二叉樹之間有何區(qū)別？【解答】①二叉樹是有序樹，度為2的樹是無序樹，二叉樹的度不一定是2。ADBGEHCF(圖 1)②二叉樹是有序樹，每個結(jié)點最多有兩棵子樹，樹是無序樹，且每個結(jié)點可以有多棵子樹。2．對于圖1所示二叉樹，試給出：（1）它的順序存儲結(jié)構(gòu)示意圖；（2）它的二叉鏈表存儲結(jié)構(gòu)示意圖；（3）它的三叉鏈表存儲結(jié)構(gòu)示意圖?！窘獯稹浚?）順序存儲結(jié)構(gòu)示意圖：ABCDEF^^^G^^H（2）二叉鏈表存儲結(jié)構(gòu)示意圖： （3）三叉鏈表存儲結(jié)構(gòu)示意圖：ABC ^^ D ^ E ^^ F^ G ^^ H ^A ^BC ^^ D ^E ^^ F ^ G ^^ H ^IDEFGCBANMKJH(圖 2)3．對于圖2所示的樹，試給出：（1）雙親數(shù)組表示法示意圖；（2）孩子鏈表表示法示意圖；（3）孩子兄弟鏈表表示法示意圖?！窘獯稹浚?）雙親數(shù)組表示法示意圖： （2）孩子鏈表表示法示意圖：0A11B02C03D24E25F16G17H58I29J410K411M312N82 ^6410 ^15311 ^97 ^12 ^0A1B2C3D4E5F6G7H8I9J10K11M12N8 ^（3）孩子兄弟鏈表表示法示意圖：A ^B^ N ^^ H ^C ^^ GF ^EDI ^^ J^ K ^^ M ^4．畫出圖3所示的森林經(jīng)轉(zhuǎn)換后所對應的二叉樹，并指出森林中滿足什么條件的結(jié)點在二叉樹中是葉子。DBCIG HAFE J(圖 3)【解答】HFGIJABCED在二叉樹中某結(jié)點所對應的森林中結(jié)點為葉子結(jié)點的條件是該結(jié)點在森林中既沒有孩子也沒有右兄弟結(jié)點。5．將題5圖所示的二叉樹轉(zhuǎn)換成相應的森林。HGDE FBAC(題5圖)【解答】森林：ABHEGDCF6．證明：在結(jié)點數(shù)多于1的哈夫曼樹中不存在度為1的結(jié)點。證明：由哈夫曼樹的構(gòu)造過程可知，哈夫曼樹的每一分支結(jié)點都是由兩棵子樹合并產(chǎn)生的新結(jié)點，其度必為2，所以哈夫曼樹中不存在度為1的結(jié)點。7．證明：若哈夫曼樹中有n個葉結(jié)點，則樹中共有2n－1個結(jié)點。證明：n個葉結(jié)點，需經(jīng)n1次合并形成哈夫曼樹，而每次合并產(chǎn)生一個分支結(jié)點，所以樹中共有2n1個結(jié)點。8．證明：由二叉樹的前序序列和中序序列可以唯一地確定一棵二叉樹。證明：給定二叉樹結(jié)點的前序序列和對稱序（中序）序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結(jié)點，該元素將二叉樹中序序列分成兩部分，左邊（設l個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設r個元素）是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根—左子樹—右子樹”的順序，則由從第二元素開始的l個結(jié)點序列和中序序列根左邊的l個結(jié)點序列構(gòu)造左子樹，由前序序列最后r個元素序列與中序序列根右邊的r個元素序列構(gòu)造右子樹。9．已知一棵度為m的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點？有多少個非終端結(jié)點？解：設樹中共有n個結(jié)點，n0個葉結(jié)點，那么n=n0+n1+…+nm (1)樹中除根結(jié)點外，每個結(jié)點對應著一個分支，而度為k的結(jié)點發(fā)出k個分支，所以： n=n1+2*n2+…+m*nm+1 (2)由(1)、(2)可知n0= n2+2*n3+3*n4+…+(m1)*nm+110．在具有n（n1）個結(jié)點的樹中，深度最小的那棵樹其深度是多少？它共有多少葉子和非葉子結(jié)點？深度最大的那棵樹其深度是多少？它共有多少葉子和非葉子結(jié)點？2。 n1。 1。 n。 1, n111．設高度為h的二叉樹上只有度為0和度為2的結(jié)點，問該二叉樹的結(jié)點數(shù)可能達到的最大值和最小值。最大值：2h1； 最小值：2h112．求表達式： a＋b*(c－d)－e/f的波蘭式（前綴式）和逆波蘭式（后綴式）。波蘭式： + a * b – c d / e f 逆波蘭式：a b c d * + e f / 13．畫出和下列已知序列對應的樹T：樹的先根次序訪問序列為：GFKDAIEBCHJ；樹的后根訪問次序為：DIAEKFCJHBG?！窘獯稹繉亩鏄浜蜆浞謩e如下左、右圖所示：GBIEADKFCHJGBIEADKFCHJ14．畫出和下列已知序列對應的森林F：森林的先根次序訪問序列為：ABCDEFGHIJKL；森林的后根訪問次序為：CBEFDGAJIKLH。ABDGCEFHIKJL15．畫出和下列已知序列對應的樹T：二叉樹的層次訪問序列為：ABCDEFGHIJ；二叉樹的中序訪問次序為：DBGEHJACIF。【解答】ABCDEFGHIJ按層次遍歷，第一個結(jié)點（若樹不空）為根，該結(jié)點在中序序列中把序列分成左右兩部分—左子樹和右子樹。若左子樹不空，層次序列中第二個結(jié)點左子樹的根；若左子樹為空，則層次序列中第二個結(jié)點右子樹的根。對右子樹也作類似的分析。層次序列的特點是：從左到右每個結(jié)點或是當前情況下子樹的根或是葉子。16．假設用于通信的電文由字符集{a,b,c,d,e,f,g}中的字母構(gòu)成。它們在電文中出現(xiàn)的頻度分別為{,,},（1）為這7個字母設計哈夫曼編碼。（2）對這7個字母進行等長編碼，至少需要幾位二進制數(shù)？111111總長壓縮多少？ （1）哈夫曼樹：a：10b：110c：010d：1110e：011f：00g：1111（2）對這7個字母進行等長編碼，至少需要3位二進制數(shù)。等長編碼的平均長度：*3+*3+*3+*3+*3+*3+*3=3哈夫曼編碼：*2+*3+*3+*4+*3+*2+*4=哈夫曼編碼比等長編碼使電文總長壓縮了：1 算法設計題1．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹結(jié)點的數(shù)目的算法?！咎崾尽坎捎眠f歸算法實現(xiàn)。二叉樹結(jié)點的數(shù)目＝0 當二叉樹為空左子樹結(jié)點數(shù)目＋右子樹結(jié)點數(shù)目＋1 當二叉樹非空int count(BiTree root){ if (root==NULL) return (0)。 else return (count(rootlchild)+count(rootrchild)+1)。 }2．請設計一個算法，要求該算法把二叉樹的葉結(jié)點按從左至右的順序鏈成一個單鏈表。二叉樹按lchildrchild方式存儲，鏈接時用葉結(jié)點的rchild域存放鏈指針?！咎崾尽窟@是一個非常典型的基于二叉樹遍歷算法，通過遍歷找到各個葉子結(jié)點，因為不論前序遍歷、中序遍歷和后序遍歷，訪問葉子結(jié)點的相對順序都是相同的，即都是從左至右。而題目要求是將二叉樹中的葉子結(jié)點按從左至右順序建立一個單鏈表，因此，可以采用三種遍歷中的任意一種方法遍歷。這里使用中序遞歸遍歷。設置前驅(qū)結(jié)點指針pre，初始為空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點的rchild為空。LinkList head,pre=NULL。 /*全局變量*/LinkList InOrder(BiTree T) /*中序遍歷二叉樹T，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為head*/{ if(T) { InOrder(Tlchild)。 /*中序遍歷左子樹*/if (Tlchild==NULL amp。amp。 Trchild==NULL) /*當前是葉子結(jié)點*/if (pre==NULL) { h