數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)樹(shù)與二叉樹(shù)1.pptVIP

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí) (樹(shù)與二叉樹(shù)),一、二叉樹(shù) 或空，或由根和由互不相交的 左子樹(shù)、右子樹(shù)構(gòu)成。 1、二叉鏈,第六章 樹(shù)和二叉樹(shù),a,b,c,d,f,g,e,a,b,c,e,d,f,g,性質(zhì)1： 在二叉樹(shù)的第i (i0)層上至多有2i-1個(gè)結(jié)點(diǎn)。 性質(zhì)2： 深度為k的二叉樹(shù)中至多有2k-1個(gè)結(jié)點(diǎn)(k0)。 性質(zhì)3： 對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0, 度為2的結(jié)點(diǎn)數(shù)為n2，則 n0=n2+1。 性質(zhì)4： 有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 +1。,2、二叉樹(shù)的性質(zhì),性質(zhì)5： 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層序從1開(kāi)始編號(hào)，則對(duì)任一結(jié)點(diǎn)(i1, 則其雙親結(jié)點(diǎn)是i/2。 (2)如果2i=n, 則結(jié)點(diǎn)i的左孩 子是結(jié)點(diǎn)2i ；否則結(jié)點(diǎn)i無(wú) 左孩子。 (3)如果2i+1=n, 則結(jié)點(diǎn)i的右 孩子是結(jié)點(diǎn)2i+1； 否則結(jié) 點(diǎn)i無(wú)右孩子 。,例.32個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，從根開(kāi)始，按層次從左到右用1-32編號(hào)。請(qǐng)回答： （1）它共有多少層？ （2）各層最左邊的結(jié)點(diǎn)的編號(hào)是多少？ （3）編號(hào)為6的結(jié)點(diǎn)的左孩子的編號(hào)是多少？ 它的右孩子呢？ （4）編號(hào)為16的結(jié)點(diǎn)的左孩子的編號(hào)是多少？ 它的右孩子呢？ （5）對(duì)于編號(hào)為8的結(jié)點(diǎn)，它的父結(jié)點(diǎn)的編號(hào)是多少？ 編號(hào)為13的結(jié)點(diǎn)呢？編號(hào)為1的結(jié)點(diǎn)呢？,二叉樹(shù)的遍歷：按某條搜索路徑訪問(wèn)二叉樹(shù)中每一個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。 遍歷方法有4種：先序遍歷，中序遍歷，后序遍歷，層次遍歷。,3、二叉樹(shù)的遍歷,先序遍歷二叉樹(shù)： （1）訪問(wèn)根結(jié)點(diǎn) （2）先序遍歷左子樹(shù) （3）先序遍歷右子樹(shù) 先序遍歷序列： abcdfge,1,2,3,4,5,6,7,a,b,c,d,f,g,e,中序遍歷二叉樹(shù)： （1）中序遍歷左子樹(shù) （2）訪問(wèn)根結(jié)點(diǎn) （3）中序遍歷右子樹(shù) 中序遍歷序列： bafgdce,a,b,c,d,f,g,e,1,2,3,4,5,6,7,后序遍歷二叉樹(shù)： （1）后序遍歷左子樹(shù) （2）后序遍歷右子樹(shù) （3）訪問(wèn)根結(jié)點(diǎn) 后序遍歷序列： bgfdeca,a,b,c,d,f,g,e,1,2,3,4,5,6,7,a,b,c,d,f,g,e,1,2,3,4,5,6,7,層次遍歷二叉樹(shù)： 按層次（1-k層)，每層從左到右依次訪問(wèn)二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)。 層次遍歷序列： abcdefg,例6.1 已知二叉樹(shù)先序遍歷序列是:abcdefg; 中序遍歷序列是:cbdaefg; （1）畫(huà)出該二叉樹(shù); （2）寫(xiě)出后序遍歷序列.(cdbgfea) （1） （2）寫(xiě)出后序遍歷序列：cdbgfea,a,b,c,d,e,f,g,1,2,3,4,5,6,7,二、樹(shù),1、 樹(shù)的定義 樹(shù)（Tree)是n(n=0)個(gè)結(jié)點(diǎn)的有限集。 在任意一棵非空樹(shù)中： (1)有且僅有一個(gè)根結(jié)點(diǎn)； (2)除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)可分為 m(m=0)個(gè)互不相交的子樹(shù)。,3、 樹(shù)與二叉樹(shù)的轉(zhuǎn)換 樹(shù)轉(zhuǎn)換成二叉樹(shù)：,(左孩子-右兄弟),O,a,c,g,b,d,e,f,O,a,c,g,b,d,e,f,2、 樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉鏈,O,a,c,g,b,d,e,f,(左孩子-右兄弟),4、 樹(shù)的遍歷,O,a,c,g,b,d,e,f,先序遍歷樹(shù)： （1）訪問(wèn)根結(jié)點(diǎn) （2）先序遍歷每一個(gè)子樹(shù) 先序遍歷序列： o ab cdfe g,O,a,c,g,b,d,e,f,后序遍歷樹(shù)： （1）后序遍歷每一個(gè)子樹(shù) （2）訪問(wèn)根結(jié)點(diǎn) 后序遍歷序列： ba fdec g 0,3、哈夫曼碼：是一種前綴編碼（即任一字符的編 碼都不是另一編碼的前綴）。左支用0表示，右 支用1表示。,1、 二叉樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL = wklk k=1 其中，n:葉子結(jié)點(diǎn)個(gè)數(shù)， wk :第k個(gè)葉子的權(quán)， lk :第k個(gè)葉子到根的路徑長(zhǎng)度。,2、Huffman樹(shù)的構(gòu)造方法 （1）將w1,w2,.,wn看成n個(gè)二叉樹(shù)； （2）選擇 2 個(gè)根結(jié)點(diǎn)的值最小的二叉樹(shù)， 構(gòu)造1個(gè)新的二叉樹(shù)；.；直至剩1個(gè)樹(shù)止。,n,三、Huffman樹(shù),(1) 構(gòu)造huffman樹(shù) 以小值為左孩子 (2) 在哈夫曼樹(shù)的所有左分支上編上號(hào)碼“0”,右分支上編上號(hào)碼“1”； (3) 將根結(jié)點(diǎn)到每個(gè)葉子結(jié) 點(diǎn)的路徑編碼串起來(lái),得到字符集的哈夫曼編碼。,(4) =(25+36+50)*2 +(8+10+14)*4+(2+5)*5 =385,例6.8 設(shè)通信用8個(gè)字符abcdefgh, 各字符使用的相對(duì)頻率分別為 25,36,2,5,8,14,10,5