【正文】 WPL=?wi li i=1 n 報(bào)文長 =?Pi li i=1 n 110 假設(shè)某系統(tǒng)通信聯(lián)絡(luò)中只可能出現(xiàn) 8種字符 ,其出現(xiàn)概率為 ， ， ， ， ， ， ， ，試設(shè)計(jì)哈夫曼編碼。 概念 利用哈夫曼樹可以構(gòu)造不等長的二進(jìn)制編碼，并且構(gòu)造所得的編碼是一種 最優(yōu)前綴編碼 ，即可以使所傳信息的總長度最短。 m1 = ht[j].weight。 /*m1存放 最小權(quán)值 ,s1是 m1在數(shù)組的 下標(biāo) */ m1=m2=MAXINT。s1,amp。i=m。 for(i=1。 存儲(chǔ)結(jié)構(gòu) 每個(gè)結(jié)點(diǎn)需包含其雙親結(jié)點(diǎn)信息和孩子結(jié)點(diǎn)信息，所以構(gòu)成一個(gè)靜態(tài)三叉鏈表。 樹的帶權(quán)路徑長度： 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，稱為樹的帶權(quán)路徑長度，通常記為 WPL： WPL=?wi li i=1 n 其中： n為葉子結(jié)點(diǎn)的個(gè)數(shù)； wi為第 i個(gè)葉子的權(quán)值； li為第 i個(gè)葉子結(jié)點(diǎn)的路徑長度。 還原 ：將各棵孤立的二叉樹按二叉樹還原為一般樹的方法還原為樹。 抹線 ：抹掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子的連線。 } CSNode, *CSTree。 分析： 67 由結(jié)點(diǎn)序列恢復(fù)二叉樹 ?可 恢復(fù)二叉樹的結(jié)點(diǎn)序列組合： （ 1） 先序 序列和 中序 序列 （ 2） 中序 序列和 后序 序列 ?不可 恢復(fù)二叉樹的結(jié)點(diǎn)序列組合： 先序 序列和 后序 序列 68 a b c d e f g c b d a e g f 例如 : a a b b c c d d e e f fgg a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 69 由遍歷序列確定二叉樹 練習(xí)： 由 先序 和 中序 序列恢復(fù)二叉樹， 并寫出后序遍歷序列。 else { p=(BiTreeNode *) malloc(sizeof(BiTreeNode))。 } 59 五、由遍歷序列確定二叉樹 在對(duì)一棵二叉樹進(jìn)行遍歷，只要遍歷的策略已確定，就可以得到一個(gè)唯一的結(jié)點(diǎn)序列。 } 57 求二叉樹的深度 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。 if (root==NULL) LeafCount = 0。 由此， 需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點(diǎn)” 的操作改為 :若是葉子，則計(jì)數(shù)器增 1。 Preorder(rootrchild)。 /*中序遍歷右子樹 */ } } 中序遍歷 48 后序遍歷 void PostOrder(BiTree root) /* 后序遍歷二叉樹 ， root為二叉樹根結(jié)點(diǎn)的指針 */ {if(root!=NULL) { PostOrder(root LChild)。 41 中序遍歷（ LDR）操作過程 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結(jié)點(diǎn)； （ 3）中序遍歷右子樹。 struct Node *parent。 29 單支二叉樹 1 3 7 A B C A B C D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 D 15 順序存儲(chǔ)只適用于完全二叉樹和滿二叉樹 30 二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 對(duì)于任意的二叉樹來說，每個(gè)結(jié)點(diǎn)最多只有兩個(gè)孩子，我們可以設(shè)計(jì)每個(gè)二叉樹結(jié)點(diǎn)包括三個(gè)域： 數(shù)據(jù)域、左孩子域和右孩子域 。 完全二叉樹： 樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中 編號(hào)為 1 至 n 的結(jié)點(diǎn) 一一對(duì)應(yīng)。 (10) Clear（ bt）： 清除操作。求二叉樹 bt中結(jié)點(diǎn) x的雙親結(jié)點(diǎn)。 樹中葉子結(jié)點(diǎn)所在的最大層次 11 任何一棵非空樹是一個(gè)二元組 Tree =（ root， F） 其中： root 被稱為根結(jié)點(diǎn)， F 被稱為子樹森林 森林： 是 m（ m≥ 0）棵互不相交的樹的集合 A root B E F K L C G D H I J M F 12 線性結(jié)構(gòu) 樹型結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無前驅(qū) ) 根結(jié)點(diǎn) (無前驅(qū) ) 最后一個(gè)數(shù)據(jù)元素 (無后繼 ) 多個(gè)葉子結(jié)點(diǎn) (無后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、 一個(gè)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、 多個(gè)后繼 ) 對(duì)比 樹型結(jié)構(gòu) 和 線性結(jié)構(gòu) 的結(jié)構(gòu)特點(diǎn) 13 二叉樹的類型定義 二、二叉樹的基本操作 一、二叉樹的定義 三、二叉樹的性質(zhì) 14 二叉樹或?yàn)?空樹 ；或是由一個(gè) 根結(jié)點(diǎn) 加上 兩棵 分別稱為 左子樹 和 右子樹的、 互不交的 二叉樹 組成。 (9) InsertChild（ Tree， p， Child）： 樹 Tree存在， p指向 Tree中某個(gè)結(jié)點(diǎn)，非空樹 Child與Tree不相交。 (4) TreeEmpty（ Tree）： 若 Tree為空，則返回TRUE，否則返回 FALSE。每棵子樹的 根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或 多個(gè)直接后繼。 4 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)) 5 數(shù)據(jù)對(duì)象 D：一個(gè)集合，該集合中的所有元素具有相同的特性。 (5) Root（ Tree）： 返回樹 Tree的根。將 Child插入 Tree中，做 p所指向結(jié)點(diǎn)的子樹。 A B C D E F G H K 根結(jié)點(diǎn) 左子樹 右子樹 二叉樹中不存在度大于 2的結(jié)點(diǎn)，并且二叉樹的子樹有 左子樹和右子樹 之分！ 15 二、二叉樹的基本操作 ： (1)Initiate（ bt）：將 bt初始化為空二叉樹。若結(jié)點(diǎn) x是二叉樹的根結(jié)點(diǎn)或二叉樹 bt中無結(jié)點(diǎn) x，則返回“空”。將二叉樹 bt置為空樹。 23 結(jié)點(diǎn)號(hào)與結(jié)點(diǎn)位置一一對(duì)應(yīng) ? 性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的 深度為 ? log2n? +1 證明： 設(shè) 完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k1 1n ≤ 2k 1,即 2k1≤ n 2k 即 k1 ≤ log2 n k 因?yàn)? k 只能是整數(shù)，因此， k =?log2n? + 1 24 ?性質(zhì) 5 ： 若對(duì)含 n 個(gè)結(jié)點(diǎn)的 完全二叉樹 從上到下且從左至右進(jìn)行 1 至 n 的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為 i 的結(jié)點(diǎn)： (1) 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親 , 否則，編號(hào)為 ?i/2? 的結(jié)點(diǎn)為其 雙親 結(jié)點(diǎn) 。 1. 二叉鏈表 2． 三叉鏈表 有時(shí)，為了找到父結(jié)點(diǎn)，可以在二叉鏈表中增加一個(gè) Parent域 ， Parent域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。 struct Node *lchild。 42 后序遍歷（ LRD）操作過程 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點(diǎn)。 /*后序遍歷左子樹 */ PostOrder(root RChild)。 } 輸出二叉樹中的結(jié)點(diǎn) 說明：輸出二叉樹中結(jié)點(diǎn)無次序要求， 三 種遍歷都可用。 55 void leaf(BiTree root) { if(root!=NULL) {leaf(rootLChild)。 else if ((rootLChild==NULL) amp。由此，需先分別求得左、右子樹的深度， 算法中“訪問結(jié)點(diǎn)”的操作為 :求得左、右子樹深度的最大值，然后加 1 。 那么，給定一個(gè)遍歷的結(jié)點(diǎn)序列，能否唯一的確定一棵二叉樹？ 答案： 不能！ 61 先序序列： A B C 結(jié)點(diǎn)序列確定二叉樹的不唯一性 A B C A B C A B C A B C 中序序列： B A C 后序序列： C B A 62 ?由擴(kuò)展的結(jié)點(diǎn)序列恢復(fù)二叉樹 在前面講述的結(jié)點(diǎn)序列中，我們忽略了 空子樹 的輸出。 pdata=ch。 先序序列： E B A D C F H G I K J 中序序列： A B C D E F G H I J K E B A D F H G 后序序列： A C D B G J K I H F