數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)

1、頁(yè)眉內(nèi)容第0章樹和二叉樹、基礎(chǔ)知識(shí)和算法1 .樹及有關(guān)概念樹，根，子樹；結(jié)點(diǎn)，結(jié)點(diǎn)的度，葉子（終端結(jié)點(diǎn)），分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)），內(nèi)部結(jié)點(diǎn)，樹的度；孩子，雙親，兄弟，祖先，子孫，堂兄弟；層次（根所在層為第1層），深度，高度；有序樹，無(wú)序樹，二叉樹是有序樹；森林。2 .二叉樹二叉樹（二叉樹與度為2的樹不同，二叉樹的度可能是0,1,2）;左孩子，右孩子。二叉樹的五種基本形態(tài)。3 .二叉樹的性質(zhì)1°.二叉樹的第i層本書中約定根結(jié)點(diǎn)在第1層，也有約定根在第0層的，則計(jì)算公式會(huì)有所不同上至多有2T個(gè)結(jié)點(diǎn)。2 .深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。滿二叉樹：深度為k,有2k-1個(gè)結(jié)點(diǎn)。完全二叉

2、樹：給滿二叉樹的結(jié)點(diǎn)編號(hào)，從上至下，從左至右，n個(gè)結(jié)點(diǎn)的完全二叉樹中結(jié)點(diǎn)在對(duì)應(yīng)滿二叉樹中白編號(hào)正好是從1到n。3 .葉子結(jié)點(diǎn)n0,度為2的結(jié)點(diǎn)為n2,則n0=n2+1。考慮結(jié)點(diǎn)個(gè)數(shù)：n=n0+m+n2考慮分支個(gè)數(shù)：n-1=2n2+n1可得n0=n2+1例：1）二叉樹有n個(gè)葉子，沒有度為1的結(jié)點(diǎn)，共有個(gè)結(jié)點(diǎn)。2）完全二叉樹的第3層有2個(gè)葉子，則共有個(gè)結(jié)點(diǎn)。分析：1）度為2的結(jié)點(diǎn)有n-1個(gè)，所以共2n-1個(gè)結(jié)點(diǎn)。2）注意考慮到符合條件的二叉樹的深度可能是3或4,所以有5、10或11個(gè)結(jié)點(diǎn)。4°.n個(gè)結(jié)點(diǎn)的完全二叉樹深度為logn1。5°.n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)按層次編號(hào)有：

3、i的雙親是n/2，如果i=1時(shí)為根（無(wú)雙親）；i的左孩子是2i,如果2i>n,則無(wú)左孩子；i的右孩子是2i+1,如果2i+1>n則無(wú)右孩子。4.二叉樹的存儲(chǔ)結(jié)構(gòu)1 。.順序存儲(chǔ)結(jié)構(gòu)用數(shù)組、編號(hào)i的結(jié)點(diǎn)存放在i-1處。適合于存儲(chǔ)完全二叉樹。2 .鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表：typedefstructBTNodeElemTypedata;structBTNode*lchild,*rchild;BTNode,*BinTree;三叉鏈表：typedefstructBTNodeElemTypedata;structBTNode*lchild,*rchild,*parent;BTNode,*BinT

4、ree;lchilddatarchild7萬(wàn)lchilddata parent rchild13例：用二叉鏈表存儲(chǔ)n個(gè)結(jié)點(diǎn)的二叉樹（n>0）,共有（n+1）個(gè)空指針域；采用三叉鏈表存儲(chǔ),共有（n+2）個(gè)空指針域。5 .二叉樹的五種基本形態(tài)空樹：bt=NULL左右子樹均空：bt->lchild=NULLandbt->rchild=NULL右子樹為空：bt->rchild=NULL左子樹為空：bt->lchild=NULL左右子樹均非空。前兩種常作為遞歸結(jié)束條件，后三者常需要遞歸。6 .遍歷二叉樹11常見有四種遍歷方式按層次遍歷，先序遍歷，中序遍歷，后序遍歷。按層次遍

