




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030年中國高溫燙布市場分析及競爭策略研究報告
- 2025至2030年中國門框式輻射測量儀市場分析及競爭策略研究報告
- 2025至2030年中國針織羊絨圍巾市場分析及競爭策略研究報告
- 2025至2030年中國脈通沖劑市場分析及競爭策略研究報告
- 2025至2030年中國精制復(fù)合紙市場分析及競爭策略研究報告
- 2025至2030年中國比較量儀市場分析及競爭策略研究報告
- 2025至2030年中國早早孕測試盒市場分析及競爭策略研究報告
- 2025至2030年中國手壓式封口機(jī)市場分析及競爭策略研究報告
- 2025至2030年中國工業(yè)用鐘市場分析及競爭策略研究報告
- 先進(jìn)成圖技術(shù)教與學(xué)智慧樹知到課后章節(jié)答案2023年下青島濱海學(xué)院
- 初級會計師考試 經(jīng)濟(jì)法基礎(chǔ)課件
- 哈工大機(jī)械原理課程設(shè)計-棒料輸送線布料裝置(方案1)
- 稀土生產(chǎn)工藝流程圖礦的開采技術(shù)
- (15.1.1)-緒論2思想政治教育概念的歷史演變
- 高速鐵路接觸網(wǎng)壓接式電連接安裝工法CREC-01-2018-60
- 上海交通大學(xué)畢業(yè)生思想政治品德情況表
- 人教版(2023版)初中語文九年級上冊全冊同步練習(xí)+單元綜合訓(xùn)練+專項訓(xùn)練+期中期未測試合集(含答案)【可編輯可打印】
- 23秋國家開放大學(xué)《EXCEL在財務(wù)中的應(yīng)用》形考作業(yè)1-4參考答案
- 有限空間監(jiān)理實施細(xì)則
- 新產(chǎn)品制造可行性及風(fēng)險分析報告
評論
0/150
提交評論