C++ 單元測試 樹、二叉樹、哈夫曼編碼

1、單元練習(xí)7一判斷題（下列各題，正確的請在前面的括號內(nèi)打；錯誤的打 ）（）（1）樹結(jié)構(gòu)中每個結(jié)點最多只有一個直接前驅(qū)。（）（2）完全二叉樹一定是滿二查樹。（）（3）在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。（）（4）一棵二叉樹中序遍歷序列的最后一個結(jié)點，必定是該二叉樹前序遍歷的最后一個結(jié)點。（）（5）二叉樹的前序遍歷中，任意一個結(jié)點均處于其子女結(jié)點的前面。（）（6）由二叉樹的前序遍歷序列和中序遍歷序列，可以推導(dǎo)出后序遍歷的序列。（）（7）在完全二叉樹中，若一個結(jié)點沒有左孩子，則它必然是葉子結(jié)點。（）（8）在哈夫曼編碼中，當(dāng)兩個字符出現(xiàn)的頻率相同，其編碼也相同，對于這種情況應(yīng)該做特殊處

2、理。（）（9）含多于兩棵樹的森林轉(zhuǎn)換的二叉樹，其根結(jié)點一定無右孩子。（）（10）具有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點。 二填空題（1） 在樹中，一個結(jié)點所擁有的子樹數(shù)稱為該結(jié)點的 度 。（2） 度為零的結(jié)點稱為 葉（或葉子，或終端） 結(jié)點。（3） 樹中結(jié)點的最大層次稱為樹的 深度（或高度） 。（4） 對于二叉樹來說，第i層上至多有 2i-1 個結(jié)點。（5） 深度為h的二叉樹至多有 2h-1 個結(jié)點。（6） 由一棵二叉樹的前序序列和 中序 序列可唯一確定這棵二叉樹。（7） 有20個結(jié)點的完全二叉樹，編號為10的結(jié)點的父結(jié)點的編號是 5 。（8） 哈夫曼樹是帶權(quán)路徑長度 最小 的二叉樹。（

3、9） 由二叉樹的后序和 中序 遍歷序列，可以唯一確定一棵二叉樹。（10） 某二叉樹的中序遍歷序列為: DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為：DABEC 。（11） 設(shè)一棵二叉樹結(jié)點的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，則二叉樹中葉結(jié)點是： E、F、H 。（12） 已知完全二叉樹的第8層有8個結(jié)點，則其葉結(jié)點數(shù)是 68 。（13） 由樹轉(zhuǎn)換成二叉樹時，其根結(jié)點無 右子樹 。（14） 采用二叉鏈表存儲的n個結(jié)點的二叉樹，一共有 2n 個指針域。（15） 采用二叉鏈表存儲的n個結(jié)點的二叉樹，共有空指針 n+1 個。（16） 前序為A，B，C且后序為

4、C，B，A的二叉樹共有 4 種。ACBABCABCACB（17）三個結(jié)點可以組成 2 種不同形態(tài)的樹。（18）將一棵完全二叉樹按層次編號，對于任意一個編號為i的結(jié)點，其左孩子結(jié)點的編號為： 2*i 。（19）給定如下圖所示的二叉樹，其前序遍歷序列為： ABEFHCG 。ABFGHDCE（20）給定如下圖所示的二叉樹，其層次遍歷序列為： ABCEFGH 。ABFGHDCE三選擇題（1）樹最適合用來表示（ D ）。 A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素 C元素之間無聯(lián)系的數(shù)據(jù) D元素之間有分支的層次關(guān)系（2）前序為A，B，C的二叉樹共有（ D ）種。 A2 B3 C4 D5（3）根據(jù)二叉樹的定義，具有3