5、歷：“從上至下，從左至右”，利用隊(duì)列。先序遍歷：DLR;中序遍歷：LDR;后序遍歷LRD。例：寫出a+b*(c-d)-e/f的前綴、中綴和后綴表達(dá)式。畫出二叉樹，分別進(jìn)行前序、中序、后序遍歷即可得到。前綴表達(dá)式：-+a*b-cd/ef中綴表達(dá)式：a+b*c-d-e/f后綴表達(dá)式：abcd-*+ef/-2°.先序遍歷算法voidPreorder(BinTreebt)if(bt)visit(bt->data);Preorder(bt->lchild);Preorder(bt->rchild);3°.中序遍歷算法voidInorder(BinTreebt)if(

6、bt)Inorder(bt->lchild);visit(bt->data);Inorder(bt->rchild);4°.后序遍歷voidPostorder(BinTreebt)if(bt)Postorder(bt->lchild);Postorder(bt->rchild);visit(bt->data);5°.非遞歸遍歷二叉樹一般借助棧實(shí)現(xiàn)。設(shè)想一指針沿二叉樹中序順序移動(dòng)，每當(dāng)向上層移動(dòng)時(shí)就要出棧。(a) 中序非遞歸遍歷指針p從根開始，首先沿著左子樹向下移動(dòng)，同時(shí)入棧保存；當(dāng)?shù)竭_(dá)空子樹后需要退棧訪問結(jié)點(diǎn)，然后移動(dòng)到右子樹上去。voi

