【導(dǎo)讀】樹的定義和基本術(shù)語。個集合本身又是一棵樹,并稱為根的子樹。有限集合T1，T2……Tm“互不相交”，即任意兩個集。合不能有相同的結(jié)點。樹的各個結(jié)點有不同層次關(guān)系，這種關(guān)系通常用圖形。畫在最上層，如圖。數(shù)或者后繼結(jié)點數(shù)稱為該結(jié)點的度。0的結(jié)點叫作末端。間互稱為兄弟結(jié)點。所有結(jié)點均稱之為該結(jié)點的子孫結(jié)點。點為第一層，其兒子結(jié)點為第二層。結(jié)點的層數(shù)逐層由上而下計算。點的最大層數(shù)叫做此樹的深度或高度。樹形結(jié)構(gòu)的邏輯特征可用樹中結(jié)點之間。為左子樹和右子樹的二叉樹組成。都是滿的，則稱此二叉樹為滿二叉樹。如果一個二叉樹中，除最下一層的各結(jié)點度。有l(wèi)ogn<k可知，k≥?對于完全二叉樹，對其結(jié)點采用“按層編號”比較方。入一維數(shù)組的第i個單元。

　　

【正文】 曼樹 哈夫曼編碼算法 (續(xù)） for (i=n。 im。 i++) /*構(gòu)造哈夫曼樹 */ { select(i1, s1, s2)。 /*在 ht[k]（ 0=k=i1)中，選擇兩 ht[s1].parent=i。 /*個其雙親域為空，且權(quán)值最小的 ht[s2].parent=i。 /*結(jié)點，它們在 ht[]中的序號為 ht[i]. lch=s1。 /* S1, S2。 ht[i]. rch]=s2。 ht[i].weight=ht[s1].weight + ht[s2].weight。 } 求哈夫曼樹 哈夫曼編碼算法 (續(xù)） for (i=0。 in。 i++) /*求哈夫曼編碼 */ { hcd[i]. start=n。 /*從 n起遞減 */ k=i。 f=ht[k].parent。 /*f是 K的父親 while (f != 1) /*若 f=1，則一個字符個編碼已經(jīng)結(jié)束 { hcd [i]. start 。 If (ht[f]. lch==k) /*判斷 k是 f的左兒子 ? 右兒子 ? hcd[i]. bits [hcd [i]. start]=?0?。 else hcd[i]. bits [hcd [i]. start]=?1?。 k=f。 f=ht [f]. parent。 /*繼續(xù)向上找，直到根 } } } ?例：已知某系統(tǒng)在通迅中只出現(xiàn) 8個字符，其頻率為 , , , , , , , . 試設(shè)計哈夫曼編碼。 設(shè)權(quán) W={5， 29， 7， 8， 14， 23， 3， 11} n=8， m=15 eight parent lch rch 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 8 0 0 29 13 0 0 7 9 0 0 8 9 0 0 14 11 0 0 23 12 0 0 3 8 0 0 11 10 0 0 8 10 0 6 15 11 2 3 19 12 7 8 29 13 4 9 42 14 5 10 58 14 1 11 100 0 12 13 例 ?試寫出如圖所示二叉樹的前序、中序和后序遍歷序列。 4 2 3 1 7 5 6 8 9 例 ?解 : 前序 : 9 中序 : 9 后序 : 1 例 ?設(shè)數(shù)據(jù)集合d={1,12,5,8,3,10,7,13,9},試依次取 d中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹，并給出該二叉排序樹中序遍歷序列。 ?解：本題產(chǎn)生的二叉排序樹如圖所示，中序遍歷序列為： 1， 3， 5，7， 8， 9， 10， 12，13。 12 1 5 13 8 3 10 7 9 例 ?假設(shè)用于通信的電文由字符集 {a， b， c，d， e， f， g， h}中的字母構(gòu)成，這 8個字母在電文中出現(xiàn)的概率分別為{,,}試為這 8個字母設(shè)計哈夫曼編碼。 ?解：哈夫曼樹如下面的圖所示 : ? a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 h:0011 0 .3 2 0 .1 9 0 .2 1 0 0 1 0 1 1 1 0 .3 2 0 .6 0 .2 8 0 .0 5 0 .0 2 0 .0 3 0 .0 6 0 .0 7 0 .1 0 0 1 1 0 1 0 1 0 .1 1 0 .1 7 例 ?假設(shè)二叉樹采用鏈接存儲方式，編寫一個中序遍歷二叉樹的非遞歸函數(shù)。 ?解：根據(jù)中序遍歷二叉樹的遞歸定義，轉(zhuǎn)換成非遞歸函數(shù)時，用一個棧保存返回的結(jié)點。先掃描根結(jié)點的所有左結(jié)點并入棧，出棧一個結(jié)點，訪問之，然后掃描該結(jié)點的右結(jié)點并入棧，再掃描右結(jié)點的所有左結(jié)點并入棧，如此這樣，直到?？諡橹?。 例6.4算法 void inorder (btree *b) { btree stack[m0], *p。 int top=0。 p=b。 do { while(p!=NULL) /*掃描左結(jié)點 */ { top++。 stack[top]=p。 p=pleft。 } 例6.4算法續(xù) if (top0) { p=stack[top]。 /*p所指結(jié)點為無左子樹的結(jié)點或其左子樹已遍歷過 */ top。 printf(“%d”,pdata)。 /*訪問結(jié)點 */ p=pright。 /*掃描右子樹 */ } }while (top!=0)。 } 返回 小 結(jié) ?樹 ?二叉樹 滿二叉樹 完全二叉樹 ?樹的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 鏈接存儲結(jié)構(gòu) ?二叉樹的遍歷 中序遍歷 先序遍歷 后序遍歷 ?線索二叉樹 ?樹的應(yīng)用 二叉排序樹 哈夫曼樹 返回 習(xí)題與練習(xí) ?一、基礎(chǔ)知識題 1. 就如圖 ： 1）哪個是根結(jié)點？ 2）哪些是葉子結(jié)點？ 3）哪個是 E的父結(jié)點？ 4）哪些是 E的子孫結(jié)點？ 5）哪些是 E的兄弟結(jié)點？哪些是 C的兄弟結(jié)點？ 6）結(jié)點 B和結(jié)點 I的層數(shù)分別是多少？ 7）樹的深度是多少？ 8）以結(jié)點 G為根的子樹的深度是多少？ 9）樹的度是多少？ 圖 樹的例子 ○ J ○ B ○C ○ D ○ E ○ F ○ G ○ A ○ H ○ I 2. 分別畫出含 3個結(jié)點的樹與二叉樹的所有不同形態(tài)。 3. 高度為 h的完全二叉樹至少有多少個結(jié)點？最多有多少個結(jié)點？ 4. 采用順序存儲方法和鏈?zhǔn)酱鎯Ψ椒ǚ謩e畫出圖。 5. 分別寫出圖 、中序和后序遍歷序列。 圖 二叉樹例子 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 6. 若二叉樹中各結(jié)點值均不相同。 1)已知一個二叉樹的中序和后序遍歷序列分別為GDHBAECIF和 GHDBEIFCA，請畫出此二叉樹。 2)已知一個二叉樹的前序和中序分別為ABCDEFGH和 BDCEAFHG，請畫出此二叉樹。 7. 一個二叉樹如圖 ,分別寫出其前序、中序、后序的遍歷序列。 8. 輸入一個正整數(shù)序列{55,34,18,88,119,11,76,9,97,99,46}，試構(gòu)造一個二叉排序樹。 9. 有一份電文中共使用 5個字符： a、 b、 c、 d、 e，它們的出現(xiàn)頻率依次為 4。試畫出對應(yīng)的哈夫曼樹，并求出每個字符的哈夫曼編碼。 圖 一個二叉樹 ○ G ○ B ○C ○ D ○ E ○ F ○ A ?二、算法設(shè)計題 1. 一個二叉樹以鏈?zhǔn)浇Y(jié)構(gòu)存儲，分別給出求二叉樹結(jié)點總數(shù)和葉子結(jié)點總數(shù)的算法。 2. 一個二叉樹以鏈?zhǔn)浇Y(jié)構(gòu)存儲，寫出在二叉樹中查找值為 x的結(jié)點的算法。 3. 設(shè)計一個算法將一個以鏈?zhǔn)酱鎯Y(jié)構(gòu)的二叉樹，按順序方式存儲到一維數(shù)組中。 4. 假設(shè)二叉排序樹 t的各元素值均不相同，設(shè)計一個算法按遞增次序打印各元素值。 5. 已知一個中序線索二叉樹，試編寫中序遍歷的非遞歸算法。 返回