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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第四章習(xí)題4.3如果已知一棵二叉樹有20個葉子結(jié)點，有10個結(jié)點僅有左孩子，15個結(jié)點僅有右孩子，求出該二叉樹的結(jié)點數(shù)目。解：設(shè)結(jié)點總數(shù)為n，葉子數(shù)n0，1度節(jié)點數(shù)n1，2度節(jié)點數(shù)n2。由題意得：n0=20 n1=10+15=25有由二叉樹性質(zhì)得：n2=n0-1=20-1=19所以，總結(jié)點數(shù) n= n0+ n1+ n2=20+25+19=644.10證明：由二叉樹的先序序列和中序序列能唯一確定一棵二叉樹，并分別由下面的兩個序列構(gòu)造出相應(yīng)的二叉樹：先序：ABCDEFGHI 先序：ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF 解：ABCDEF

2、GHIABCDEFGHIJ 對應(yīng)二叉樹 對應(yīng)二叉樹 ABCDEFGHIJ4.12已知一棵二叉樹的先序、中序和后序序列如下，其中各有一部分未給出其值，請構(gòu)造出該二叉樹。 先序：A B C D E F G H I J中序：C B E D A H G F I J后序：C E D B H G J I F A4.17設(shè)計算法以輸出每個結(jié)點到根結(jié)點之間的路徑上的所有結(jié)點的值。解：算法如下：/先序遍歷查找結(jié)點 x，打印到根節(jié)點路徑void BiTreeSearchNR(BiNode* pBT, elementType x, BiNode* &pR)BiNode* p;seqStack S;int t

3、agMaxLen; /標(biāo)記左子樹、右子樹initStack(S); /初始化棧p=pBT;while(p | !stackEmpty(S)if(p) /p!=NULLpushStack(S, p); /當(dāng)前根節(jié)點指針 p 入棧tagS.top=0; /標(biāo)記遍歷左子樹/判定p是否目標(biāo)結(jié)點if(p->data=x)/返回p指針pR=p;while(!stackEmpty(S) /找到目標(biāo)結(jié)點，打印到根節(jié)點的路徑popStack(S,p);cout<<p->data<<", "break; /退出循環(huán)elsep=p->lChild; /遍

4、歷左子樹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é)點p的左右子樹都已經(jīng)遍歷，且沒有找到目標(biāo)，p直接彈出popStack(S, p);p=NULL; /上面出棧的p已經(jīng)沒有，回去循環(huán)取棧頂?shù)南乱粋€元素4.24 將下圖中的森林轉(zhuǎn)換為對應(yīng)的二叉樹。 解：轉(zhuǎn)換后的二叉樹如下圖 4.28將下圖中的二叉樹轉(zhuǎn)換為對應(yīng)的森林。 4.34以數(shù)據(jù)集合4,6,8,10,12,15

5、,18,20,22中的元素為葉子結(jié)點的權(quán)值構(gòu)造一棵哈夫曼樹，并計算其帶權(quán)路徑長度。解：WPL=115+44+71+22+33+38+10+18=351 =4*(4+6+8+10)+3*(12+15+18+20)+2*22=351461012222244115711518338101820384.35已知一個文件中僅有10個不同的字符，各字符出現(xiàn)的個數(shù)分別為100,150,180,200,260,300,350,390,400,500。試對這些符號重新編碼，以壓縮文件的規(guī)模，并求出其壓縮后的規(guī)模以及壓縮比（壓縮前后的規(guī)模比）。解：采用哈夫曼編碼，根據(jù)題意得到如下哈夫曼樹和哈夫曼編碼。等長編碼：若采用等長編碼，10個不同字符需要4位編碼， 則總碼長度=4*(100+150+180+200+260+300+350+390+400+500)=11320Haffman編碼，碼長=WPLWPL=2830+1160+1670+510+650+770+900+250+380=9120 =4*(100+150+180+200)+3*(260+300+350+390+400+500)=912