【正文】 樹(shù)的帶權(quán)路徑長(zhǎng)度 : 樹(shù)中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根 結(jié)點(diǎn)的路徑長(zhǎng)度之和，記為： 一、哈夫曼樹(shù)的定義 根 6 哈夫曼樹(shù)統(tǒng)稱一類帶權(quán)路徑長(zhǎng)度最短的樹(shù)。 中序遍歷： 即： 依次從左至右 對(duì)森林中的每一棵 樹(shù) 進(jìn)行 后根遍歷 。 先序遍歷： 森林的遍歷 即： 依次從左至右 對(duì)森林中的每一棵 樹(shù) 進(jìn)行 先根遍歷 。 若樹(shù)不空，則自上而下、自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。 H D G F C I E B J H D G C E B F J I 137 由此，樹(shù)和森林的各種操作均可與二叉樹(shù)的操作相對(duì)應(yīng)?；蛘撸梢韵葘⑸种械拿恳豢脴?shù)變?yōu)槎鏄?shù)，然后將各二叉樹(shù)的根結(jié)點(diǎn)視為兄弟連在一起。從物理結(jié)構(gòu)來(lái)看，存儲(chǔ)它們的二叉鏈表是相同的，只是解釋不同。 結(jié)點(diǎn)結(jié)構(gòu) : firstchild data nextsibling 三、孩子 兄弟表示法 (二叉鏈表存儲(chǔ)） 128 A B C D E F G root A B C E D F G 如何找結(jié)點(diǎn) *x的第 i個(gè)孩子？ x 129 A B C D E F H G I 分別用雙親表示法、孩子鏈表、孩子 —兄弟表示法表示圖示樹(shù)。 // 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 } CTree。 ChildPtr firstchild。 A B C D E F G 125 typedef struct CTNode { int child。 123 Ⅲ. 以上兩種方法在實(shí)際應(yīng)用中都會(huì)遇到一些困難。 n*d(n1)=n*(d1)+1個(gè)，顯然造成很大的空間浪費(fèi)。 // 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) } PTree。 int parent。 缺點(diǎn)： 就插入和刪除結(jié)點(diǎn)而言，除需修 改指針外，還須相應(yīng)的修改線索。 prerchild = p。 三、如何建立 (中序 )線索鏈表？ 107 void InThreading(BiThrTree p) { if (p) { // 對(duì)以 p為根的非空二叉樹(shù)進(jìn)行中序線索化 InThreading(plchild)。 // 訪問(wèn)后繼結(jié)點(diǎn) } p = prchild。 //第 一個(gè)結(jié)點(diǎn) while (pRTag==Thread amp。 //當(dāng) *q不是 return (q)。 由于在線索鏈表中添加了遍歷中得到的 “前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍 歷的算法。 線索鏈表 的類型描述： typedef enum { Link, Thread } PointerTag。 101 typedef struct BiThrNode { TElemType data。這些 指針，稱作“ 線索 ”。 Tlchild = lc。 Tdata = c。 Tlchild = Trchild = NULL。 break。amp。 case ?)? : Pop(S, c)。 ch = *p。 while (!(GetTop(S)==?? amp。 Push(S, ??)。 若當(dāng)前的優(yōu)先級(jí)“高”，則入運(yùn)算符棧 。ch)。 else { 建根結(jié)點(diǎn) 。 // 構(gòu)造右子樹(shù) } return OK。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。ch)。 depth = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 首先分析 二叉樹(shù)的深度 和它的 左 、 右子樹(shù)深度 之間的關(guān)系。 // 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( Tlchild, count)。 75 void CountLeaf (BiTree T, intamp。 else return(Preorder_Seek (Trchild, x, p)) 。 } //else } // while return OK。 // 訪問(wèn)根結(jié)點(diǎn) Push(S,p)。 } //else } // while 71 void PreOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 p=plchild。 } // 根指針進(jìn)棧，遍歷左子樹(shù) else { //根指針退棧，訪問(wèn)根結(jié)點(diǎn)， Pop(S,p)。 遍歷左子樹(shù) if( !visit(pdata) ) return ERROR。 p=prchild。 }// InOrderTraverse 四、中序遍歷算法的非遞歸描述 67 非遞歸算法的執(zhí)行過(guò)程 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 訪問(wèn)： C (4) while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點(diǎn) if (p) { Push(S,p)。 } // 根指針進(jìn)棧，遍歷左子樹(shù) else { //根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù) Pop(S,p)。 e)) { InitStack(S)。 pre(T L)。 pre(T L)。 返回 返回 pre(T R)。 } } } 64 void pre(BiTree t) { if (t!=NULL) { printf (%d\t,tdata)。amp。 // 遍歷左子樹(shù) PreOrder(Trchild, Visit)。 中 （根） 序的遍歷算法： 57 A D B C L D R B L D R L D R A D C L D R 中序遍歷序列： B D A C 中序遍歷 : 58 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）后序遍歷左子樹(shù)； （ 2）后序遍歷右子樹(shù)； （ 3）訪問(wèn)根結(jié)點(diǎn)。 52 “遍歷 ”是任何類型均有的操作， 對(duì)線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼 )， 故不需要另加討論。 parent lchild data rchild 結(jié)點(diǎn)結(jié)構(gòu) : C 語(yǔ)言的類型描述如下 : 2． 三叉鏈表 47 A D E B C F ? ? ? ? ? ? ? root ? A B D C F E 48 練習(xí)：畫(huà)出下面二叉樹(shù)的三叉鏈表。 // 左右孩子指針 } BiTNode, *BiTree。 根據(jù)二叉樹(shù)的性質(zhì) 2，有 k個(gè)結(jié)點(diǎn)的二叉樹(shù)，需要長(zhǎng)度為 2k1 的一維數(shù)組 一、 二叉樹(shù)的順序存儲(chǔ)表示 41 完全二叉樹(shù) 一般二叉樹(shù) 的順序表示 的順序表示 二叉樹(shù)的順序表示 1 1 2 3 4 5 6 7 8 9 10 14 1 2 3 4 6 7 8 9 12 14 2 4 8 9 10 5 6 7 3 1 2 3 7 6 4 8 9 12 5 10 11 13 42 實(shí)現(xiàn)： 按滿二叉樹(shù)中結(jié)點(diǎn)的編號(hào)，依次存放二叉 樹(shù)中的數(shù)據(jù)元素。 (2) 若 2in，則該結(jié)點(diǎn)無(wú)左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其 左孩子 結(jié)點(diǎn)； (3) 若 2i+1n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)， 否則，編號(hào)為 2i+1 的結(jié)點(diǎn)為其 右孩子 結(jié)點(diǎn) 。 二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)， 則第 i 層的結(jié)點(diǎn)數(shù) = 2i2? 2 = 2i1 。T)。 p所指結(jié)點(diǎn)的原右或左子樹(shù)成為 c的右子樹(shù)。e, value)。 LevelOrderTraverse(T, Visit()) // 層序遍歷 。 BiTreeDepth(T)。 RightChild(T, e)。 否 26 練習(xí)：具有 3個(gè)結(jié)點(diǎn)的二叉樹(shù)有多少種？ 27 二叉樹(shù)的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 ADT BinaryTree： P121 28 Root(T)。 有向樹(shù)： 無(wú)序 樹(shù)： D H I J M D I H J M = 20 雙親在同一層的結(jié)點(diǎn) A B C D E F G H I J K L M 結(jié)點(diǎn) A的度： 結(jié)點(diǎn) B的度： 結(jié)點(diǎn) M的度： 葉子： 結(jié)點(diǎn) A的孩子： 結(jié)點(diǎn) B的孩子： 結(jié)點(diǎn) I的雙親： 結(jié)點(diǎn) L的雙親： 結(jié)點(diǎn) B， C， D為兄弟 結(jié)點(diǎn) K， L為兄弟 樹(shù)的度： 結(jié)點(diǎn) A的層次： 結(jié)點(diǎn) M的層次： 樹(shù)的深度： 結(jié)點(diǎn) F， G為堂兄弟 結(jié)點(diǎn) A是結(jié)點(diǎn) F， G的祖先 結(jié)點(diǎn) B的子孫： 3 2 0 B， C， D E， F 3 K， L， F， G， M， I ， J D E 1 4 例 E， K， L， F 4 21 線性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無(wú)前驅(qū) ) 根結(jié)點(diǎn) (無(wú)前驅(qū) ) 最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼 ) 多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、一個(gè)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、多個(gè)后繼 ) 22 二叉樹(shù) 23 二叉樹(shù) 或?yàn)?空樹(shù) ；或是由一個(gè) 根結(jié)點(diǎn)加上 兩棵 分別稱為 左子樹(shù) 和 右子樹(shù) 的、互不相交的 二叉樹(shù) 組成。 森林： 是 m（ m≥ 0）棵互 不相交的樹(shù)的集合。 兄弟 結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)。 A B C D E F G H I J M K L 定義根結(jié)點(diǎn)的層次為 1,第 t層結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)的層次為 t+1。 (結(jié)點(diǎn)擁有子樹(shù)數(shù)目 ) 樹(shù)中所有結(jié)點(diǎn)的度的最大值。T) // 銷毀樹(shù)結(jié)構(gòu) DeleteChild(amp。T, definition) // 按定義構(gòu)造樹(shù) Assign(T, cur_e, value) // 給當(dāng)前結(jié)點(diǎn)賦值 InsertChild(amp。 ?5 A 只有根結(jié)點(diǎn)的 樹(shù) A B C D E F G H I J K L M 有子樹(shù)的 樹(shù) 根