【正文】 二叉樹轉(zhuǎn)換成森林 ? 如果 B=(root,LB,RB)是一棵二叉樹 ,則可按如下規(guī)則轉(zhuǎn)換成森林 F={T1,T2, … ,Tm}： ? (1)若 B為空 ， 則 F為空； ? (2)若 B非空 ， 則 F中第一棵樹 T1的根 ROOT(T1)即為二叉樹 B的根 root； ? T1中的根結(jié)點(diǎn)的子樹森林 F1是由 B的左子樹LB轉(zhuǎn)換而成的森林 。 int n, r。 = 0。 //第 2個(gè)孩子 位置域 ...... int childd。 //雙親位置域 }PTNode。plchild=pre。 pre=Thrt。 第二節(jié) 線索二叉樹 中序遍歷二叉樹 T，并將其中序線索化 : (為了記下遍歷過程中訪問結(jié)點(diǎn)的先后次序，附設(shè)一個(gè)全程指針 pre) Status InOrderThreading(BiThrTree amp。 – 如結(jié)點(diǎn) “ *” 的后繼是 “ c” 。 else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW)。 后（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 A B C D G E F C F D B G E A 算法的遞歸描述 Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { if (T){ if (PostOrderTraverse(Tlchild,Visit)) if (PostOrderTraverse(Trchild,Visit)) if (Visit(Tdata)) return OK。 先（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 A B C D G E F A B C D F E G 算法的遞歸描述 Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { if (T){ if (Visit(Tdata)) if (PreOrderTraverse(Tlchild,Visit)) if (PreOrderTraverse(Trchild,Visit)) return OK。 struct BiTNode *lchild, *rchild。 完全二叉樹 ： 樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中 編號(hào)為 1 至 n 的結(jié)點(diǎn) 一一對(duì)應(yīng)。 p 所指結(jié)點(diǎn)原有左或右子樹成為 c 的右子樹。T, amp。 初始條件：二叉樹 T 存在， visit 是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 初始條件：二叉樹 T 存在， visit 是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 初始條件：二叉樹 T 存在， e 是 T 的結(jié)點(diǎn)。 初始條件：二叉樹 T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。 第一節(jié) 二叉樹的定義 ? Parent(T, e)。 初始條件：二叉樹 T 存在。 {銷毀結(jié)構(gòu) } DestroyBiTree(amp。如果左子樹 L 不空，則必存在一個(gè)根結(jié)點(diǎn) ，它是 root 的 左后繼(root, ∈ H)，如果右子樹 R 不空，則必存在一個(gè)根結(jié)點(diǎn) 為 root 的 右后繼 (root, ∈ H)。 } ADT Tree 第六章 樹和二叉樹 二叉樹 第一節(jié) 二叉樹的定義 ? 定義： 二叉樹 是另一種樹形結(jié)構(gòu)。p, i, c)。 初始條件：樹 T存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。 RightSibling(T, cur_e)。 初始條件：樹 T 存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：若 T 為空樹，則返回 TRUE，否則返回 FALSE。 初始條件： definition 給出樹 T的定義。反之，以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫 。 樹的度（ degree of tree）： 樹內(nèi)各結(jié)點(diǎn)的度的最大值。在一棵非空樹 T中： (2) 在 n0時(shí)，有且僅有一個(gè)特殊的數(shù)據(jù)元素稱為樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)只有后繼結(jié)點(diǎn)，沒有前驅(qū)結(jié)點(diǎn)。 A C G T2 D H I T3 J M B E L K T1 F 空樹 僅有根結(jié) 點(diǎn)的樹 第一節(jié) 樹的定義 下面列出一些樹結(jié)構(gòu)和非樹結(jié)構(gòu)的示意圖： 第一節(jié) 樹的定義 2. 樹的表示方法 1) 直觀表示法（ a） 樹的直觀表示法是以倒著的分支樹的形式表示。 無序樹： 樹中結(jié)點(diǎn)的子樹是無次序的。 第三節(jié) 樹的抽象數(shù)據(jù)類型 ? 基本操作 ： {結(jié)構(gòu)初始化 } InitTree(amp。T)。 操作結(jié)果：返回 T的 深度 。 初始條件：樹 T 存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。 TraverseTree(T, visit())。T)。 DeleteChild(amp。即：二叉樹是 n（ n≥ 0）個(gè)結(jié)點(diǎn)的有限集合。 操作結(jié)果：構(gòu)造 空 二叉樹 T。 操作結(jié)果：銷毀二叉樹 T。 初始條件：二叉樹 T 存在。 LeftChild(T, e)。 LeftSibling(T, e)。 PreOrderTraverse(T, visit())。 PostOrderTraverse(T, visit())。 ClearBiTree(amp。 操作結(jié)果：結(jié)點(diǎn) e 賦值為 value。 初始條件：二叉樹 T 存在， p 指向 T 中某個(gè)結(jié)點(diǎn)，LR 為 0 或 1。 （ 3） 在完全二叉樹中，若某個(gè)結(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。 struct TriTNode *lchild, *rchild。 }//PreOrderTraverse 第一節(jié) 遍歷二叉樹 A B C D E F G D L R T D L R D L R A B E D L R D L R DLR DLR C F D G 先序遍歷結(jié)果 : A B C D E F G T 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結(jié)點(diǎn)； （ 3）中序遍歷右子樹。 }//PostOrderTraverse 第一節(jié) 遍歷二叉樹 A B C D E F G H K 例如 : 先序 序列 : A B C D E F G H K 中序 序列 : B D C A H G K F E 后序 序列 : D C B H K G F E A 第一節(jié) 遍歷二叉樹 例： 已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹。 CreateBiTree(Trchild)。 第二節(jié) 線索二叉樹 例如 : 將下列二叉鏈表改為中序線索鏈表 Info A B C D E F G H I J K L M NLtagLchild 2 4 6 0 7 0 10 0 12 13 0 0 0 0RtagRchild 3 5 0 0 8 9 11 0 0 0 14 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 第二節(jié) 線索二叉樹 0 0 0 1 0 1 0 1 0 0 1 1 1 1 5 上例樹的形態(tài) Info Ltag Lchild Rtag RchildA 0 2 0 3B 0 4 0 5C 0 6 1 ThrtD 1 Thrt 1 2E 0 7 0 8F 1 1 0 9G 0 10 0 11H 1 5 1 1I 0 12 1 3J 0 13 1 7K 1 7 0 14L 1 6 1 9M 1 2 1 10N 1 11 1 5Thrt 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B D E F C H I G K J M N L 中序線索二叉樹 // 二叉樹的二叉線索存儲(chǔ)表示 typedef enum {Link,Thread} PointerTag。 ThrtLTag=Link。 preRTag=Thread。} //后繼線索 pre=p。 //根的位置和結(jié)點(diǎn)數(shù) }PTree。 int n。 } *ChildPtr。 struct CSNode *firstchild,*nextsibling。 第二節(jié) 森林與二叉樹的轉(zhuǎn)換 ? 樹的兩種遍歷方法： 一 、 先根遍歷： （ 1） 訪問樹的根結(jié)點(diǎn)； （ 2） 依次先根遍歷每棵子樹 。 ? (2) 在 F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹 ,且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左 、 右子樹根結(jié)點(diǎn)的權(quán)值之和 。 設(shè)字符集只含有 4個(gè)字符 A， B， C， D，用兩位二進(jìn)制表示的編碼分別為 00， 01， 10， 11。 第二節(jié) 赫夫曼編碼 ABACCDA 不等長編碼 利用赫夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的 赫夫曼編碼 是一種 最優(yōu)前綴編碼 ， 即使所傳 電文的總長度最短 。HT/*HF樹 */, int n /*n個(gè)字符 */ HuffmanCode amp。++i,++p) *p={0,0,0,0} //將葉子結(jié)點(diǎn)以外的結(jié)點(diǎn)初始化為 0 for(i=n+1； i=m； i++){ //建立 HF樹 SelectMin(HT， i1， s1， s2)； //選出權(quán)值最小的兩個(gè)結(jié)點(diǎn) s1,s2 HT[s1].parent=i。 else cd[start]=“1”。掌握各種遍歷策略的 遞歸算法 ， 靈活運(yùn)用遍歷算法 實(shí)現(xiàn)二叉樹的其它操作。 謝 謝！