【正文】 單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式 第二級(jí) 第三級(jí) 第四級(jí) 第五級(jí) 145 哈 夫 曼 樹 與 哈 夫 曼 編 碼 ?引例 — 問題的提出 ?哈夫曼樹系統(tǒng)理論 ?問題的解決 哈 夫 曼 樹 David Huffman 按此程序流程，有 80%的數(shù)據(jù)需進(jìn)行 3次或 3次以上比較才能得出結(jié)果。 先序遍歷 森林中第一棵樹的子樹森林 。然后去掉所有雙親到右孩子的連線。即一棵二叉樹或樹可 唯一 的對(duì)應(yīng)一個(gè)二叉鏈表。 雙親結(jié)點(diǎn)結(jié)構(gòu) : data firstchild 126 typedef struct { CTBox nodes[MAX_TREE_SIZE]。 A B C D E F G 124 1 0 0 0 2 2 4 data firstchild 0 A 1 B 2 C 3 D 4 E 5 F 6 G 6 4 5 1 2 3 parent 與雙親表示法相反，孩子表示法便于實(shí)現(xiàn)涉及孩子的操作，卻不太適合涉及雙親的操作。 每個(gè)結(jié)點(diǎn)包含 多個(gè)指針域 每個(gè)指針指向一棵子樹的根結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)究竟應(yīng)設(shè) 多少個(gè)指針域 ？ 有以下幾種 設(shè)計(jì)方式 ： 122 Ⅰ. 若以樹的度 d來設(shè)置指針域的個(gè)數(shù)，顯然各個(gè)結(jié)點(diǎn)是 同構(gòu)的，便于各種操作。 對(duì)于求雙親或祖先（包括根結(jié)點(diǎn)）都十分方便， 但是要求結(jié)點(diǎn)的孩子或其他后代，則需遍歷整個(gè)結(jié)構(gòu)。 plchild = pre。 prchild!=T) { p = prchild。 BiThrNode * next( BiThrNode *p) { if (prtag) return (prchild) // prtag為 1,表示線索 , else { //右子樹非空 即右子樹為空 q= prchild。 // 左右指針 PointerTag LTag, RTag。 } 94 僅知二叉樹的先序序列“ abcdefg” 不能唯一確定一棵二叉樹， 由二叉樹的先序和中序序列建樹 如果同時(shí)也知二叉樹的中序序列“ cbdaegf”,則會(huì)如何？ 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 95 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 fg a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 96 線索二叉樹 ? 何謂線索二叉樹？ ? 線索鏈表的遍歷算法 ? 如何建立線索鏈表？ 97 一、何謂線索二叉樹？ 遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。 } 93 建子樹的算法為： void CrtSubtree (Bitreeamp。 // 建子樹并入棧 PND Pop(S, c)。 } // CrtExptree … … 90 switch (ch) { case ?(? : Push(S, ch)。 p = exp。 入操作數(shù)棧 。ch)。 39。 else { depthLeft = TreeDepth( Tlchild )。amp。p) {// 若二叉樹中存在和 x相同的元素，則 p指向該結(jié)點(diǎn)并返回 true if (T) { if (Tdata==x) { p=T。 p=T。 p=prchild。 p=plchild。 p=prchild。 T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R)。 pre(T L)。 else { DispLeaf(blchild)。 e)) { // 先序遍歷二叉樹 if (T) { Visit(Tdata) 。 即找一個(gè)完整而有規(guī)律的走法，得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。 極端情形 : 只有右單支的二叉樹 1 3 7 15 31 1 3 7 15 31 43 二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示 1. 二叉鏈表 2．三叉鏈表 3．線索鏈表 44 typedef struct BiTNode { // 結(jié)點(diǎn)結(jié)構(gòu) TElemType data。特點(diǎn)： 每一層上的結(jié)點(diǎn)數(shù)都是最 大結(jié)點(diǎn)數(shù) . 完全二叉樹 ： 樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中 編號(hào)為 1 至 n 的結(jié)點(diǎn) 一一對(duì)應(yīng)。T)。T)。 RightSibling(T, e)。 ?二叉樹的子樹有左、右之分，其次序不能任意顛倒。 子孫 結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)稱為此結(jié)點(diǎn) ~。 度大于零的結(jié)點(diǎn)。p, i, c) // 將以 c為根的樹插入為結(jié)點(diǎn) p的第 i棵子樹 11 ClearTree(amp。 ? 特點(diǎn)： – 樹中各子樹是互不相交的集合。T) // 初始化構(gòu)造空樹 插入類： CreateTree(amp。 分支的個(gè)數(shù)。 雙親 結(jié)點(diǎn)：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。 有序樹： (１ ) 有確定的根； (２ ) 樹根和子樹根之間為有向關(guān)系。 LeftChild(T, e)。 PostOrderTraverse(T, Visit()) // 后序遍歷 。 InsertChild(T, p, LR, c) // 根據(jù) LR為 0或 1，插入 c為 T中 p所指結(jié)點(diǎn)的左或右子樹。 (i≥ 1) 用歸納法證明 ： 歸納基 ： 歸納假設(shè)： 歸納證明： i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)， 2i1 = 20 = 1； 假設(shè)對(duì)所有的 j， 1≤ j ? i， 命題成立 。樹中各結(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同。 // 左右孩子指針、 雙親指針 } TriTNode, *TriTree。 先 （根） 序的遍歷算法： 55 A D B C D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C 先序遍歷 : 56 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結(jié)點(diǎn)； （ 3）中序遍歷右子樹。f(brchild) 其他情況 63 void DispLeaf(BTNode *b) { if (b!=NULL) { if (blchild==NULL amp。 } } 主程序 Pre( T ) 返回 返回 pre(T R)。 T C printf(C)。 p=plchild。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=plchild。 p=prchild。 p=prchild。 由此， 需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點(diǎn)” 的操作改為 :若是葉子，則計(jì)數(shù)器增 1。由此， 需先分別求得左、右子樹的深度， 算法中 “ 訪問結(jié)點(diǎn) ” 的操作為 :求得左、右子樹深度的最大值，然后加 1 。T) { scanf(amp。 // 構(gòu)造左子樹 CreateBiTree(Trchild)。 } 由前綴表示式建樹的算法的基本操作： 87 a+b (a+b) c – d/e a+b c 分析表達(dá)式和二叉樹的關(guān)系 : a b + a b c + a b c + (a+b) c a b c d e + / 88 算法的 基本操作 : scanf(amp。T, char exp[] ) { InitStack(S)。 // 非運(yùn)算符 ,即字母 ,建葉子結(jié)點(diǎn)并入棧 PND else { } if ( ch!= ?? ) { p++。 defult : } // switch … … 91 while(!Gettop(S, c) amp。 Tdata = char。 Pop(PND, lc)。 如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“ 線索鏈表 ”。 p = Next(p) ) Visit (p)。 //最左下的結(jié)點(diǎn)是中序遍歷的 Visit(pdata)。把中序遞歸遍歷算法中的Visit(pdata)改為 設(shè)置線索 的語句。 // 右子樹線索化 } // if } // InThreading 108 0 A 0 ? 0 B 0 0 C 0 ? ? 0 D 0 ? ? 0 E 0 ? root pre == NULL current 109 0 A 0 ? 1 B 0 0 C 0 ? ? 0 D 0 ? ? 0 E 0 ? root pre == NULL current 110 0 A 0 ? 1 B 0 0 C 0 ? 1 D 0 ? ? 0 E 0 ? root pre current 111 0 A 0 ? 1 B 0 0 C 0 ? 1 D 1 ? 0 E 0 ? root pre current 112 0 A 0 ? 1 B 0 0 C 0 ? 1 D 1 1 E 0 ? root pre current 113 0 A 0 ? 1 B 0 0 C 0 ? 1 D 1 1 E 1 root pre current 114 0 A 0 ? 1 B 0 0 C 1 ? 1 D 1 1 E 1 root pre 后處理 115 線索樹的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)： 線索樹由于含有其前驅(qū)、后繼的 信息，因此在進(jìn)行各種操作時(shí)顯 得比較方便。 int r, n。雖然節(jié)省了空間，但給運(yùn)算帶來了不便。 孩子結(jié)點(diǎn)結(jié)構(gòu) : child nextchild 孩子鏈表 C語言的類型描述 : typedef struct { TElemType data。 } CSNode, *CSTree。 (因?yàn)闃涓鶝]有兄弟 ) 134 (二 ) 森林與二叉樹之間的轉(zhuǎn)換 在把森林轉(zhuǎn)換為二叉樹時(shí)，可以把森林中除第一棵樹以外的其它所有樹的根結(jié)點(diǎn)看作第一棵樹根結(jié)點(diǎn)的 兄弟 結(jié)點(diǎn)。 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)