【正文】 。 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 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)二叉樹或 哈夫曼樹 。 142 若森林不空，則 中序遍歷 森林中第一棵樹的子樹森林 。 應(yīng)當(dāng)注意的是， 和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yō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度。 樹結(jié)構(gòu) : 127 typedef struct CSNode{ TElemType data。 struct CTNode *nextchild。 Ⅱ. 若每個結(jié)點按其實際的孩子數(shù)來設(shè)置指針域的個數(shù)，并在結(jié)點內(nèi)設(shè)置度數(shù)域“ degree”指出結(jié)點所包含的指針的數(shù)目。 // 雙親位置域 } PTNode。 } pre = p。 // p進(jìn)至其右子樹根 } } // InOrderTraverse_Thr c d e f + / a b nil nil 中序遍歷序列： a+b*cde/f 106 在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當(dāng)前訪問結(jié)點的“ 前驅(qū) ”和“ 后繼 ”信息。 最左下結(jié)點時，繼續(xù)查找 } //else } 105 有右子樹 無右子樹 對新子樹 void InOrderTraverse_Thr(BiThrTree T, //中序遍歷帶頭結(jié)點二叉線索樹 T的非遞歸算法 void (*Visit)(TElemType e)) { //T指向頭結(jié)點，頭結(jié)點的左鏈 lchild指向根結(jié)點 p = Tlchild。 // Link==0:指針， Thread==1:線索 102 二、線索鏈表的遍歷算法 : for ( p = firstNode(T)。 與其相應(yīng)的二叉樹，稱作 “ 線索二叉樹 ” 包含 “線索” 的存儲結(jié)構(gòu)，稱作 “ 線索鏈表 ” A B C D E F G H K （先序序列） ^ D ^ C ^ ^ B E ^ A B C D E F G H K 99 對 線索鏈表 中結(jié)點的約定： 在二叉鏈表的結(jié)點中 增加兩個標(biāo)志域 ， 并作如下規(guī)定： 若該結(jié)點的左子樹不空 ， 則 Lchild域的指針指向其左子樹， 且左標(biāo)志域的值為 “ 指針 Link‖(0) ； 否則 ， Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志域的值為 “ 線索 Thread‖(1) 。 Pop(PND, rc)。 //棧頂元素 c優(yōu)先級 高于 當(dāng)前運算符 ch 92 建葉子結(jié)點的算法為： void CrtNode(BiTreeamp。 while (c!= ?(? ) { CrtSubtree( t, c)。amp。 否則建子樹 。 遞歸建左子樹 。 Tdata = ch。 } return depth。 CountLeaf( Trchild, count)。 }//else }//if else return FALSE。 p=plchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點， Pop(S,p)。 p=prchild。 p=plchild。 p=T。 T D printf(D)。 pre(tlchild)。// 遍歷右子樹 } } 62 例 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲 ,試設(shè)計一個算法 ,輸出一棵給定二叉樹的所有葉子結(jié)點 。而二叉樹是非 線性結(jié)構(gòu)， 每個結(jié)點有兩個后繼 ， 則存在 如何遍歷 即按什么樣的 搜索 路徑 遍歷的問題。 C 語言的類型描述如下 : 1. 二叉鏈表 lchild data rchild 結(jié)點結(jié)構(gòu) : 45 A D E B C F ? ? ? ? ? ? ? root A B D C F E 在有 n個結(jié)點的二叉鏈表中，有 ？ 個空指針域 n+1 46 typedef struct TriTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 39 二叉樹的存儲結(jié)構(gòu) 二、 二叉樹的鏈?zhǔn)酱鎯Ρ硎? 一、 二叉樹的順序存儲表示 40 二叉樹的順序存儲結(jié)構(gòu)中結(jié)點的存放次序是：對該樹中每個結(jié)點進(jìn)行編號 ,其編號從小到大的順序就是結(jié)點存放在連續(xù)存儲單元的先后次序。 DeleteChild(T, p, LR)。 CreateBiTree(amp。 PreOrderTraverse(T, Visit()) // 先序遍歷 。 Value(T, e)。 A root B E F K L C G D H I J M F 19 子樹之間不存在確定的次序關(guān)系 （ 能互換 ） 。 樹中葉子結(jié)點所在的最大層次。T, amp。 (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root, (2) 當(dāng) n1時，其余結(jié)點可分為 m (m0)個互 不相交的有限集 T1, T2, …, T m, 其中每一 個子集本身又是一棵樹 ,稱為根 root的子樹。 ?5 A 只有根結(jié)點的 樹 A B C D E F G H I J K L M 有子樹的 樹 根 子 樹 6 A B C D E F G H I J M K L A( ) T1 T3 T2 樹根 B(E, F(K, L)), C(G), D(H, I, J(M)) 7 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合。T) // 銷毀樹結(jié)構(gòu) DeleteChild(amp。 A B C D E F G H I J M K L 定義根結(jié)點的層次為 1,第 t層結(jié)點子樹的根結(jié)點的層次為 t+1。 森林： 是 m（ m≥ 0）棵互 不相交的樹的集合。 否 26 練習(xí)：具有 3個結(jié)點的二叉樹有多少種？ 27 二叉樹的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 ADT BinaryTree： P121 28 Root(T)。 BiTreeDepth(T)。e, value)。T)。 (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其 左孩子 結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的結(jié)點為其 右孩子 結(jié)點 。 // 左右孩子指針 } BiTNode, *BiTree。 52 “遍歷 ”是任何類型均有的操作， 對線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因為每個結(jié)點均只有一個后繼 )， 故不需要另加討論。 // 遍歷左子樹 PreOrder(Trchild, Visit)。 } } } 64 void pre(BiTree t) { if (t!=NULL) { printf (%d\t,tdata)。 pre(T L)。 e)) { InitStack(S)。 }// InOrderTraverse 四、中序遍歷算法的非遞歸描述 67 非遞歸算法的執(zhí)行過程 A B C D E F G p i A (1) A B C D E F G p i A B (2) A B C D E F G p i A B C (3) p=NULL pC p=NULL A B C D E F G i A B 訪問： C (4) while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點 if (p) { Push(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=plchild。 // 訪問根結(jié)點 Push(S,p)。 else return(Preorder_Seek (Trchild, x, p)) 。 // 對葉子結(jié)點計數(shù) CountLeaf( Tlchild, count)。 depth = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。 else { 建根結(jié)點 。 若當(dāng)前的優(yōu)先級“高”，則入運算符棧 。 while (!(GetTop(S)==?? amp。 case ?)? : Pop(S, c)。 break。 Tdata = c。這些 指針，稱作“ 線索 ”。 線索鏈表 的類型描述： typedef enum { Link, Thread } PointerTag。 //當(dāng) *q不是 return (q)。 // 訪問后繼結(jié)點 } p = prchild。 prerchild = p。 int parent。 n*d(n1)=n*(d1)+1個，顯然造成很大的空間浪費。 A B C D E F G 125 typedef struct CTNode { int child。 // 結(jié)點數(shù)和根結(jié)