7、dInOrder(BinTreebt,VisitFuncvisit)InitStack(S);p=bt;while(p|!StackEmpty(S)if(p)Push(S,p);p=p->lchild;elsePop(S,p);visit(p);/中序訪問結(jié)點(diǎn)的位置p=p->rchild;(b) 先序非遞歸遍歷按照中序遍歷的順序，將訪問結(jié)點(diǎn)的位置放在第一次指向該結(jié)點(diǎn)時(shí)。voidPreorder(BinTreebt,VisitFuncvisit)InitStack(S);p=bt;while(p|!StackEmpty(S)if(p)visit(p);/先序訪問結(jié)點(diǎn)的位置Push(S

8、,p);p=p->lchild;elsePop(S,p);p=p->rchild;或者，由于訪問過的結(jié)點(diǎn)便可以棄之不用，只要能訪問其左右子樹即可，寫出如下算法。voidPreorder(BinTreebt,VisitFuncvisit)InitStack(S);Push(S,bt);while(!StackEmpty(S)Pop(S,p);if(p)visit(p);/ 先進(jìn)棧，后訪問，所以/ 這里先讓右子樹進(jìn)棧Push(S,p->rchild);Push(S,p->lchild);(c)后序非遞歸遍歷后序遍歷時(shí)，分別從左子樹和右子樹共兩次返回根結(jié)點(diǎn)，只有從右子樹返回時(shí)

9、才訪問根結(jié)點(diǎn)，所以增加一個(gè)棧標(biāo)記到達(dá)結(jié)點(diǎn)的次序。voidPostOrder(BinTreebt,VisitFuncvisit)InitStack(S),InitStack(tag);p=bt;while(p|!StackEmpty(S)if(p)Push(S,p),Push(tag,1);/第一次入棧p=p->lchild;elsePop(S,p),Pop(tag,f);if(f=1)/從左子樹返回，二次入棧，然后p轉(zhuǎn)右子樹Push(S,p),Push(tag,2);p=p->rchild;else/從右子樹返回(二次出棧)，訪問根結(jié)點(diǎn)，p轉(zhuǎn)上層visit(p);p=NULL;/必

10、須的，使下一步繼續(xù)退棧注：后序非遞歸遍歷的過程中，棧中保留的是當(dāng)前結(jié)點(diǎn)的所有祖先。這是和先序及中序遍歷不同的。在某些和祖先有關(guān)的算法中，此算法很有價(jià)值。7.遍歷二叉樹的應(yīng)用11寫出遍歷序列(前、中、后序)2.根據(jù)遍歷序列畫出二叉樹(a)已知前序和中序序列，唯一確定二叉樹。例：前序：ABDEGCFH,中序：DBGEAFHC,畫出二叉樹。分析：前序序列的第一個(gè)是根，這是解題的突破口。步驟：前序序列的第一個(gè)是根在中序序列中標(biāo)出根，分成左右子樹在前序序列中標(biāo)出左右子樹(根據(jù)結(jié)點(diǎn)個(gè)數(shù)即可)分別對(duì)左右子樹的前序和中序序列重復(fù)以上步驟直至完成。(b)已知后序和中序序列，唯一確定二叉樹。例：后序：DGEBHF

11、CA，中序：DBGEAFHC，畫出二叉樹。分析：后序序列的最后一個(gè)是根，這是解題的突破口。步驟：后序序列的最后一個(gè)是根在中序序列中標(biāo)出根，分成左右子樹在后序序列中標(biāo)出左右子樹(根據(jù)結(jié)點(diǎn)個(gè)數(shù)即可)分別對(duì)左右子樹的后序和中序序列重復(fù)以上步驟直至完成。(c)已知前序和后序序列，不存在度為1的結(jié)點(diǎn)時(shí)能唯一確定二叉樹。例：前序：ABDEC，后序：DEBCA，畫出二叉樹。又前序AB，后序BA則不能唯一確定二叉樹。注：對(duì)于不存在度為1的結(jié)點(diǎn)的二叉樹，首先確定根結(jié)點(diǎn)，然后總可以將其余結(jié)點(diǎn)序列劃分成左右子樹，以此類推即可確定二叉樹。說明：畫出二叉樹后可以進(jìn)行遍歷以便驗(yàn)證。3°.編寫算法思路：按五種形態(tài)

12、(-)分析，適度簡(jiǎn)化。例：求二叉樹結(jié)點(diǎn)的個(gè)數(shù)。分析：0；1；L+1;1+R;1+L+R。簡(jiǎn)化：1+L=0+R=oi+l+R=o1+L=0+R1+L+R可合并成一種情況。intNodeCount(BinTreebt)if(bt=0)return0；elsereturn1+NodeCount(bt->lchild)+NodeCount(bt->rchild)；例：求二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)。分析：0；1；L;R;L+R。簡(jiǎn)化：可合并成。intLeafCount(BinTreebt)if(bt=0)return0；elseif(bt->lchild=0andbt->rchild=

13、0)return1；elsereturnLeafCount(bt->lchild)+LeafCount(bt->rchild)；例：求二叉樹的深度。分析：0；1；1+L;1+R;1+max(L,R)。簡(jiǎn)化：可合并成。intDepth(BinTreebt)if(bt=0)return0；elsereturn1+max(Depth(bt->lchild),Depth(bt->rchild)；8.線索二叉樹1°.線索n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空指針，可以利用其指向前驅(qū)或后繼結(jié)點(diǎn)，叫線索，同時(shí)需附加一個(gè)標(biāo)志，區(qū)分是子樹還是線索。lchildltagdatartag

14、rchild0/10/1Ichild有左子樹，則指向左子樹，標(biāo)志ltag=0;沒有左子樹，可作為前驅(qū)線索，標(biāo)志ltag=1。rchild有右子樹，則指向右子樹，標(biāo)志rtag=0;沒有右子樹，可作為后繼線索，標(biāo)志rtag=1。2.線索化二叉樹利用空指針作為線索指向前驅(qū)或后繼。左邊空指針可以作為前驅(qū)線索，右邊空指針可以作為后繼線索，可以全線索化或部分線索化。表0.1線索化二叉樹的類型前驅(qū)、后繼線索前驅(qū)線索后繼線索中序線索化中序全線索中序前驅(qū)線索中序后繼線索前序線索化前序全線索前序前驅(qū)線系前序后繼線索后序線索化后序全線索后序前驅(qū)線索后序后繼線索3°.畫出線索二叉樹思路：先寫出遍歷序列，再畫

15、線索。步驟：標(biāo)出必要的空指針（前驅(qū)左指針；后繼右指針，要點(diǎn)：“不要多標(biāo)，也不要少標(biāo)”）。寫出對(duì)應(yīng)的遍歷序列（前序，中序或后序）對(duì)照遍歷結(jié)果畫線索。例：畫出圖中二叉樹的后序后繼線索。步驟：先標(biāo)出所有空的右指針（DGCH）;寫出后序遍歷結(jié)果：DGEBHFCA;標(biāo)出后繼線索：DG,GE,CA,HF。如圖。4°.遍歷線索二叉樹反復(fù)利用孩子和線索進(jìn)行遍歷，可以避免遞歸。9.樹和森林1二樹的存儲(chǔ)結(jié)構(gòu)雙親表示法，孩子表示法，孩子兄弟表示法。特點(diǎn)：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子，但求雙親麻煩；兩者可以結(jié)合起來使用。孩子兄弟表示法，容易求得孩子和兄弟，求雙親麻煩，也可

16、以增加指向雙親的指針來解決。2.樹與二叉樹的轉(zhuǎn)換表0.2樹和二叉樹的對(duì)應(yīng)關(guān)系樹第一個(gè)孩子 下一個(gè)兄弟對(duì)應(yīng)的二叉樹左孩子右孩子特點(diǎn)：由樹轉(zhuǎn)化成的二叉樹，根結(jié)點(diǎn)沒有右孩子例：樹轉(zhuǎn)換成二叉樹。3°.森林與二叉樹的轉(zhuǎn)換森林中第1棵樹的根作為對(duì)應(yīng)的二叉樹的根；其他的樹看作第1棵樹的兄弟；森林中的樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹。則森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹。例：將森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹。參見課本P138。4°.樹的遍歷樹的結(jié)構(gòu)：根，根的子樹。先根遍歷：。例：ABCDEFGHIJK。后根遍歷：。例：CEDFBHGJKIA。5 .遍歷森林森林的結(jié)構(gòu)：第一棵樹的根，第一棵樹的根的子樹森林，其余樹（除第一棵

17、外）組成的森林。先序遍歷：。例：ABCDEFGHIJ。中序遍歷：。例：BDCEAGFIJH。注：先序遍歷森林，相當(dāng)于依次先根遍歷每一棵樹；中根遍歷森林相當(dāng)于后根遍歷每一棵樹。樹的結(jié)構(gòu)劃森林的結(jié)構(gòu)劃分6 .遍歷樹、森林與遍歷二叉樹的關(guān)系表0.3遍歷樹、森林和二叉樹的關(guān)系樹森林二叉樹先根遍歷后根遍歷先序遍歷先序遍歷中序遍歷中序遍歷10.赫夫曼樹及其應(yīng)用1;最優(yōu)二叉樹(赫夫曼樹，哈夫曼樹)樹的帶權(quán)路徑長(zhǎng)度：所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。nWPLwk1kk1路徑長(zhǎng)度1k按分支數(shù)目計(jì)算。帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為最優(yōu)二叉樹，或赫夫曼樹(哈夫曼樹)。2.構(gòu)造赫夫曼樹算法：參見課本P145。簡(jiǎn)單說，“每

18、次取兩個(gè)最小的樹組成二叉樹”(不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場(chǎng)合引用。)。3°.赫夫曼編碼(前綴碼)向左分支為0,向右分支為1,從根到葉子的路徑構(gòu)成葉子的前綴編碼。例：字符及其權(quán)值如下：A(6),B(7),C(1),D(5),E(2),F(8),構(gòu)造哈夫曼樹和哈夫曼編碼，計(jì)算帶權(quán)路徑長(zhǎng)度。 A ： B. C. D. E2 - F8weightparentlchildrchild1A60002B70003C10004D50005E20006F8000700008000090000100000110000或采用課本上的算法計(jì)算，如下。 表0.4赫夫曼算法weightpare

19、ntlchildrchild1A69002B79003C17004D58005E27006F810007383588104791311121016116811290910結(jié)果同上。說明：同樣的一組權(quán)值可能構(gòu)造出不同的哈夫曼樹，結(jié)果不一定唯一，但帶權(quán)路徑長(zhǎng)度都是最小的。技巧：要使前一種方法構(gòu)造出的赫夫曼樹和課本上算法產(chǎn)生的一樣，只要把每次合并產(chǎn)生的二叉樹放在樹的集合的末尾，并且總是用兩個(gè)最小樹的前者作為左子樹后者作為右子樹。、習(xí)題一定義及性質(zhì)1、設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1則T中的葉子數(shù)為（D）A.5B.6C.7D.85.在下述結(jié)論中，正確的是（D）【南京

20、理工大學(xué)1999一、4（1分）】只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0；二叉樹的度為2;二叉樹的左右子樹可任意交換；深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A.B.C.D.16 .有關(guān)二叉樹下列說法正確的是（B）【南京理工大學(xué)2000、11（1.5分）】A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為217 .二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（C）A.2IB.2I-1-1C.2I-1D.2I-119. 一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,則這棵二叉樹最少有（B）結(jié)點(diǎn)A.2hB.2h-1C.2h+1D,h+12

21、4.高度為K的二叉樹最大的結(jié)點(diǎn)數(shù)為（C）。A.2kB.2k-1C.2k-1D.2k-1-1二叉樹由_（1）_,（2）,（3）三個(gè)基本單元組成。1.（1）根結(jié)點(diǎn)（2）左子樹（3）右子樹具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。9深度為H的完全二叉樹至少有（1）個(gè)結(jié)點(diǎn);至多有（2）個(gè)結(jié)點(diǎn);H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是（3。（1）2H-1（2）2H-1（3）H=log2N+122 .完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。V二二叉樹存儲(chǔ)在下列存儲(chǔ)形式中，哪一個(gè)不是樹的存儲(chǔ)形式？（D）A.雙親表示法B.孩子鏈表表示法C.孩子兄弟表示法D.順序存儲(chǔ)表示法二叉樹只能用二叉鏈表表示。X用鏈表（llink

22、-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n-1個(gè)空指針。x。應(yīng)為n+1個(gè)三二叉樹遍歷23 算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（B）C . abcde/*+ D .要交換其所有分支結(jié)點(diǎn)左、D .按層次ABCDEF中序遍歷結(jié)果為C . CBEDFA D ,不定dabec,中序遍歷序列是 debac ,它的前序遍歷是A.ab+cde/*B.abcde/+*+30.若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，遍歷方法最合適。CA.前序B.中序C.后序33.已知一棵二叉樹的前序遍歷結(jié)果為為（A）。A.CBEFDAB.FEDCBA34.已知某二叉樹的后序遍歷序列是(D)。A .

23、acbed B.decab.deabc D . cedba15.用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。X21.由一棵二叉樹的前序序列和后序序列可以唯一確定它。X。必須知道中序39.某二叉樹T有n個(gè)結(jié)點(diǎn)，設(shè)按某種順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為1,2,n,且有如下性質(zhì)：T中任一結(jié)點(diǎn)V,其編號(hào)等于左子樹上的最小編號(hào)減1,而V的右子樹的結(jié)點(diǎn)中，其最小編號(hào)等于V左子樹上結(jié)點(diǎn)的最大編號(hào)加1。這時(shí)是按（B）編號(hào)的。A.中序遍歷序列B.前序遍歷序列C.后序遍歷序列D.層次順序?qū)τ谇靶虮闅v與中序遍歷結(jié)果相同的二叉樹為（1）;F對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（2）。BA.一般二叉樹B

24、.只有根結(jié)點(diǎn)的二叉樹C.根結(jié)點(diǎn)無(wú)左孩子的二叉樹D.根結(jié)點(diǎn)無(wú)右孩子的二叉樹E.所有結(jié)點(diǎn)只有左子數(shù)的二叉樹F.所有結(jié)點(diǎn)只有右子樹的二叉樹四線索化52n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（C）A2nBnlCnlDn18.后序線索二叉樹是不完善的，要對(duì)它進(jìn)行遍歷，還需要使用棧。V47.一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個(gè)數(shù)是：（D）A.不確定B.0C.1D.249.若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為（C）A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)50.引入二叉線索樹的目的是（A）A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼

25、的速度B.為了能在二叉樹中方便的進(jìn)行插入與刪除C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一51.線索二叉樹是一種（C）結(jié)構(gòu)。A邏輯B邏輯和存儲(chǔ)C物理D線性54二叉樹在線索后，仍不能有效求解的問題是（D）。A.前（先）序線索二叉樹中求前（先）序后繼B.中序線索二叉樹中求中序后繼C.中序線索二叉樹中求中序前驅(qū)D.后序線索二叉樹中求后序后繼五哈弗曼樹13.設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（D）A.不確定B.2nC,2n+1D.2n-162下述編碼中哪一個(gè)不是前綴碼（B）。A（00，01，10，11）B（0，1，00，11）C（0，10，110，111）D（1，01，000，001）

26、樹與二叉樹轉(zhuǎn)換） 。 【青島大學(xué)2001 五、 5 （ 2 分） 】空 D 非空h ，則 t 的后根序遍歷是h 的27.利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（A.指向最左孩子B.指向最右孩子38將一棵樹t轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹A.前序遍歷B.中序遍歷C.后序遍歷（B）域?yàn)榭盏慕Y(jié)點(diǎn)有（C）個(gè)。55. 設(shè) F 是一個(gè)森林， 一個(gè)森林,B 是由 F 變換得的二叉樹。若F 中有 n 個(gè)非終端結(jié)點(diǎn)，則 B 中右指針An-1BnCn+1Dn+256.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的（B）。A.先序B.中序C.后序D.層次序六綜合1從概念上講，樹，森林和二叉

27、樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。1.樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同,也就是說樹(樹是森林的特例，即森林中只有一棵樹的特殊情況)可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有三：一是二叉樹的度至多為2,樹無(wú)此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分枝的情況下，也必須指出是左子樹還是右子樹，樹無(wú)此限制；三是二叉樹允許為空，樹一般不允許為空(個(gè)別書上允許為空)。71.設(shè)二叉樹BT的存儲(chǔ)結(jié)構(gòu)如下：12345678910Lchild00237580101D

28、ataJHFDBACEGIRchild0009400000其中BT為樹根結(jié)點(diǎn)的指針，其值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題：(1)畫出二叉樹BT的邏輯結(jié)構(gòu)；(2)寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點(diǎn)序列；(3)畫出二叉樹的后序線索樹。78.設(shè)有正文AADBAACACCDACAC期D,集為A,B,C,D,設(shè)計(jì)一套二進(jìn)制編碼，使得上述正文的編碼最短。78.字符A,B,C,D出現(xiàn)的次數(shù)為9,1,5,3。其哈夫曼編碼如下A:1,B:000,C:01,D:00175.由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實(shí)現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請(qǐng)寫出程序所缺的語(yǔ)句。#defineMAX100typedefstructNodecharinfo;structNode*llink,*rlink;TNODE;c