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

1、數(shù)據(jù)構(gòu)造復(fù)習(xí)(樹與二叉樹)一、二叉樹一、二叉樹或空，或由根和由互不相交的或空，或由根和由互不相交的左子樹、右子樹構(gòu)成。左子樹、右子樹構(gòu)成。1、二叉鏈、二叉鏈abcdfgeabcedfg性質(zhì)性質(zhì)1： 在二叉樹的第在二叉樹的第i (i0)層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)2： 深度為深度為k的二叉樹中至多有的二叉樹中至多有2k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k0)。性質(zhì)性質(zhì)3： 對(duì)任何一棵二叉樹對(duì)任何一棵二叉樹T，假設(shè)其終端結(jié)點(diǎn)數(shù)為，假設(shè)其終端結(jié)點(diǎn)數(shù)為n0,度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，那么，那么 n0=n2+1。性質(zhì)性質(zhì)4： 有有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

2、+1。性質(zhì)性質(zhì)5： 假設(shè)對(duì)一棵有假設(shè)對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層序從個(gè)結(jié)點(diǎn)的完全二叉樹按層序從1開場(chǎng)編號(hào)，那么對(duì)任一結(jié)點(diǎn)開場(chǎng)編號(hào)，那么對(duì)任一結(jié)點(diǎn)(i=i1, 那么其雙親結(jié)點(diǎn)是那么其雙親結(jié)點(diǎn)是i/2。(2)假設(shè)假設(shè)2i=n, 那么結(jié)點(diǎn)那么結(jié)點(diǎn)i的左孩的左孩 子是結(jié)點(diǎn)子是結(jié)點(diǎn)2i ；否那么結(jié)點(diǎn)；否那么結(jié)點(diǎn)i無無 左孩子。左孩子。(3)假設(shè)假設(shè)2i+1=0)個(gè)結(jié)點(diǎn)的有限集。個(gè)結(jié)點(diǎn)的有限集。在恣意一棵非空樹中：在恣意一棵非空樹中：(1)有且僅有一個(gè)根結(jié)點(diǎn)；有且僅有一個(gè)根結(jié)點(diǎn)；(2)除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)可分為除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)可分為 m(m=0)個(gè)互不相交的子樹。個(gè)互不相交的子樹。 (左孩子-右兄

3、弟)OacgbdefOacgbdefOacgbdefOacgbdef 先序遍歷樹： 1訪問根結(jié)點(diǎn) 2先序遍歷每一個(gè)子樹 先序遍歷序列： o ab cdfe gOacgbdef 后序遍歷樹： 1后序遍歷每一個(gè)子樹 2訪問根結(jié)點(diǎn) 后序遍歷序列： ba fdec g 03、哈夫曼碼：是一種前綴編碼即任一字符的編、哈夫曼碼：是一種前綴編碼即任一字符的編 碼都不是另一編碼的前綴。左支用碼都不是另一編碼的前綴。左支用0表示，右表示，右 支用支用1表示。表示。1 1、 二叉樹的帶權(quán)途徑長(zhǎng)度二叉樹的帶權(quán)途徑長(zhǎng)度 WPL = WPL = wklk wklk k=1k=1其中，其中，n:n:葉子結(jié)點(diǎn)個(gè)數(shù)，葉子結(jié)點(diǎn)

4、個(gè)數(shù)， wk : wk :第第k k個(gè)葉子的權(quán)，個(gè)葉子的權(quán)， lk : lk :第第k k個(gè)葉子到根的途徑長(zhǎng)度。個(gè)葉子到根的途徑長(zhǎng)度。 2 2、HuffmanHuffman樹的構(gòu)造方法樹的構(gòu)造方法 1 1將將w1,w2,.,wnw1,w2,.,wn看成看成n n個(gè)二叉?zhèn)€二叉樹；樹； 2 2選擇選擇 2 2 個(gè)根結(jié)點(diǎn)的值最小的二叉?zhèn)€根結(jié)點(diǎn)的值最小的二叉樹，樹，構(gòu)造構(gòu)造1 1個(gè)新的二叉樹；個(gè)新的二叉樹；.；直至剩；直至剩1 1個(gè)樹個(gè)樹止。止。 n 三、三、Huffman樹樹 (1) 構(gòu)造構(gòu)造huffman樹樹 以小值為左孩子以小值為左孩子 (2) 在哈夫曼樹的一切左分在哈夫曼樹的一切左分支上編上號(hào)碼支上編上號(hào)碼“0,右分支右分支上編上號(hào)碼上編上號(hào)碼“1； (3) 將根結(jié)點(diǎn)到每個(gè)葉子結(jié)將根結(jié)點(diǎn)到每個(gè)葉子結(jié) 點(diǎn)的途徑編碼串起來點(diǎn)的途徑編碼串起來,得到得到字符集的哈夫曼編碼。字符集的哈夫曼編碼。(4) =(25+36+50)*2 +(8+10+14)*4+(2+5)*5 =385 例例6.8 設(shè)通訊譽(yù)設(shè)通訊譽(yù)8個(gè)字符個(gè)字符abcdefgh, 各字符運(yùn)各字符運(yùn)用的相對(duì)頻率分別為用的相對(duì)頻率分別為 25,36,2,5,8,14,10,50, 設(shè)設(shè)計(jì)哈夫曼編碼計(jì)哈夫曼編碼, 求該樹的帶樹途徑長(zhǎng)度。