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

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