【正文】 ef struct PTNode { TElemType data。 int parent。 // 雙親位置域 } PTNode。 data parent define MAX_TREE_SIZE 100 結(jié)點結(jié)構(gòu) : C語言的類型描述 : 120 typedef struct { PTNode nodes[MAX_TREE_SIZE]。 int r, n。 // 根結(jié)點的位置和結(jié)點個數(shù) } PTree。 樹結(jié)構(gòu) : r=0 n=7 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 121 A B C D E F G 二、孩子鏈表表示法 : 樹中每個結(jié)點可能包含多棵子樹， 所以可以采用 多叉鏈表 表示。 每個結(jié)點包含 多個指針域 每個指針指向一棵子樹的根結(jié)點 每個結(jié)點究竟應(yīng)設(shè) 多少個指針域 ？ 有以下幾種 設(shè)計方式 ： 122 Ⅰ. 若以樹的度 d來設(shè)置指針域的個數(shù)，顯然各個結(jié)點是 同構(gòu)的，便于各種操作。但由于樹中很多結(jié)點的度都小于 d，一棵度為 d且含有 n個結(jié)點的樹必有 ？ 個空指針域。 n*d(n1)=n*(d1)+1個，顯然造成很大的空間浪費。 Ⅱ. 若每個結(jié)點按其實際的孩子數(shù)來設(shè)置指針域的個數(shù)，并在結(jié)點內(nèi)設(shè)置度數(shù)域“ degree”指出結(jié)點所包含的指針的數(shù)目。顯然各結(jié)點是 不同構(gòu) 的。雖然節(jié)省了空間，但給運算帶來了不便。 123 Ⅲ. 以上兩種方法在實際應(yīng)用中都會遇到一些困難。較實用的方法是 為樹中每個結(jié)點建立一個孩子鏈表 ，而 n個頭指針又組成一個線性表，為了便于查找，可采用順序存儲結(jié)構(gòu)。 A B C D E F G 124 1 0 0 0 2 2 4 data firstchild 0 A 1 B 2 C 3 D 4 E 5 F 6 G 6 4 5 1 2 3 parent 與雙親表示法相反，孩子表示法便于實現(xiàn)涉及孩子的操作，卻不太適合涉及雙親的操作。 Ⅳ. 為了方便各種操作，可以把雙親表示法和孩子表示法結(jié)合起來，即 帶雙親的孩子鏈表 。 A B C D E F G 125 typedef struct CTNode { int child。 struct CTNode *nextchild。 } *ChildPtr。 孩子結(jié)點結(jié)構(gòu) : child nextchild 孩子鏈表 C語言的類型描述 : typedef struct { TElemType data。 ChildPtr firstchild。 // 孩子鏈的頭指針 } CTBox。 雙親結(jié)點結(jié)構(gòu) : data firstchild 126 typedef struct { CTBox nodes[MAX_TREE_SIZE]。 int n, r。 // 結(jié)點數(shù)和根結(jié)點的位置 } CTree。 樹結(jié)構(gòu) : 127 typedef struct CSNode{ TElemType data。 struct CSNode *firstchild, *nextsibling。 } CSNode, *CSTree。 結(jié)點結(jié)構(gòu) : firstchild data nextsibling 三、孩子 兄弟表示法 (二叉鏈表存儲） 128 A B C D E F G root A B C E D F G 如何找結(jié)點 *x的第 i個孩子？ x 129 A B C D E F H G I 分別用雙親表示法、孩子鏈表、孩子 —兄弟表示法表示圖示樹。 練習： A B C E D F G I H 孩子 兄弟表示法 130 樹、森林和二叉樹的對應(yīng)關(guān)系 (一 ) 樹與二叉樹之間的轉(zhuǎn)換 二叉樹和樹都可以用二叉鏈表作為存儲結(jié)構(gòu)。即一棵二叉樹或樹可 唯一 的對應(yīng)一個二叉鏈表。這樣就可以得到二叉樹與樹之間的對應(yīng)關(guān)系。從物理結(jié)構(gòu)來看，存儲它們的二叉鏈表是相同的，只是解釋不同。 131 A B C D E F G A B C E D F G root A B C E D F G root A B C D E F G root A B C D E F G 樹 二叉樹 孩子兄弟表示法 二叉鏈表表 示法 內(nèi)存中的表示 132 樹轉(zhuǎn)換成二叉樹的規(guī)則 要把一棵樹轉(zhuǎn)換為二叉樹，只要： 兄弟 之間加一條連線； ，除 保留 其與第一個孩子之間的 連線外， 去掉 該結(jié)點與其它孩子的連線； ，把右孩子順時針 旋轉(zhuǎn) 45度。 133 A J H D G F C I E B A J H D G F C I E B A J H D G F C I E B A H D G F C I E B J 如： ? 從轉(zhuǎn)換過程可以看出： 樹轉(zhuǎn)換為二叉樹后，二叉樹根結(jié)點的右子樹必為空。 (因為樹根沒有兄弟 ) 134 (二 ) 森林與二叉樹之間的轉(zhuǎn)換 在把森林轉(zhuǎn)換為二叉樹時，可以把森林中除第一棵樹以外的其它所有樹的根結(jié)點看作第一棵樹根結(jié)點的 兄弟 結(jié)點。或者，可以先將森林中的每一棵樹變?yōu)槎鏄洌缓髮⒏鞫鏄涞母Y(jié)點視為兄弟連在一起。 森林轉(zhuǎn)換成二叉樹的規(guī)則 135 H D G F C I E B J 如： J H D G F C I E B J H D G F I E B C 136 H D G F C I E B J 以上我們給出了：樹和森林轉(zhuǎn)化為二叉樹的規(guī)則， 那么二叉樹如何轉(zhuǎn)化為樹或森林？看下面例子： 二叉樹轉(zhuǎn)換成樹或森林的規(guī)則 若結(jié)點 x是其雙親 p的左孩子，則把 x的右孩子、右孩子的右孩子、 …… 都與 p用線連起來。然后去掉所有雙親到右孩子的連線。最后作適當?shù)恼{(diào)整即可。 H D G F C I E B J H D G C E B F J I 137 由此，樹和森林的各種操作均可與二叉樹的操作相對應(yīng)。 應(yīng)當注意的是， 和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋? 左是孩子，右是兄弟。 138 一、樹的遍歷 二、森林的遍歷 三、樹的遍歷的應(yīng)用 樹和森林的遍歷 139 樹的遍歷 可有三條搜索路徑 : 按層次遍歷 : 先根 (次序 )遍歷 : 后根 (次序 )遍歷 : 若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。 若樹不空，則自上而下、自左至右訪問樹中每個結(jié)點。 140 層次遍歷時頂點的訪問序列： A B C D E F G H I J K 先根遍歷時頂點的訪問序列： A B E F C D G H I J K 后根遍歷時頂點的訪問序列： E F B C I J K H G D A A B C D E F G H I J K 141 若森林不空，則 訪問 森林中第一棵樹的根結(jié)點 。 先序遍歷 森林中第一棵樹的子樹森林 。 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 先序遍歷： 森林的遍歷 即： 依次從左至右 對森林中的每一棵 樹 進行 先根遍歷 。 142 若森林不空，則 中序遍歷 森林中第一棵樹的子樹森林 。 訪問 森林中第一棵樹的根結(jié)點 。 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 中序遍歷： 即： 依次從左至右 對森林中的每一棵 樹 進行 后根遍歷 。 143 樹、森林的遍歷和二叉樹遍歷的對應(yīng)關(guān)系 ？ 先根遍歷 后根遍歷 樹 二叉樹 森林 先序遍歷 先序遍歷 中序遍歷 中序遍歷 144 A B C D E F G H I J K L M N O 先序遍歷： 后序遍歷： 層次遍歷： A B E F I G C D H J K L N O M E I F G B C J K N O L M H D A A B C D E F G H I J K L M N O 寫出下面樹的先根、后根及按層次遍歷的遍歷序列。 單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級 145 哈 夫 曼 樹 與 哈 夫 曼 編 碼 ?引例 — 問題的提出 ?哈夫曼樹系統(tǒng)理論 ?問題的解決 哈 夫 曼 樹 David Huffman 按此程序流程，有 80%的數(shù)據(jù)需進行 3次或 3次以上比較才能得出結(jié)果。 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A 等級 分數(shù)段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 5% 15% 40% 30% 10% 設(shè)實際學生成績的分布規(guī)律如下： (設(shè)成績?yōu)? a) 引例 ： 百分制成績轉(zhuǎn)換成五級分制成績 等級分數(shù)段比例ABCDE0~ 59 60~ 69 70~ 79 80~ 89 90~ 1000. 05 0. 15 0. 40 0. 30 0. 10等級分數(shù)段比例如何設(shè)計程序才能使得 比較的總次數(shù) 最少 ？ 問題： 程序執(zhí)行的時間 ,與什么因素有關(guān)？ CPU的處理速度 (硬件因素 )； 程序中執(zhí)行基本運算的次數(shù) ,即比較的次數(shù) (軟件因素 )。 樹的帶權(quán)路徑長度 : 樹中所有的葉結(jié)點的權(quán)值乘上其到根 結(jié)點的路徑長度之和，記為： 一、哈夫曼樹的定義 根 6 哈夫曼樹統(tǒng)稱一類帶權(quán)路徑長度最短的樹。 WPL = ? wklk (n個葉子結(jié)點 ) k=1 n 假設(shè)有 n個權(quán)值 {w1, w2, …, w n}， 構(gòu)造一棵有 n 個葉子結(jié)點的二叉樹，每個葉子結(jié)點所帶權(quán)值為 wi ，則其中 WPL最小 的二叉樹稱為 最優(yōu)二叉樹或 哈夫曼樹 。 哈 夫 曼