【正文】 ； //編碼結(jié)束符。 2. 從 F中選兩個(gè)權(quán)值最小的二叉樹 Ti和 Tj， 構(gòu)造一個(gè) 根結(jié)點(diǎn) R, R的權(quán) wR為 wi + wj 。 二、 樹與森林的遍歷 例 先根遍歷樹 A B C D E F H I J G 先根遍歷序列 : A B E C F D G H I J 二、 樹與森林的遍歷 （ 2）后根遍歷 : 若樹非空，則 ? 從左到右后根次序遍歷根的每棵子樹 。 else p=r。 while (prtag amp。 !prerchild) { prerchild=p。 為了區(qū)分線索與真實(shí)指針，給結(jié)點(diǎn)增加兩個(gè)域 Ltag和 Rtag lchild Ltag data Rtag rchild Ltag=0: lchild 指向結(jié)點(diǎn)的左子女； Ltag=1: lchild 指向 某一遍歷序列 前驅(qū)； Rtag=0: rchild 指向結(jié)點(diǎn)的右子女； Rtag=1: rchild 指向 某一遍歷序列 后繼 ； 二、線索二叉樹 (Threaded Binary Tree) Typedef enum{Link,Thread} PointerTag。A 訪問： C B E G D p (11) 例 A B C D E F G i amp。C (3) 例 p=NULL A B C D E F G i amp。 amp。 ／／ 構(gòu)造左子樹 CreateBiTree(BTrchild)。 一、遍歷 “ 訪問 ”的含義特別很廣，如：輸出結(jié)點(diǎn)的信息等。 操作結(jié)果：后序遍歷 T中每個(gè)結(jié)點(diǎn)一次且僅一次 。 基本操作 : LeftSibling(T， e)； 初始條件：二叉樹 T存在， e是 T中某個(gè)結(jié)點(diǎn)。 BiTreeEmpty(T)； 初始條件：二叉樹 T存在 。 二叉樹的 5種基本形態(tài)： 1 空 2 只有根 3 右子樹空 4 左子樹空 5 左、右子樹非空 具有 3個(gè)結(jié)點(diǎn)的 二叉樹 可能有幾種不同形態(tài)？ 抽象數(shù)據(jù)類型二叉樹的定義： ADT BinaryTree{ 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合 。 RightSibling(T， cur_e)； 初始條件：樹 T存在 ， cur_e是 T中某個(gè)結(jié)點(diǎn) 。T) 初始條件；樹 T存在 。 祖先、后代（ ancestor） :一個(gè)結(jié)點(diǎn)是它所有子樹中的結(jié)點(diǎn) 的祖先，這些結(jié)點(diǎn)是它的后代 (子孫 )。 操作結(jié)果；返回 T的深度 。 操作結(jié)果：插入 c為 T中 p所指結(jié)點(diǎn)的第 i棵子樹 。 DestroyBiTree(amp。 Value(T， e) 初始條件：二叉樹 T存在 ， e是 T中某個(gè)結(jié)點(diǎn) 。若 e是 T的右孩子或無右兄弟， 則返回 “ 空 ” 。若它是雙親 的右子女 ,則它的編號是雙親編號的 2倍 +1. 二叉樹的性質(zhì) A B C D E F H 1 2 3 4 5 6 7 編號的滿二叉樹 完全二叉樹 (Complete Binary Tree): 深度為 k的滿二叉樹 , 刪去第 k層上最右邊的 j(0 j2k1)個(gè)結(jié)點(diǎn) ,就得到一個(gè)深度為 k 的完全二叉樹 . 編號的完全二叉樹 : 與滿二叉樹編號相同 ? 二叉樹的性質(zhì) 1 A B C E 2 3 4 A B C D E 1 2 3 4 5 A B C E F H 1 2 3 4 5 6 F 7 性質(zhì) 4: 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹 ,其深度為 。 PreOrderTraverse(BTlchild)。 amp。 push(S,p)。D 訪問： C B p (6) 例 A B C D E F G i amp。 //指向根 while (p || !StackEmpty(S)) { if (p) { push((p, L))； // p帶 L入 棧 p=plchild。 lchild Ltag data Rtag rchild 二、線索二叉樹 (Threaded Binary Tree) 加了線索的二叉樹是 線索二叉樹 ； 給二叉樹加線索的過程是 線索化（穿線） ； 按前序遍歷序列穿線的二叉樹是 前序線索二叉樹 ； 按中序遍歷序列穿線的二叉樹是 中序線索二叉樹 ； 按后序遍歷序列穿線的二叉樹是 后序線索二叉樹 ； 中序線索 二叉樹簡稱 線索二叉樹 ； 二、線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 先序序列： ABCDE 先序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 二、 線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 中序序列： BCAED 中序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 ^ 二、 線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 后序序列： CBEDA 后序線索二叉樹 0 0 0 0 1 1 1 1 1 1 ^ 二、 線索二叉樹 (Threaded Binary Tree) D B F E A C NULL NULL 中序線索二叉樹 二、線索二叉樹 (Threaded Binary Tree) Void lnorderTraverse(BiTree BT) { ／／ 采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹 T的非遞歸算法 . InitStack(S)； p=BT； while(p||!StackEmpty(S)) { if(p) { push(S， p)； p=plchild； }//根指針進(jìn)棧，遍歷左子樹 else { ／／ 根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹 pop(S， p)； visit(p)。 2) 找出給定結(jié)點(diǎn) p在某一次序中的后繼結(jié)點(diǎn) 。 } } // inOrderTraverse 中序遍歷線索二叉樹的算法 同理，我們可以前序非遞歸遍歷中序線索二叉樹， 同樣不需要遞歸（使用了系統(tǒng)棧）也不需要棧 . 關(guān)鍵問題 1 根就是第一個(gè)結(jié)點(diǎn) . 關(guān)鍵問題 2，有如下 3種情況： ?P有左子女：則 p左子女是 p的后繼；否則 ?P有右子女：則 p的右子女是 p的后繼 。 typedef struct { PTNode nodes[MAXTREESIZE]。 ?先序遍歷第一棵樹中的根 結(jié)點(diǎn)的子樹森林； ?先序遍歷其余的樹所構(gòu)成 的森林； A B C D E F G H I J 中序遍歷序列： BCDAFEHJIG 中序遍歷森林 二、 樹與森林的遍歷 中序遍歷 : ?中序遍歷第一棵樹的子樹； ?訪問第一棵樹的根 。HT， HuffmanCode amp。 ?理解最優(yōu)樹的特性，掌握建立最優(yōu)樹和 Huffman編 碼的方法 。 i=m； ++i， ++p) *p={0， 0， 0， 0}； //后 n1個(gè)結(jié)點(diǎn) for(i=n+1； i=m； ++i){ //建哈夫曼樹 //在 HT[1..i1]選擇 parent為 0且 weight最小的兩個(gè)結(jié)點(diǎn)，其序號分別為 s1和 s2。 樹的路徑長度 ：樹中每個(gè)結(jié)點(diǎn)的路徑長度之和。表頭數(shù)組中每一項(xiàng)稱孩子鏈表頭指針 CTBox: (頭結(jié)點(diǎn) ) 單鏈表中每一項(xiàng)稱孩子結(jié)點(diǎn) (也稱表結(jié)點(diǎn) )： CTNode: 一、 樹的存儲結(jié)構(gòu) data firstchild child next typedef struct CTNode { //孩子結(jié)點(diǎn)（ 表結(jié)點(diǎn)） int child； struct CTNode *next； } *ChildPtr； tyPedef struct { //頭結(jié)點(diǎn) TElemType data； ChildPtr firstchild。 // P有右子女 else{ r=prchild。 // P無右子女 else { p=prchild。 } // p指向左子女 else { pop(S,p)。} //訪問 p else { push((p, R))。A amp。A (1) 例 A B C D E F G p i amp。 amp。 3. 建立左子樹和右子樹。 }BiTNode, *BiTree。 PreOrderTraverse(T)； 初始條件：二叉樹 T存在。 操作結(jié)果：若 e是 T的非根結(jié)點(diǎn) ， 則返回它的雙親 ， 否則返回 “ 空 ”。 初始條件： definition給出二叉樹 T的定義 。 }ADT Tree 基本操作 : ? 樹的表示方法： 1. 樹形表示： 樹（ Tree） 的定義和基本術(shù)語 A B C D E F H I J G 2. 括號表示 (廣義表表示 )： (A(B(E))(C(F))(D(G(H)(I)(J)))) T1 T3 T2 樹根 3. 凹入表表示 (目錄表示法 )： A B C D E F H I J G A B E C F D G H I J 樹（ Tree） 的定義和基本術(shù)語 4. 文氏圖表示 (集合表示 ): A B C D E F H I J G A B E C F D G H I J 樹（ Tree） 的定義和基本術(shù)語 二叉樹是另一種樹形結(jié)構(gòu)。 操作結(jié)果：結(jié)點(diǎn) cur_e 賦值為 value。 操作結(jié)果 ， 銷毀樹 T。T) 初始條件：樹 T存在 。 Assign(T， cur_e， value) 初始條件：樹 T存在 ， cur_e是 T中某個(gè)結(jié)點(diǎn) 。 操作結(jié)果：按某種次序?qū)?T的每個(gè)結(jié)點(diǎn)進(jìn)行遍歷 。T,definition)。 Parent(T， e)； 初始條件：二叉樹 T存在 ， e是 T中某個(gè)結(jié)點(diǎn) 。 操作結(jié)果：根據(jù) LR為 0或 1，刪除 T中 p所指結(jié)點(diǎn)的左或右子樹。 struct BiTNode *lchild,* rchild。 2. 建立根。 A B C E F H G D I 后序遍歷 LRN amp。 p=prchild； }//else }／／ InOrderTraverse 非遞歸中序遍歷 BT的算法 : A B C D E F G p i amp。D 訪問： C B E p (8) 例 A B C D E F G i amp。 p=NULL。 // p入棧 p=plchild。 if () p=prchild。 // P有左子女 else if (!prtag) p=pr