5、個結(jié)點的二叉樹有（ C ）種樹型。 A3 B4 C5 D6（4）在一棵具有五層的滿二叉樹中，結(jié)點的總數(shù)為（ B ） A16 B31 C32 D33（5）具有64個結(jié)點的完全二叉樹的深度為（ C ） A5B6 C7 D8（6）任何一棵二叉樹的葉結(jié)點在前序、中序、后序遍歷序列中的相對次序（ A ）。 A不發(fā)生改變 B發(fā)生改變 C不能確定 D以上都不對（7）A，B為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，A在B前的條件是（ C ）。 AA在B右方 BA是B祖先 CA在B左方 DA是B子孫（8）下列4棵樹中，（ B ）不是完全二叉樹。 A B C DABECDABCDABEFCDABEGFDCD（9）如

6、右圖所示的二叉樹，后序遍歷的序列是（ D ）ABADECFGHI A A、B、C、D、E、F、G 、H、I B A、B、D、H、I、E、C、F、G C H、D、I、B、E、A、F、C、G D H、I、D、E、B、F、G、C、A（10）對于下邊的二叉樹，其中序序列為 （ A ）ADBEHAFCG BDBHEAFCG CABDEHCFG DABCDEFGH （11）某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為: DEBAC，則前序遍歷序列為（ D ）。 A ACBEDBDECABCDEABC DCEDBA（12）具有n（n>1）個結(jié)點的完全二叉樹中，結(jié)點i（2i>n）的左孩子結(jié)

7、點是（ D ）。A2iB2i+1C2i-1 D不存在（若2i<=n，則答案為A）（13）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ A ）。A唯一的 B有多種C有多種，但根結(jié)點都沒有左孩子 D有多種，但根結(jié)點都沒有右孩子（14）將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點編號，根結(jié)點的編號為1，則編號為45的結(jié)點的左孩子編號為（ B ）。 A46 B47 C90 D91（15）將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點編號，根結(jié)點的編號為1，則編號為49的結(jié)點的右孩子編號為（ B ）。 A98 B99 C50 D100（16）二叉樹按某種順序線索化后，

8、任一結(jié)點均有指向其前驅(qū)和后繼的線索，這種說法（ B ）。 A正確 B錯誤C不確定 D都有可能（17）下列陳述正確的是（ D ）。A二叉樹是度為2的有序樹B二叉樹中結(jié)點只有一個孩子時無左右之分C二叉樹中必有度為2的結(jié)點 D二叉樹中最多只有兩棵子樹，且有左右子樹之分（18）用5個權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是（ B ）。32 33 34 15 （ 先構(gòu)造哈夫曼樹，WPL=（1+2）*3+（3+4+5）*2=33 ）（19）在樹結(jié)構(gòu)中，若結(jié)點B有4個兄弟，A是B的父親結(jié)點，則A的度為為（ C ）。 A3 B4 C5 D6（20）二叉樹的葉結(jié)點個數(shù)比度為2的結(jié)點的個數(shù)（

9、C ）。 A無關(guān) B相等 C多一個 D少一個四. 簡答題1 已知一棵樹邊的集合如下，請畫出此樹，并回答問題。(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)（1）哪個是根結(jié)點？（2）哪些是葉結(jié)點？（3）哪個是G的雙親？（4）哪些是G的祖先？（5）哪些是G的孩子？（6）哪些是E的子孫？（7）哪些是E的兄弟？哪些是F的兄弟？（8）結(jié)點B和N的層次各是多少？（9）樹的深度是多少？（10）以結(jié)點C為根的子樹的深度是多少？（11）樹的度數(shù)是多少？答：（1）A是根結(jié)點。（2）葉結(jié)點：M，N，D，J，K

10、，F(xiàn)，I。（3）G的雙親：C。（4）G的祖先：A，C。（5）G的孩子：J，K。（6）E的子孫：L，M，N。（7）E的兄弟：D；F的兄弟：G，H。（8）結(jié)點B的層次為2；結(jié)點N的層次是5。（9）樹的深度是5。（10）以結(jié)點C為根的子樹的深度是3。（11）樹的度數(shù)是3。2 設(shè)下列二叉樹是與某森林對應(yīng)的二叉樹，試回答下列問題。DABEGICFHJLK（1）森林中有幾棵樹？（2）每一棵樹的根結(jié)點分別是什么？（3）第一棵樹有幾個結(jié)點？（4）第二棵樹有幾個結(jié)點？（5）森林中有幾個葉結(jié)點？ 解： （1） 4 （2） A，C，G，K （3） 6 （4） 2 （5） 73二叉樹按中序遍歷的結(jié)果為：ABC，試問有

