數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)PPT學(xué)習(xí)教案

1、數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)一、二叉樹(shù)一、二叉樹(shù)或空，或由根和由互不相交的或空，或由根和由互不相交的左子樹(shù)、右子樹(shù)構(gòu)成。左子樹(shù)、右子樹(shù)構(gòu)成。1、二叉鏈、二叉鏈abcdfgeabcedfg第1頁(yè)/共18頁(yè)性質(zhì)性質(zhì)1： 在二叉樹(shù)的第在二叉樹(shù)的第i (i0)層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)2： 深度為深度為k的二叉樹(shù)中至多有的二叉樹(shù)中至多有2k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k0)。性質(zhì)性質(zhì)3： 對(duì)任何一棵二叉樹(shù)對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(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)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完

2、全二叉樹(shù)的深度為 +1。第2頁(yè)/共18頁(yè)性質(zhì)性質(zhì)5： 如果對(duì)一棵有如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層序從個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層序從1開(kāi)始編號(hào)，則對(duì)任一結(jié)點(diǎn)開(kāi)始編號(hào)，則對(duì)任一結(jié)點(diǎn)(i=i1, 則其雙親結(jié)點(diǎn)是則其雙親結(jié)點(diǎn)是i/2。(2)如果如果2i=n, 則結(jié)點(diǎn)則結(jié)點(diǎn)i的的左孩左孩 子是結(jié)點(diǎn)子是結(jié)點(diǎn)2i ；否則結(jié)點(diǎn)否則結(jié)點(diǎn)i無(wú)無(wú) 左孩子左孩子。(3)如果如果2i+1=0)個(gè)結(jié)點(diǎn)的有限集。個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹(shù)中：在任意一棵非空樹(shù)中：(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è)互不相交的子樹(shù)。個(gè)互不相交的子樹(shù)。第

3、11頁(yè)/共18頁(yè) (左孩子-右兄弟)OacgbdefOacgbdef第12頁(yè)/共18頁(yè)Oacgbdef第13頁(yè)/共18頁(yè)Oacgbdef 先序遍歷樹(shù)：先序遍歷樹(shù)： （1）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn) （2）先序遍歷每一個(gè)子樹(shù)）先序遍歷每一個(gè)子樹(shù) 先序遍歷序列：先序遍歷序列： o ab cdfe g第14頁(yè)/共18頁(yè)Oacgbdef 后序遍歷樹(shù)：后序遍歷樹(shù)： （1）后序遍歷每一個(gè)子樹(shù)）后序遍歷每一個(gè)子樹(shù) （2）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn) 后序遍歷序列：后序遍歷序列： ba fdec g 0第15頁(yè)/共18頁(yè)3、哈夫曼碼：是一種前綴編碼（即任一字符的編、哈夫曼碼：是一種前綴編碼（即任一字符的編 碼都不是另一

4、編碼的前綴）。左支用碼都不是另一編碼的前綴）。左支用0表示，右表示，右 支用支用1表示。表示。1 1、 二叉樹(shù)的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度 WPL = wklk k=1其中，其中，n:n:葉子結(jié)點(diǎn)個(gè)數(shù)，葉子結(jié)點(diǎn)個(gè)數(shù)， w wk k : :第第k k個(gè)葉個(gè)葉子子的權(quán)，的權(quán)， l lk k : :第第k k個(gè)葉個(gè)葉子到根的路徑長(zhǎng)度子到根的路徑長(zhǎng)度。 2 2、HuffmanHuffman樹(shù)的構(gòu)造方法樹(shù)的構(gòu)造方法 （1 1）將）將ww1 1,w,w2 2, ,.,w.,wn n 看成看成n n個(gè)二叉樹(shù)；個(gè)二叉樹(shù)； （2 2）選擇）選擇 2 2 個(gè)根結(jié)點(diǎn)的值最小的二叉樹(shù)，個(gè)根結(jié)點(diǎn)的值最小的二叉樹(shù)，

5、構(gòu)造構(gòu)造1 1個(gè)新的二叉樹(shù)；個(gè)新的二叉樹(shù)；. .；直至剩；直至剩1 1個(gè)樹(shù)止。個(gè)樹(shù)止。 n 三、三、Huffman樹(shù)樹(shù)第16頁(yè)/共18頁(yè) (1) 構(gòu)造構(gòu)造huffman樹(shù)樹(shù) 以小值為左孩子以小值為左孩子 (2) 在哈夫曼樹(shù)的所有左分在哈夫曼樹(shù)的所有左分支上編上號(hào)碼支上編上號(hào)碼“0”,右分支右分支上編上號(hào)碼上編上號(hào)碼“1”； (3) 將根結(jié)點(diǎn)到每個(gè)葉子結(jié)將根結(jié)點(diǎn)到每個(gè)葉子結(jié) 點(diǎn)的路徑編碼串起來(lái)點(diǎn)的路徑編碼串起來(lái),得到得到字符集的哈夫曼編碼。字符集的哈夫曼編碼。(4) =(25+36+50)* *2 +(8+10+14)* *4+(2+5)* *5 =385 例例6.8 設(shè)通信用設(shè)通信用8個(gè)字符個(gè)字符abcdefgh, 各字符使用的相各字符使用的相對(duì)頻率分別為對(duì)頻率分別為 25,36,2,5,8,14,10,50, 設(shè)計(jì)哈夫曼編碼設(shè)計(jì)哈夫曼編碼, 求該樹(shù)的帶樹(shù)路徑長(zhǎng)度。求該