圖論討論課(二叉樹的理論)

1、 二叉樹問題 小組成員：劉化慶 胥棟寬 唐珊珊內(nèi)容概要 基本概念基本概念 二叉樹的定義與典型性質(zhì)二叉樹的定義與典型性質(zhì) 二叉樹的存儲二叉樹的存儲 二叉樹的遍歷二叉樹的遍歷 線索二叉樹線索二叉樹 Huffman樹樹基本概念 樹根 樹葉 孩子 雙親 兄弟 堂兄弟 祖先 子孫 層數(shù) 樹高 左子樹vs右子樹 有序樹vs無序樹 t叉樹 樹的表示方法： 直觀法 集合法 文氏圖 目錄法二叉樹的定義與典型性質(zhì)定義定義典型性質(zhì)：典型性質(zhì)：(a)二叉樹的第 i 層上至多有 2i 1個結(jié)點(b)(b)深度為深度為 k k 的二叉樹至多有的二叉樹至多有 2 2 k k-1-1個結(jié)點個結(jié)點(k(k 1)1)(c)對任何

2、一棵二叉樹T, 如果其葉結(jié)點數(shù)為 n0, 度為2的結(jié)點數(shù)為 n2,則n0n21（葉子和分支點的關(guān)系)(d)設T是高為h的 v 階二叉樹，則(e)設T是高為h的 v 階二叉樹，則滿二叉樹滿二叉樹完全二叉樹完全二叉樹二叉樹的存儲順序存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：二叉鏈式存儲結(jié)構(gòu)：二叉鏈式存儲結(jié)構(gòu)：三叉鏈式存儲結(jié)構(gòu)：三叉鏈式存儲結(jié)構(gòu)：二叉樹的遍歷 先序：樹根、左子樹、右子樹 中序：左子樹、樹根、右子樹 后序：左子樹、右子樹、樹根 例： 先序：- + a * b c d / e f 中序：a + b * c d e / f 后序：a b c d - * + e f / -二叉樹的遍歷 void InOrde

3、rTraverse(BiTree T, Status(*Visit) /采用二叉鏈表存貯二叉樹,visit()是訪問結(jié)點的函數(shù) /中序遍歷二叉樹 /對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit( ) if (T) /若二叉樹為空，結(jié)束返回InOrderTraverse(T-lchild, Visit); /遍歷左子樹Visit(T-data)； /訪問根結(jié)點InOrderTraverse(T-rchild, Visit); /遍歷右子樹 / InOrderTraverse 線索二叉樹二叉樹的遍歷存在如下問題： (a)遍歷算法要復雜的多，費時的多； (b)為檢索或查找二叉樹中某結(jié)點在某種遍歷下的后繼，必須從

4、根開始遍歷，直到找到該結(jié)點及后繼 如果能將二叉樹線性化，就可以減化遍歷算法，如果能將二叉樹線性化，就可以減化遍歷算法，提高遍歷速度提高遍歷速度線索二叉樹 lchildLTagdataRTagrchild 0 0 lchild域指示結(jié)點的左孩子域指示結(jié)點的左孩子 ，表示，表示為左孩子指針為左孩子指針 LTagLTag= 1 = 1 域指示結(jié)點的前驅(qū)，域指示結(jié)點的前驅(qū)， 表示表示為線索為線索 0 域指示結(jié)點的右孩子，表示域指示結(jié)點的右孩子，表示為右孩子指針為右孩子指針 RTagRTag= 1 = 1 域指示結(jié)點的后驅(qū)，域指示結(jié)點的后驅(qū)， 表示表示為線索為線索中序線索二叉樹舉例中序線索二叉樹舉例AB

5、CDE A B D C ET中序序列：BCAED中序線索二叉樹0000111111遍歷Huffman樹又稱最優(yōu)二叉樹，它是n個帶權(quán)葉子結(jié)點構(gòu)成的所 有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 =35 222444555777 問題： 已知已知t個權(quán)值，個權(quán)值，w1、w2、wt，如何構(gòu)造，如何構(gòu)造Huffman樹？樹？定理例例9已知權(quán)值 W= 5, 6, 2, 9, 7 56275276976713952767139527952716671329 Huffman編碼編碼 問題描述問題描述: 電報傳送 A(00) B(01) C(10) D(11) “ABACCDA” = “00010010101100” (a)盡可能短 A(0) B(00) C(1) D(01) (b)單一解釋 “ABACCDA” = “000011010”（多種解釋）前綴編碼前綴編碼 互不為前綴互不為前綴 例： 是：1,00,01001 不是：1,00,00101 定理定理 由一棵樹給定的由一棵樹給定的2叉樹可以產(chǎn)生一個二元前綴碼叉樹可以產(chǎn)生一個二元前綴碼例 在