11、幾種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果？并畫出這些二叉樹。答：（1） 5種。ABCAADCBBABCACCB（2） 4. 分別畫出具有3個結(jié)點的樹和三個結(jié)點的二叉樹的所有不同形態(tài)。答：（1） 三個結(jié)點的樹 （2） 三個結(jié)點的二叉樹樹 五. 應(yīng)用題1已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：A，C，D，B，G，I，H，F(xiàn)，E和A，B，C，D，E，F(xiàn)，G，H，I。請畫出該二叉樹，并寫出它的前序遍歷的序列。BCHDDFGEIA答：恢復(fù)的二叉樹為： 其前序遍歷的序列為：E B A D C F H G I2已知一棵二叉樹的前序遍歷和中序遍歷的序列分別為： A，B，D，G，H，C，E，F(xiàn)，I和G，

12、D，H，B，A，E，C，I，F(xiàn)。 請畫出此二叉樹，并寫出它的后序遍歷的序列。GHABDCEFI答：恢復(fù)的二叉樹為： 其后序遍歷的序列為：G H D B E I F C A3 已知一棵樹的層次遍歷的序列為：ABCDEFGHIJ，中序遍歷的序列為：DBGEHJACIF，請畫出該二叉樹，并寫出它的后序遍歷的序列。ABCHDDFGEIJ解：后序遍歷的序列：D G J H E B I F C A 4. 把下列一般樹轉(zhuǎn)換為二叉樹12435678(1) (2) ABFEGHIJCD12468 8D537ABCHDDFGEIJ解：（1） （2）5. 把下列森林轉(zhuǎn)換為二叉樹FGKIJHACBDEKABCHDDF

13、GEIJ解：6把下列二叉樹還原為森林ADBICHFGE解：還原后的二叉樹為：ABCHDDFGEI7 某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲，其結(jié)構(gòu)如下：1234567891011121314151617181920EAFDHCGIB（1）畫出該二叉樹（3分）（2）寫出按層次遍歷的結(jié)點序列（2分）解：ADHFGECBI（1）（2）層次遍歷的結(jié)點序列：E A F D H C G I B8 某二叉樹的存儲如下：12345678910lchild00237580101dataJHFDBACEGIrchild0009400000 其中根結(jié)點的指針為6，lchild、rchild分別為結(jié)點的左、右孩子的指針域，d

14、ata為數(shù)據(jù)域。（1）畫出該二叉樹（3分）（2）寫出該樹的前序遍歷的結(jié)點序列（2分）解：BDJHGACFEI（1） （2）前序遍歷的結(jié)點序列：A B C E D F H G I J9 給定如圖所示二叉樹T，請畫出與其對應(yīng)的中序線索二叉樹。0828D25D33D40D60D08D54D55D33解： （1） 中序遍歷序列：55 40 25 60 28 08 33 54（2） 中序線索二叉樹：NULLNULL0828D25D33D40D60D08D54D55D10. 畫出表達式：-A+B-C+D 的標(biāo)識符樹，并求它們的后綴表達式。解： +¯+¯BDCAD0后綴表達式：0 A B

15、 + C D + 11 畫出表達式：（A+B/C-D）*（E*（F+G）的標(biāo)識符樹，并求它們的后綴表達式。ABC+DDFGE/+*¯*解：后綴表達式：A B C / + D E F G + * *12 對于算術(shù)表達式（A+B*C/D）*E+F*G，畫出標(biāo)識符樹，并求它們的后綴表達式。解：*EGFD*B+*AD/C后綴表達式：A B C D / * + E * F G * +13 給定一個權(quán)集W=4，5，7，8，6，12，18，試畫出相應(yīng)的哈夫曼樹，并計算其帶權(quán)路徑長度WPL。351325D12660181798D457解：4 5 6 7 8 12 18 9 13 17 25 35 6

