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

2、：由二叉樹的先序序列和中序序列能唯一確定一棵二叉樹，并分別由下面的兩個序列構造出相應的二叉樹：先序： ABCDEFGHI 先序： ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF 解：A B C H D I E 對應二叉樹J 對應二叉樹4.12已知一棵二叉樹的先序、中序和后序序列如下，其中各有一部分未給出其值，請構造出該二叉樹。先序： 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設計算法以輸出每個結點到根結點之間的路徑上的所有結點的值。E 解：算法如下：/先序遍歷查找結點

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

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

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

6、351 -完整版學習資料分享71 22 12 6 - 33 15 8 38 18 10 18 20 -WORD 格式-可編輯-專業資料- 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 個 不 同 的 字 符 ， 各 字 符 出 現 的 個 數 分 別 為100,150,180,200,260,300,350,390,400,500。試對這些符號重新編碼， 以壓縮文件的規模， 并求出其壓縮后的規模以及壓縮比（壓縮

7、前后的規模比） 。解：采用哈夫曼編碼，根據題意得到如下哈夫曼樹和哈夫曼編碼。等長編碼：若采用等長編碼， 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% -完整版學習資料分享1670 650 260 150 - 770 300 180 900 350 200 380 390 400 50