數(shù)據(jù)結(jié)構(gòu)ch4作業(yè)

1、15個結(jié)點(diǎn)僅有右孩子，度節(jié)點(diǎn)數(shù) n1，2度節(jié)點(diǎn)數(shù) n2。n1=10+15=25 A B G C F D E A B F D J H - F 15個結(jié)點(diǎn)僅有右孩子，度節(jié)點(diǎn)數(shù) n1，2度節(jié)點(diǎn)數(shù) n2。n1=10+15=25 A B G C F D E A B F D J H - F G H I G I 第四章習(xí)題4.3 如果已知一棵二叉樹有 20個葉子結(jié)點(diǎn)，有 10個結(jié)點(diǎn)僅有左孩子，求出該二叉樹的結(jié)點(diǎn)數(shù)目。解：設(shè)結(jié)點(diǎn)總數(shù)為 n，葉子數(shù) n0，1由題意得： n0=20 有由二叉樹性質(zhì)得： n2=n0-1=20-1=19 所以，總結(jié)點(diǎn)數(shù) n= n0+ n1+ n2=20+25+19=64 4.10證明

2、：由二叉樹的先序序列和中序序列能唯一確定一棵二叉樹，并分別由下面的兩個序列構(gòu)造出相應(yīng)的二叉樹：先序： ABCDEFGHI 先序： ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF 解：A B C H D I E 對應(yīng)二叉樹J 對應(yīng)二叉樹4.12已知一棵二叉樹的先序、中序和后序序列如下，其中各有一部分未給出其值，請構(gòu)造出該二叉樹。先序： A B C D E F G H I J 中序： C B E D A H G F I J后序： C ED B H G J I F AC 4.17設(shè)計(jì)算法以輸出每個結(jié)點(diǎn)到根結(jié)點(diǎn)之間的路徑上的所有結(jié)點(diǎn)的值。E 解：算法如下：/先序遍歷查找結(jié)點(diǎn)

3、 x，打印到根節(jié)點(diǎn)路徑void BiTreeSearchNR(BiNode* pBT, elementType x, BiNode* &pR) -完整版學(xué)習(xí)資料分享- -WORD 格式-可編輯-專業(yè)資料- - BiNode* p; seqStack S; int tagMaxLen; /標(biāo)記左子樹、右子樹initStack(S); /初始化棧p=pBT; while(p | !stackEmpty(S) if(p) /p!=NULL pushStack(S, p); /當(dāng)前根節(jié)點(diǎn)指針 p 入棧tagS.top=0; /標(biāo)記遍歷左子樹/判定 p是否目標(biāo)結(jié)點(diǎn)if(p-data=x) /返回 p指針

4、pR=p; while(!stackEmpty(S) /找到目標(biāo)結(jié)點(diǎn)，打印到根節(jié)點(diǎn)的路徑 popStack(S,p); coutdatalChild; /遍歷左子樹 else /p=NULL 但是棧不空 stackTop(S, p); /取棧頂，但不退棧，以便遍歷 p的右子樹if(tagS.top=0) / 說明 p 的右子樹尚未遍歷，設(shè)置標(biāo)記，遍歷右子樹 tagS.top=1; p=p-rChild; else /tagS.top=1 ，說明棧頂結(jié)點(diǎn) p的左右子樹都已經(jīng)遍歷， 且沒有找到目標(biāo)，p直接彈出 popStack(S, p); p=NULL; /上面出棧的 p已經(jīng)沒有，回去循環(huán)取棧頂

5、的下一個元素 4.24 將下圖中的森林轉(zhuǎn)換為對應(yīng)的二叉樹。-完整版學(xué)習(xí)資料分享JEDJEGMCEICEI- KGFKLNFJGKJOLHOPGKOFLNILMPMMNNO-WORD 格式-可編輯-專業(yè)資料- JEDJEGMCEICEI- KGFKLNFJGKJOLHOPGKOFLNILMPMMNNOABC解：轉(zhuǎn)換后的二叉樹如下圖ABCD FHI4.28將下圖中的二叉樹轉(zhuǎn)換為對應(yīng)的森林。ABDHABDH4.34 以數(shù)據(jù)集合 4,6,8,10,12,15,18,20,22 中的元素為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈夫曼樹，并計(jì)算其帶權(quán)路徑長度。解：WPL=115+44+71+22+33+38+10+18=

6、351 -完整版學(xué)習(xí)資料分享71 22 12 6 - 33 15 8 38 18 10 18 20 -WORD 格式-可編輯-專業(yè)資料- 71 22 12 6 - 33 15 8 38 18 10 18 20 =4*(4+6+8+10)+3*(12+15+18+20)+2*22=351 115 44 22 10 4 4.35 已 知 一 個 文 件 中 僅 有 10 個 不 同 的 字 符 ， 各 字 符 出 現(xiàn) 的 個 數(shù) 分 別 為100,150,180,200,260,300,350,390,400,500。試對這些符號重新編碼， 以壓縮文件的規(guī)模， 并求出其壓縮后的規(guī)模以及壓縮比（壓縮

7、前后的規(guī)模比） 。解：采用哈夫曼編碼，根據(jù)題意得到如下哈夫曼樹和哈夫曼編碼。等長編碼：若采用等長編碼， 10個不同字符需要 4位編碼，則總碼長度 =4*(100+150+180+200+260+300+350+390+400+500)=11320 Haffman 編碼，碼長 =WPL WPL=2830+1160+1670+510+650+770+900+250+380=9120 =4*(100+150+180+200)+3*(260+300+350+390+400+500)=9120 壓縮比 =9120/11320=80.6% -完整版學(xué)習(xí)資料分享1670 650 260 150 - 770 300 180 900 350 200 380 390 400 50