16、0 WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15914 給定一個權(quán)集W=3，15，17，14，6，16，9，2，試畫出相應(yīng)的哈夫曼樹，并計算其帶權(quán)路徑長度WPL。491733D1698229201514D56113D2解 2 3 6 9 14 15 16 175 29 33 11 20 49 82WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=22915 假設(shè)用于通信的電文僅由A、B、C、D、E、F、G 8個字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10。試為這8個字母設(shè)計哈夫曼編碼。解：以權(quán)值：2、3、6、7、

17、10、19、21、32構(gòu)造哈夫曼樹：651911281740D213260D10000D023D710D00000111111 01字母編號對應(yīng)編碼出現(xiàn)頻率A10107B0019C100002D10016E1132D100013E0121F101110六算法設(shè)計題以二叉鏈表為存儲結(jié)構(gòu)，設(shè)二叉樹BT結(jié)構(gòu)為：typedef struct BTchar data;BT *lchild;BT *rchild;BT;1 求二叉樹中的度數(shù)為2的結(jié)點。2 求二叉樹中值為最大的元素。3 將二叉樹各結(jié)點存儲到一維數(shù)組中。4 前序輸出二叉樹中各結(jié)點及其結(jié)點所在的層號。5 求二叉樹的寬度6 交換二叉樹各結(jié)點的左右子

18、樹。7 寫出在二叉樹中查找值為x的結(jié)點在樹中層數(shù)的算法。解：1 求二叉樹中的度數(shù)為2的結(jié)點。void count(BT t) if (t) if (t->lchild && t->rchild) k+; count(t->lchild); count(t->rchild);2. 求二叉樹中值為最大的元素。int maxnode(BT t, int max) if (t) if (t->data>max) max=t->data;max=maxnode(t->lchild,max);max=maxnode(t->rchild,

19、max);3將二叉樹各結(jié)點存儲到一維數(shù)組中。void create(BT t,int a ,int i) if (t) ai=t->data; create (t->lchild, a, 2*i); create (t->rchild, a, 2*i+1);4前序輸出二叉樹中各結(jié)點及其結(jié)點所在的層號。void preorderlevel (BT t,int h) / t的層數(shù)為h if (t!=NULL) printf (“%d,%d”,t->data, h); preorderlevel (t->lchild, h+1); preorderlevel (t-&g

20、t;rchild, h+1);5. 求二叉樹的寬度 思想：按層遍歷二叉樹，采用一個隊列q，讓根結(jié)點入隊列，最后出隊列，若有左右子樹，則左右子樹根結(jié)點入隊列，如此反復(fù)，直到隊列為空。 int Width(BT *T) int front=-1,rear=-1; / 隊列初始化 int flag=0,count=0,p; / p用于指向樹中層的最右邊的結(jié)點，標(biāo)志flag記錄層中結(jié)點數(shù)的最大值 if (T!=NULL) rear+; qrear=T; flag=1; p=rear; while (front<p) front+; T=qfront; if (T->lchild!=NULL

21、) rear+; qrear=T->lchild; count+; if (T->rchild!=NULL) rear+; qrear=T->rchild; count+; if (front=p) / 當(dāng)前層已遍歷完畢 if (flag<count) flag=count; count=0; p=rear; / p指向下一層最右邊的結(jié)點 / endwhile return(flag); 6解：借助棧來進行對換。Swap(BinTree*T) BinTree *stack100, *temp; int top=-1; root=T; if (T!=NULL) top+;

22、 stacktop=T; while(top>-1) T=stacktop; top-; if (T->child!=NULL|T->rchild!=NULL) / 交換結(jié)點的左右指針 temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; if (T->lchild!=NULL) top+; stacktop=T->lchild; if (T->rchild!=NULL) top+; stacktop=T->rchild; main() int I,j,k,l; printf(

23、“n”); root=CreateBinTree(); Inorder (root);i=CountNode (root); j=CountLeafs (root);k=Depth (root); l=Width (root); printf(“nThe Node s Number:%d”,i); printf(“nThe Leafss Number:%d”,j); printf(“nThe Depth is:%d”,k); printf(“nThe width is:%d”,l); Swap(root); Printf(“nThe swapTree is:”);Inorder(root);7

