【正文】 。 6. 學(xué)會編寫實(shí)現(xiàn)樹的各種操作的算法 。 5. 熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn) ， 掌握樹和森林與二叉樹的轉(zhuǎn)換方法 。 本章小結(jié) 4. 理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系 ， 熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法 。 掌握各種遍歷策略的遞歸算法 ， 靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作 。 3. 遍歷二叉樹是二叉樹各種操作的基礎(chǔ) 。 三 . 前綴編碼 1. 熟練掌握二叉樹的結(jié)構(gòu)特性 ， 了解相應(yīng)的證明方法 。 (3) (4) 9 例如 : 已知權(quán)值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 10 110 111 指的是，任何一個字符的編碼都 不是同一字符集中另一個字符的編碼 的前綴。 (2) 從 F中刪去這兩棵樹，同時加入 剛生成的新樹 。 例如： 2 7 9 7 5 4 9 2 WPL(T) = 7?2+5?2+2?3+4?3+9?2 = 60 WPL(T) = 7?4+9?4+5?3+4?2+2?1 = 89 5 4 根據(jù)給定的 n 個權(quán)值 {w1, w2, …, w n}， 構(gòu)造 n 棵二叉樹的集合 F = {T1, T2, … , T n}， 其中每棵二叉樹中均只含一個帶權(quán)值 為 wi 的根結(jié)點(diǎn) ,其左、右子樹為空樹 。 結(jié)點(diǎn)的路徑長度 定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上 分支的數(shù)目。 r = p。 r = p。 GetHead(Q,s)。 // 所建為根結(jié)點(diǎn) else { } // 非根結(jié)點(diǎn)的情況 } // for } // CreateTree … … GetHead(Q,s)。 // 創(chuàng)建結(jié)點(diǎn) EnQueue(Q, p)。fa, amp。 ch!=? ?。fa, amp。T ) { T = NULL。 假設(shè)以二元組 (F,C)的形式自上而下 、自左而右依次輸入樹的各邊 ， 建立樹的孩子 兄弟鏈表 。 T = Tnextsibling。 else OutPath( Tfirstchild, s )。 S ) { while ( T ) { Push(S, Tdata )。 } Pop(S)。 else { AllPath( Tlchild, S )。amp。 S ) { if (T) { Push( S, Tdata )。 } } // TreeDepth return(max(h1+1, h2))。 else { h1 = TreeDepth( Tfirstchild )。 } CSNode, *CSTree。 先根遍歷 后根遍歷 樹 二叉樹 森林 先序遍歷 先序遍歷 中序遍歷 中序遍歷 樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系 ？ 設(shè)樹的存儲結(jié)構(gòu)為孩子兄弟鏈表 typedef struct CSNode{ Elem data。 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 森林的遍歷 中序遍歷 若森林不空，則 中序遍歷 森林中第一棵樹的子樹森林 。 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 森林由三部分構(gòu)成： 1. 先序遍歷 若森林不空，則 訪問森林中第一棵樹的根結(jié)點(diǎn) 。 若樹不空，則自上而下自左至右訪問樹中每個結(jié)點(diǎn)。 應(yīng)當(dāng)注意的是， 和樹對應(yīng)的二叉樹，其左、右子樹的概念 已改變?yōu)椋?左是孩子，右是兄弟 樹和森林的遍歷 一 . 樹的遍歷 二 . 森林的遍歷 三 . 樹的遍歷的應(yīng)用 樹的遍歷可有三條搜索路徑 : 按層次遍歷 : 先根 (次序 )遍歷 : 后根 (次序 )遍歷 : 若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。 由 RBT 對應(yīng)得到 (T2, T3, …, T n)。 否則， 由 Node(root) 對應(yīng)得到 ROOT( T1 )。 由 (T2, T3,…, T n ) 對應(yīng)得到 RBT。 否則， 由 ROOT( T1 ) 對應(yīng)得到 Node(root)。 二叉樹 B =( LBT, Node(root), RBT )。 C語言的類型描述 : 結(jié)點(diǎn)結(jié)構(gòu) : firstchild data nextsibling 設(shè) 森林 F = ( T1, T2, …, T n )。 struct CSNode *firstchild, *nextsibling。 // 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 } CTree。 雙親結(jié)點(diǎn)結(jié)構(gòu) data firstchild typedef struct { CTBox nodes[MAX_TREE_SIZE]。 ChildPtr firstchild。 } *ChildPtr。 樹結(jié)構(gòu) : 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 r=0 n=7 data firstchild 1 2 3 4 5 6 4 二 . 孩子鏈表表示法 typedef struct CTNode { int child。 int r, n。 // 雙親位置域 } PTNode。 } 樹和森林的 表示方法 一 . 雙親表示法 二 . 孩子鏈表表示法 三 . 樹的二叉鏈表 (孩子 兄弟） 存儲表示法 樹的三種存儲結(jié)構(gòu) 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 r=0 n=7 data parent 一 . 雙親表示法 typedef struct PTNode { Elem data。 //處理最后一個結(jié)點(diǎn) preRTag = Thread。 InThreading(T)。 else { Thrtlchild = T。 // 添加頭結(jié)點(diǎn) return OK。 ThrtRTag=Thread。Thrt, BiThrTree T) { // 構(gòu)建中序線索鏈表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode)))) exit (OVERFLOW)。 // 保持 pre 指向 p 的前驅(qū) InThreading(prchild)。 prerchild = p。 plchild = pre。 三 . 如何建立線索鏈表？ void InThreading(BiThrTree p) { if (p) { // 對以 p為根的非空二叉樹進(jìn)行線索化 InThreading(plchild)。 // p進(jìn)至其右子樹根 } } 在中序遍歷過程中修改結(jié)點(diǎn)的 左 、 右指針域 ， 以保存當(dāng)前訪問結(jié) 點(diǎn)的 “ 前驅(qū) ” 和 “ 后繼 ” 信息 。 Visit(pdata)。amp。 //第 一個結(jié)點(diǎn) Visit(pdata)。 二 . 線索鏈表的遍歷算法 例如 : 對中序線索化鏈表的遍歷算法 ※ 中序遍歷的第一個結(jié)點(diǎn)？ ※ 在中序線索化鏈表中結(jié)點(diǎn)的后繼？ 左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn) 若 無右子樹， 則為 后繼線索所指結(jié)點(diǎn) 否則為 對其右子樹進(jìn)行中序遍歷時訪問的第一個結(jié)點(diǎn) void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { p = Tlchild。 p=Succ(p) ) Visit (p)。 // Link==0:指針， Thread==1:線索 for ( p=firstNode(T)。 // 左右標(biāo)志 } BiThrNode, *BiThrTree。 struct BiThrNode *lchild,*rchild。 若該結(jié)點(diǎn)的右子樹不空， 則 rchild域的指針指向其右子樹， 且右標(biāo)