【正文】 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)二叉樹或 哈夫曼樹 。 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è)實際學(xué)生成績的分布規(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ù) (軟件因素 )。 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 寫出下面樹的先根、后根及按層次遍歷的遍歷序列。 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 142 若森林不空，則 中序遍歷 森林中第一棵樹的子樹森林 。 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 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é)點 。 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。 應(yīng)當注意的是， 和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋? 左是孩子，右是兄弟。最后作適當?shù)恼{(diào)整即可。 森林轉(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用線連起來。 (因為樹根沒有兄弟 ) 134 (二 ) 森林與二叉樹之間的轉(zhuǎn)換 在把森林轉(zhuǎn)換為二叉樹時，可以把森林中除第一棵樹以外的其它所有樹的根結(jié)點看作第一棵樹根結(jié)點的 兄弟 結(jié)點。 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度。這樣就可以得到二叉樹與樹之間的對應(yīng)關(guān)系。 練習(xí)： A B C E D F G I H 孩子 兄弟表示法 130 樹、森林和二叉樹的對應(yīng)關(guān)系 (一 ) 樹與二叉樹之間的轉(zhuǎn)換 二叉樹和樹都可以用二叉鏈表作為存儲結(jié)構(gòu)。 } CSNode, *CSTree。 樹結(jié)構(gòu) : 127 typedef struct CSNode{ TElemType data。 int n, r。 // 孩子鏈的頭指針 } CTBox。 孩子結(jié)點結(jié)構(gòu) : child nextchild 孩子鏈表 C語言的類型描述 : typedef struct { TElemType data。 struct CTNode *nextchild。 Ⅳ. 為了方便各種操作，可以把雙親表示法和孩子表示法結(jié)合起來，即 帶雙親的孩子鏈表 。較實用的方法是 為樹中每個結(jié)點建立一個孩子鏈表 ，而 n個頭指針又組成一個線性表，為了便于查找，可采用順序存儲結(jié)構(gòu)。雖然節(jié)省了空間，但給運算帶來了不便。 Ⅱ. 若每個結(jié)點按其實際的孩子數(shù)來設(shè)置指針域的個數(shù)，并在結(jié)點內(nèi)設(shè)置度數(shù)域“ degree”指出結(jié)點所包含的指針的數(shù)目。但由于樹中很多結(jié)點的度都小于 d，一棵度為 d且含有 n個結(jié)點的樹必有 ？ 個空指針域。 樹結(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é)點可能包含多棵子樹， 所以可以采用 多叉鏈表 表示。 int r, n。 // 雙親位置域 } PTNode。 119 typedef struct PTNode { TElemType data。 116 樹和森林 117 樹的三種存儲結(jié)構(gòu) 一、 雙親表示法 （順序存儲） 二、 孩子鏈表表示法 三、 孩子 兄弟表示法 (二叉鏈表存儲） 118 A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data parent 一、雙親表示法 : (順序存儲結(jié)構(gòu) ) 利用每個結(jié)點至多有一個雙親的性質(zhì)。 // 右子樹線索化 } // if } // InThreading 108 0 A 0 ? 0 B 0 0 C 0 ? ? 0 D 0 ? ? 0 E 0 ? root pre == NULL current 109 0 A 0 ? 1 B 0 0 C 0 ? ? 0 D 0 ? ? 0 E 0 ? root pre == NULL current 110 0 A 0 ? 1 B 0 0 C 0 ? 1 D 0 ? ? 0 E 0 ? root pre current 111 0 A 0 ? 1 B 0 0 C 0 ? 1 D 1 ? 0 E 0 ? root pre current 112 0 A 0 ? 1 B 0 0 C 0 ? 1 D 1 1 E 0 ? root pre current 113 0 A 0 ? 1 B 0 0 C 0 ? 1 D 1 1 E 1 root pre current 114 0 A 0 ? 1 B 0 0 C 1 ? 1 D 1 1 E 1 root pre 后處理 115 線索樹的優(yōu)缺點： 優(yōu)點： 線索樹由于含有其前驅(qū)、后繼的 信息，因此在進行各種操作時顯 得比較方便。 } pre = p。 } if (!prerchild) // 建后繼線索 { preRTag = Thread。 // 左子樹線索化 if (!plchild) // 建前驅(qū)線索 { pLTag = Thread。把中序遞歸遍歷算法中的Visit(pdata)改為 設(shè)置線索 的語句。 // p進至其右子樹根 } } // InOrderTraverse_Thr c d e f + / a b nil nil 中序遍歷序列： a+b*cde/f 106 在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當前訪問結(jié)點的“ 前驅(qū) ”和“ 后繼 ”信息。 Visit(pdata)。amp。 //最左下的結(jié)點是中序遍歷的 Visit(pdata)。 最左下結(jié)點時，繼續(xù)查找 } //else } 105 有右子樹 無右子樹 對新子樹 void InOrderTraverse_Thr(BiThrTree T, //中序遍歷帶頭結(jié)點二叉線索樹 T的非遞歸算法 void (*Visit)(TElemType e)) { //T指向頭結(jié)點，頭結(jié)點的左鏈 lchild指向根結(jié)點 p = Tlchild。 //從 *p的右孩子開始查找 while (!qltag) q=qlchild。 103 rtag rightChild = = 0（右子女指針） = = 1（后繼線索） = = NULL 無此情況 無后繼 != NULL 后繼為當前結(jié)點右子樹的中序下的第一個結(jié)點 后繼為右子女結(jié)點 尋找當前結(jié)點在中序序列下的后繼 尋找當前結(jié)點在中序序列下的前驅(qū) ltag LeftChild == 0（左子女指針） == 1（前驅(qū)線索） = = NULL 無此情況 無前驅(qū) != NULL 前驅(qū)為當前結(jié)點左子樹中序下的最后一個結(jié)點 前驅(qū)為左子女結(jié)點 104 寫出中序線索二叉樹中找指針 p所指結(jié)點后繼的算法。 p = Next(p) ) Visit (p)。 // Link==0:指針， Thread==1:線索 102 二、線索鏈表的遍歷算法 : for ( p = firstNod