24、解：int h=-1,lh=1,count=0;charx=c; / 賦初值Level (BinTree T,int h,int lh) / 求X結(jié)點在樹只的層樹 if (T=Null) h=0; else if (T->data=x) h=lh; count=h; else h+; Level(T->lchild,h,lh); if (h=-1) Level(T->rchild,h,lh); main() BinTree *(*newroot);Printf(“n”);Root=CreateBinTree();Inorder(root);Printf(“n”);Level(

25、root,h,lh);Printf(“%d”,count);模擬考題一 讀程序，寫出運行結(jié)果1二叉樹的結(jié)構(gòu)如圖所示，試寫出執(zhí)行下列算法后的輸出結(jié)果： 。（用大寫的英文字母表示，字母之間不要任何間隔符號，最后一個字母后面也不要間隔符號）CFBDADGEtypedef struct BT datatype data; BT *lchild;BT *rchild;BT;void Preorder(BT *T) if (T!=NULL) cout<< T->data; Preorder(T->lchild); Preorder(T->rchild); 解：ABCEDFG

26、先序遍歷2二叉樹的結(jié)構(gòu)如圖所示，試寫出執(zhí)行下列算法后的輸出結(jié)果： 。typedef struct BTCFBDADGE datatype data; / 定義結(jié)點BT *lchild;BT *rchild;BT;int BTD(BT *T) int ldep,rdep;if (T=NULL)return 0;else ldep= BTD (T->lchild); rdep= BTD (T->rchild); if (ldep>rdep)return ldep+1; elsereturn rdep+1;解：4 （求二叉樹深度）3二叉樹的結(jié)構(gòu)如圖所示，試寫出執(zhí)行下列算法后，cou

27、nt的值為多少？CFBDADGEtypedef struct BT datatype data; / 定義結(jié)點BT *lchild;BT *rchild;BT;int count=0;void Leafnum(BT *T) if (T!=NULL) if(T->lchild=NULL && T->rchild=NULL)count+; Leafnum(T->lchild); Leafnum(T->rchild); 解：3 （求葉結(jié)點數(shù)） (2，3，4改為程序填空)二 程序填空1填空完成二叉樹按層次遍歷的程序typedef struct BT dataty

28、pe data; / 定義結(jié)點BT *lchild;BT *rchild;BT;void Levelorder(BT *T) / 層次遍歷 int i,j; BT *q100,*p; p=T; if ( p!=NULL ) i=1;qi=p;j=2; while (i!=j) p=qi;cout<< p->data ; if ( p->lchild!=NULL ) qj= p->lchild ;j+; if (p->rchild!=NULL) qj= p->rchild ;j+; i+; 三 應(yīng)用題1 將下列二叉樹轉(zhuǎn)換為森林。DABEGICFHJK解：

29、DABIHDECFGJK2 畫出和下列二叉樹相應(yīng)的森林。DABHCJEKGFIM解：（根右邊的子樹肯定是森林，而孩子結(jié)點的右子樹均為兄弟）3 某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲，其結(jié)構(gòu)如下：1234567891011121314151617181920EAFDHCGIB（1）畫出該二叉樹（2分）（2）寫出結(jié)點值為D的父結(jié)點及左、右子樹（3分）解：ADHFGECBI（1）（2） D的父結(jié)點為AD的左子樹為CD的右子樹為空4 某二叉樹的存儲如下：12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000 其中根結(jié)點的指針為6，lchild、rchild分別為結(jié)點的左、右孩子的指針域，data為數(shù)據(jù)域。（1）畫出該二叉樹（3分）（2）寫出該樹的中序遍歷的結(jié)點序列（2分）BDJHGACFEI解：（1） （2）中序遍歷的結(jié)點序列：E C B H F D J I G A5 某二叉樹的存儲如下：123