大學(xué)數(shù)據(jù)結(jié)構(gòu)課件第6章樹和二叉樹

1、1F 6.1 樹的定義和基本術(shù)語(yǔ)F 6.2 二叉樹F 6.3 遍歷二叉樹和線索二叉樹F 6.4 樹和森林F 6.6 赫夫曼樹及其應(yīng)用 特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè) 直接后繼（直接后繼（1：n）第6章 樹和二叉樹21.樹的定義 注：注：樹的定義具有樹的定義具有遞歸性遞歸性，即樹中還有樹。，即樹中還有樹。由一個(gè)或多個(gè)（n 0）結(jié)點(diǎn)組成的有限集合。在任何一棵非空樹T中：（1）有且僅有一個(gè)結(jié)點(diǎn)稱為根（root）；（2）當(dāng)n1時(shí)，其余的結(jié)點(diǎn)分為m（m 0）個(gè) 互不相交的有限集合T1、T2Tm。每個(gè) 集合本身又是棵樹，被稱作這個(gè)根的子樹。6.1 樹的定

2、義和基本術(shù)語(yǔ)3A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM根根子樹子樹6.1 樹的定義和基本術(shù)語(yǔ)4樹的抽象數(shù)據(jù)類型定義D D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D:數(shù)據(jù)操作數(shù)據(jù)操作P:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R:若若D D是空集，則稱為空樹；是空集，則稱為空樹；/允許允許n=0n=0若若D D中僅含一個(gè)數(shù)據(jù)元素，則中僅含一個(gè)數(shù)據(jù)元素，則R R為空集；為空集；其他情況下的其他情況下的R R存在二元關(guān)系：存在二元關(guān)系： RootRoot唯一唯一/關(guān)于根的說明關(guān)于根的說明 DjDk= /關(guān)于子樹不相交的說明關(guān)于子樹不相交的說明 /關(guān)于數(shù)據(jù)元素的說明關(guān)于

3、數(shù)據(jù)元素的說明/至少至少1515個(gè)個(gè)6.1 樹的定義和基本術(shù)語(yǔ)5圖形表示法嵌套集合表示法廣義表表示法凹入表示法（目錄表示法）樹的表示方法6.1 樹的定義和基本術(shù)語(yǔ)6圖形表示法：大連工業(yè)大學(xué)大連工業(yè)大學(xué)信息學(xué)院信息學(xué)院生物與食品學(xué)院生物與食品學(xué)院外語(yǔ)學(xué)院外語(yǔ)學(xué)院數(shù)學(xué)數(shù)學(xué)物理物理電信電信計(jì)算機(jī)計(jì)算機(jī)根子樹ABCDEFGH6.1 樹的定義和基本術(shù)語(yǔ)7廣義表表示法：ABCDEFGH根根作為由子樹森林組成的作為由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左邊A（B，C，D）A（B，C（E,F,G,H），），D）凹入表示法：ABCDEFGH6.1 樹的定義和基本術(shù)語(yǔ)8ABCDEFGH嵌套表示法：A

4、BDCEGFH6.1 樹的定義和基本術(shù)語(yǔ)92.若干術(shù)語(yǔ) ABCDJEFG HIKLM 根根-根結(jié)點(diǎn)（沒有前驅(qū)）根結(jié)點(diǎn)（沒有前驅(qū)） 森林森林-指指m m棵不相交的樹的集合棵不相交的樹的集合有序樹有序樹-結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）無(wú)序樹無(wú)序樹-結(jié)點(diǎn)各子樹可互換位置結(jié)點(diǎn)各子樹可互換位置 雙親雙親-上層的那個(gè)結(jié)點(diǎn)（直接前驅(qū)）上層的那個(gè)結(jié)點(diǎn)（直接前驅(qū)） 孩子孩子-下層結(jié)點(diǎn)的子樹的根（直接后繼）下層結(jié)點(diǎn)的子樹的根（直接后繼） 兄弟兄弟-同一雙親下的同一層結(jié)點(diǎn)（孩子之間互稱兄弟）同一雙親下的同一層結(jié)點(diǎn)（孩子之間互稱兄弟）堂兄弟堂兄弟-雙親位于同一

5、層的結(jié)點(diǎn)（但并非同一雙親）雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親） 祖先祖先-從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn) 子孫子孫-該結(jié)點(diǎn)下層子樹的任一結(jié)點(diǎn)該結(jié)點(diǎn)下層子樹的任一結(jié)點(diǎn)6.1 樹的定義和基本術(shù)語(yǔ)10ABCDJEFG HIKLM 結(jié)點(diǎn)結(jié)點(diǎn)-樹中的數(shù)據(jù)元素樹中的數(shù)據(jù)元素 結(jié)點(diǎn)的度結(jié)點(diǎn)的度-結(jié)點(diǎn)擁有的子樹的數(shù)目結(jié)點(diǎn)擁有的子樹的數(shù)目（有幾個(gè)直接后繼度就是幾）（有幾個(gè)直接后繼度就是幾）結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次-從根到該結(jié)點(diǎn)的層數(shù)從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）（根結(jié)點(diǎn)算第一層） 葉子葉子-度為度為0 0的點(diǎn)（終端結(jié)點(diǎn)）的點(diǎn)（終端結(jié)點(diǎn)） 分支結(jié)點(diǎn)分支結(jié)點(diǎn)-度不為度不為0 0的點(diǎn)

6、（非終端結(jié)點(diǎn)）的點(diǎn)（非終端結(jié)點(diǎn)） 樹的度樹的度-所有結(jié)點(diǎn)度中的最大值所有結(jié)點(diǎn)度中的最大值（Max 各結(jié)點(diǎn)的度各結(jié)點(diǎn)的度 ）樹的深度樹的深度-所有結(jié)點(diǎn)中最大的層數(shù)所有結(jié)點(diǎn)中最大的層數(shù)（ Max 各結(jié)點(diǎn)的層次各結(jié)點(diǎn)的層次 ）（或高度）（或高度）6.1 樹的定義和基本術(shù)語(yǔ)11 二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)； 可以證明，所有樹都能轉(zhuǎn)化為唯一對(duì)應(yīng)的二叉樹，不失可以證明，所有樹都能轉(zhuǎn)化為唯一對(duì)應(yīng)的二叉樹，不失一般性。一般性。 1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的性質(zhì)3. 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹12 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存

7、在度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2 2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹和右子樹次序不能顛倒（有序樹）。左子樹和右子樹次序不能顛倒（有序樹）。 具有具有3 3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？普通樹呢？個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？普通樹呢？6.2 二叉樹-定義13 性質(zhì)性質(zhì)1 1：在二叉樹的第在二叉樹的第i i層上至多有層上至多有2 2i-1i-1個(gè)個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)（i0i0）。）。問：第問：第i i層上至少有層上至少有 個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？ 性質(zhì)性質(zhì)2 2：深度為深度為k k的二叉樹至多有的二叉樹至多有2 2k k-1-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k0k0）。）。 性質(zhì)性質(zhì)3 3：對(duì)于任何一棵二

8、叉樹，若度對(duì)于任何一棵二叉樹，若度2 2的結(jié)點(diǎn)數(shù)有的結(jié)點(diǎn)數(shù)有n2n2個(gè)，個(gè)， 葉子結(jié)點(diǎn)數(shù)為葉子結(jié)點(diǎn)數(shù)為n0n0，則，則n0=n2+1n0=n2+1。6.2 二叉樹-性質(zhì)14證明性質(zhì)3：二叉樹中全部結(jié)點(diǎn)數(shù)二叉樹中全部結(jié)點(diǎn)數(shù)n=n0+n1+n2n=n0+n1+n2( (葉子數(shù)葉子數(shù)+ +度度1 1的結(jié)數(shù)的結(jié)數(shù)+ +度為度為2 2的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù)) )又又 二叉樹中全部結(jié)點(diǎn)數(shù)二叉樹中全部結(jié)點(diǎn)數(shù)n=B+1n=B+1( (總分支數(shù)總分支數(shù) + + 根結(jié)點(diǎn)根結(jié)點(diǎn)) )（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前驅(qū)，即一個(gè)分支）（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前驅(qū)，即一個(gè)分支）而而 總分支數(shù)總分支數(shù)B=n1+2n

9、2B=n1+2n2( (度為度為1 1必有必有1 1個(gè)直接后繼，度為個(gè)直接后繼，度為2 2必有必有2 2個(gè)直接后繼個(gè)直接后繼) )三式聯(lián)立可得：三式聯(lián)立可得：n0+n1+n2=n1+2n2+1n0+n1+n2=n1+2n2+1，即，即n0=n2+1n0=n2+16.2 二叉樹-性質(zhì)15滿二叉樹：深度為深度為k且有且有 2k-1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。 特點(diǎn)：特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。 可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。4 48 89 95 51010 11116 61212 13137 71414 15152

10、 23 31 1完全二叉樹：完全二叉樹：深度為深度為k，有，有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為為k的滿二叉樹中編號(hào)從的滿二叉樹中編號(hào)從1至至n 的結(jié)點(diǎn)一一的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。對(duì)應(yīng)時(shí)，稱之為完全二叉樹。特點(diǎn)特點(diǎn): （1）葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)； （2）對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為）對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為h， 則其左分支下的子孫的最大層次數(shù)必為則其左分支下的子孫的最大層次數(shù)必為h或或h+1。4 48 89 95 510106 67 72

11、23 31 16.2 二叉樹-特例1612311458912136710141512311458912671012345671234566.2 二叉樹-特例17對(duì)于特殊性質(zhì)的二叉樹，還具備以下2個(gè)性質(zhì)：性質(zhì)性質(zhì)4 4：具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為1。性質(zhì)性質(zhì)5 5：如果對(duì)一棵有如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹個(gè)結(jié)點(diǎn)的完全二叉樹(其深度為其深度為1) 的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i（1in），有：），有： 1）如果）如果i i=1，則結(jié)點(diǎn)，則結(jié)點(diǎn)i i是二叉樹的根，無(wú)雙親；如果是二叉樹的根，無(wú)雙親；如果i i1， 則其雙親

12、則其雙親parent（i i）是結(jié)點(diǎn)）是結(jié)點(diǎn) i/2 ； 2）如果）如果2i in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無(wú)左孩子無(wú)左孩子(結(jié)點(diǎn)結(jié)點(diǎn)i i為葉子結(jié)點(diǎn)為葉子結(jié)點(diǎn))；否則其；否則其 左孩子左孩子lchild（i i）是結(jié)點(diǎn)）是結(jié)點(diǎn)2i i； 3）如果）如果2i i+1n，則結(jié)點(diǎn)，則結(jié)點(diǎn)i i無(wú)右孩子；否則其右孩子無(wú)右孩子；否則其右孩子rchild(i)i) 是結(jié)點(diǎn)是結(jié)點(diǎn)2i i+1。4 48 89 95 510106 67 72 23 31 16.2 二叉樹-性質(zhì)18一、順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)二次自上而下、自左至右存儲(chǔ)二叉樹上的結(jié)點(diǎn)元素。

13、叉樹上的結(jié)點(diǎn)元素。DHIEFGBCA0123456789ABCDEFGHIDFEBCA0123456789ABCDE0000F僅適合于完全二叉樹僅適合于完全二叉樹對(duì)于非完全二叉樹：對(duì)于非完全二叉樹：將各層空缺處全部補(bǔ)上將各層空缺處全部補(bǔ)上“虛結(jié)點(diǎn)虛結(jié)點(diǎn)”，其內(nèi)容為，其內(nèi)容為0 0缺點(diǎn)：缺點(diǎn)：浪費(fèi)空間；插入、刪除不便浪費(fèi)空間；插入、刪除不便 6.2 二叉樹-存儲(chǔ)結(jié)構(gòu)19二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表二叉鏈表中包含中包含2個(gè)指針域。個(gè)指針域。一般從根結(jié)點(diǎn)開始存儲(chǔ)。一般從根結(jié)點(diǎn)開始存儲(chǔ)。DATAPARENT LCHILD RCHILDlchild data rchild lchild data paren

14、t rchild 為了便于找到結(jié)點(diǎn)的雙親，為了便于找到結(jié)點(diǎn)的雙親，可再增加一個(gè)雙親域指針，可再增加一個(gè)雙親域指針，將二叉鏈表變成將二叉鏈表變成三叉鏈表三叉鏈表。鏈表的鏈表的頭指針頭指針指向二叉樹的根結(jié)點(diǎn)。指向二叉樹的根結(jié)點(diǎn)。6.2 二叉樹-存儲(chǔ)結(jié)構(gòu)20例：例：CEFDBGAABCDEFG A B C D E F G二叉鏈表三叉鏈表在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域空指針個(gè)數(shù)：空指針個(gè)數(shù)：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+16.2 二叉樹-存儲(chǔ)結(jié)構(gòu)21一、遍歷二叉樹按某條搜索路徑訪問樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被按某條搜索路徑訪問樹中

15、每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。訪問一次，而且僅被訪問一次。 v二叉樹由根、左子樹、右子樹構(gòu)成，三者的組合可構(gòu)成二叉樹由根、左子樹、右子樹構(gòu)成，三者的組合可構(gòu)成6種種 遍歷方案：遍歷方案：根左右、根右左、左根右、左右根、右根左、右左根根左右、根右左、左根右、左右根、右根左、右左根v若若限定限定“先左后右先左后右”，則有，則有3種實(shí)現(xiàn)方案：種實(shí)現(xiàn)方案： 根左右根左右 左根右左根右 左右根左右根先序遍歷 中序遍歷 后序遍歷6.3 遍歷二叉樹和線索二叉樹22DHIFGBCA1、 先序遍歷2、 中序遍歷3、 后序遍歷訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)先序遍歷左子樹先序遍歷左子樹先序遍歷右子樹先

16、序遍歷右子樹A BD CFGH I中序遍歷左子樹中序遍歷左子樹訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)中序遍歷右子樹中序遍歷右子樹DB A FCHGI后序遍歷左子樹后序遍歷左子樹后序遍歷右子樹后序遍歷右子樹訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)DB FHIGC A例1：6.3 遍歷二叉樹和線索二叉樹231、 先序遍歷2、 中序遍歷3、 后序遍歷+* / AB C DEA / B* C*D+EA B / C * D例2：*AB/C*E+D*E+前綴表達(dá)式前綴表達(dá)式中綴表達(dá)式中綴表達(dá)式后綴表達(dá)式后綴表達(dá)式6.3 遍歷二叉樹和線索二叉樹24例：例：已知一棵二叉樹的中序序列和后序序列分別是已知一棵二叉樹的中序序列和后序序列分別是BDCEA

17、FHG 和和 DECBHGFA，請(qǐng)畫出這棵二叉樹。，請(qǐng)畫出這棵二叉樹。討論：若已知若已知先序序列先序序列（或后序序列）和（或后序序列）和中序序列中序序列，能否恢復(fù)，能否恢復(fù) 出對(duì)應(yīng)的二叉樹？出對(duì)應(yīng)的二叉樹？分析：分析：由后序遍歷特征，由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部根結(jié)點(diǎn)必在后序序列尾部（即（即A A）由中序遍歷特征，由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹的子孫子樹的子孫（即（即BDCEBDCE），其右部必全部是右子樹的子孫（即），其右部必全部是右子樹的子孫（即FHGFHG）繼而，根據(jù)后序中的繼而，根據(jù)后序中的DECBDECB子樹

18、可確定子樹可確定B B為為A A的左孩子，根據(jù)的左孩子，根據(jù)HGFHGF子子串可確定串可確定F F為為A A的右孩子；以此類推的右孩子；以此類推6.3 遍歷二叉樹和線索二叉樹25已知中序遍歷：已知中序遍歷：B D C E A F H G已知后序遍歷：已知后序遍歷：D E C B H G F A（B D C E）（ F H G）A （D C E）BFGHCD EAABC6.3 遍歷二叉樹和線索二叉樹26已知先序遍歷序列如下：已知先序遍歷序列如下：ABDCEFABCEFD6.3 遍歷二叉樹和線索二叉樹27二、線索二叉樹普通二叉樹只能找到結(jié)點(diǎn)的左右孩子的信息普通二叉樹只能找到結(jié)點(diǎn)的左右孩子的信息，而

19、該結(jié)點(diǎn)，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來(lái)將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來(lái)，則從第一，則從第一個(gè)結(jié)點(diǎn)開始就能很快地遍歷整個(gè)樹了。個(gè)結(jié)點(diǎn)開始就能很快地遍歷整個(gè)樹了。例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：A/B*C*D+E，實(shí)際上已將二叉樹轉(zhuǎn)為線，實(shí)際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼。性排列，顯然具有唯一前驅(qū)和唯一后繼。如何預(yù)存這類信息呢？增加兩個(gè)域增加兩個(gè)域:前驅(qū)指針、后繼指針前驅(qū)指針、后繼指針利用利用n+1n+1個(gè)空鏈域個(gè)空鏈域6.3 遍歷二叉樹和線索二叉樹28規(guī)定：規(guī)定：1

20、）若結(jié)點(diǎn)有左子樹，則）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則，lchild指向其直接前驅(qū)（即線索）；指向其直接前驅(qū)（即線索）；2）若結(jié)點(diǎn)有右子樹，則）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則，rchild指向其直接后繼（即線索）；指向其直接后繼（即線索）；lchild data rchild約定：約定： 當(dāng)當(dāng)TagTag域?yàn)橛驗(yàn)? 0時(shí)，表示時(shí)，表示孩子孩子情況；情況； 當(dāng)當(dāng)TagTag域?yàn)橛驗(yàn)? 1時(shí)，表示時(shí)，表示線索線索情況。情況。lchild LTag data RTag rchild6.3 遍歷二叉樹和線索二叉樹29有關(guān)線索

21、二叉樹的幾個(gè)術(shù)語(yǔ)：有關(guān)線索二叉樹的幾個(gè)術(shù)語(yǔ)： 線索鏈表：線索鏈表：用上述結(jié)點(diǎn)構(gòu)成的二叉鏈表用上述結(jié)點(diǎn)構(gòu)成的二叉鏈表 線索：線索：指向前驅(qū)和后繼結(jié)點(diǎn)的指針指向前驅(qū)和后繼結(jié)點(diǎn)的指針 線索二叉樹：線索二叉樹：同加上線索的二叉樹（同加上線索的二叉樹（圖形式樣圖形式樣） 線索化：線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程 線索化過程就是在遍歷過程中修改空指針的過程：線索化過程就是在遍歷過程中修改空指針的過程：將空的將空的lchildlchild改為結(jié)點(diǎn)的直接前驅(qū)；改為結(jié)點(diǎn)的直接前驅(qū)；將空的將空的rchildrchild改為結(jié)點(diǎn)的直接后繼。改為結(jié)點(diǎn)

22、的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況正常情況”）6.3 遍歷二叉樹和線索二叉樹30例：畫出下列二叉樹所對(duì)應(yīng)的中序線索二叉樹中序遍歷結(jié)果：中序遍歷結(jié)果：HDIBE A FCGNILNIL6.3 遍歷二叉樹和線索二叉樹31NILNIL 0 1 0 A 0 0 B 0 0 C 0 0 D 0 1 E 1 1 F 1 1 G 1 1 H 1 1 I 1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)6.3 遍歷二叉樹和線索二叉樹中序遍歷結(jié)果：中序遍歷結(jié)果：HDIBE A FCG321. 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)2. 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換3. 樹和森林的遍歷樹和森林

23、的遍歷6.4 樹和森林33一、一、 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)樹有三種常用存儲(chǔ)方式： 雙親表示法雙親表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法1、用雙親表示法來(lái)存儲(chǔ)用一組用一組連續(xù)空間連續(xù)空間來(lái)存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在來(lái)存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器附設(shè)一個(gè)指示器，指示其雙親結(jié)點(diǎn)在，指示其雙親結(jié)點(diǎn)在鏈表中的位置。鏈表中的位置。6.4 樹和森林-樹的存儲(chǔ)34例1：雙親表示法HDEFGBCA雙親表示法缺點(diǎn)：缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)01234567Data Parent A -1 B 0 C 0 D 1 E 1 F 4 G

24、4 H 46.4 樹和森林-樹的存儲(chǔ)352、用孩子表示法來(lái)存儲(chǔ)：將每個(gè)結(jié)點(diǎn)的將每個(gè)結(jié)點(diǎn)的孩子孩子排列起來(lái)，形成一個(gè)排列起來(lái)，形成一個(gè)帶表頭帶表頭（裝父親結(jié)（裝父親結(jié)點(diǎn)）點(diǎn)）的線性表的線性表（n個(gè)結(jié)點(diǎn)要設(shè)立個(gè)結(jié)點(diǎn)要設(shè)立n個(gè)鏈表），再將個(gè)鏈表），再將n個(gè)個(gè)表頭用數(shù)組表頭用數(shù)組存放存放起來(lái)，這樣就形成一個(gè)起來(lái)，這樣就形成一個(gè)混合結(jié)構(gòu)混合結(jié)構(gòu)。HDEFGBCA孩子表示法 B C A D E B C D F G H E F G H 0 01 12 23 34 45 56 67 76.4 樹和森林-樹的存儲(chǔ)36HDEFGBCA帶雙親的孩子表示法Parent Data0 01 12 23 34 45 56

25、67 7ABCDEFGH-10011444 B C D E F G H 6.4 樹和森林-樹的存儲(chǔ)373、用孩子兄弟表示法來(lái)存儲(chǔ)：用用二叉鏈表二叉鏈表來(lái)存儲(chǔ)樹，但鏈表的兩個(gè)指針域含義不同。來(lái)存儲(chǔ)樹，但鏈表的兩個(gè)指針域含義不同。firstchild data nextsibling指向結(jié)點(diǎn)的第一個(gè)孩子指向結(jié)點(diǎn)的第一個(gè)孩子指向結(jié)點(diǎn)的第一個(gè)兄弟指向結(jié)點(diǎn)的第一個(gè)兄弟HDEFGBCA孩子兄弟表示法ABDCEFGH6.4 樹和森林-樹的存儲(chǔ)38二、二、 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換： 結(jié)點(diǎn)的第一孩子做為其左孩子結(jié)點(diǎn)的第一孩子做為其左孩子 結(jié)點(diǎn)的右鄰近兄弟做為其右孩子結(jié)點(diǎn)的右鄰近兄弟做為其右孩子HD

26、EFGBIAC二叉樹1、樹與二叉樹的轉(zhuǎn)換6.4 樹和森林-樹與二叉樹的轉(zhuǎn)換392、二叉樹與樹的轉(zhuǎn)換：把所有右孩子都變成其雙親的兄弟把所有右孩子都變成其雙親的兄弟6.4 樹和森林-樹與二叉樹的轉(zhuǎn)換403、森林與二叉樹的轉(zhuǎn)換： 各樹要先各自轉(zhuǎn)為二叉樹各樹要先各自轉(zhuǎn)為二叉樹 依次連接到前一個(gè)二叉樹的右子樹上依次連接到前一個(gè)二叉樹的右子樹上BDACIGHJEF6.4 樹和森林-森林與二叉樹的轉(zhuǎn)換41三、樹和森林的遍歷三、樹和森林的遍歷1、樹的遍歷v 先序遍歷v 后序遍歷 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 依次先序遍歷根結(jié)點(diǎn)的每棵子樹依次先序遍歷根結(jié)點(diǎn)的每棵子樹 依次后序遍歷根結(jié)點(diǎn)的每棵子樹依次后序遍歷根結(jié)點(diǎn)的每棵

27、子樹 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)DBEACABCD EBDCEA先序：先序：中序：中序：后序：后序：ABCDEBDCEADECBA結(jié)論：結(jié)論：樹后序遍歷相當(dāng)于對(duì)應(yīng)二叉樹的中序遍歷；樹后序遍歷相當(dāng)于對(duì)應(yīng)二叉樹的中序遍歷；樹沒有中序遍歷，因?yàn)樽訕錈o(wú)左右之分。樹沒有中序遍歷，因?yàn)樽訕錈o(wú)左右之分。6.4 樹和森林-樹的遍歷422、森林的遍歷v 先序遍歷v 中序遍歷訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn)先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林中序

28、遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林訪問第一棵樹的根結(jié)點(diǎn)訪問第一棵樹的根結(jié)點(diǎn)中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林BDACIGHJEFABCD E FGH I JBCDAFEHJ IG6.4 樹和森林-森林的遍歷43一、一、 最優(yōu)二叉樹（赫夫曼樹）最優(yōu)二叉樹（赫夫曼樹）路 徑：由一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。路徑長(zhǎng)度：路徑上的分支數(shù)目。樹的路徑長(zhǎng)度：從根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。帶權(quán)路徑長(zhǎng)度：結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)值的乘積。樹的帶權(quán)路徑長(zhǎng)度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。赫夫曼樹：帶權(quán)路徑長(zhǎng)度最小的樹。DEFGBCA6.6 赫夫曼樹

29、及其應(yīng)用44例：例：三棵二叉樹中，三棵二叉樹中，4 4個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)a a、b b、c c、d d分別帶權(quán)分別帶權(quán)7 7、5 5、2 2、4 4，它們的帶權(quán)路徑長(zhǎng)度分別為，它們的帶權(quán)路徑長(zhǎng)度分別為? ? WPL=7 WPL=7* *2+52+5* *2+22+2* *2+42+4* *2=362=36 WPL=7 WPL=7* *3+53+5* *3+23+2* *1+41+4* *2=462=46 WPL=7 WPL=7* *1+51+5* *2+22+2* *3+43+4* *3=353=35abcddabccdba7 77 77 75 55 55 52 22 22 24 44 44

30、 4WPL=WkLk nk=1Weighted Path LengthHuffman樹6.6 赫夫曼樹及其應(yīng)用45二、構(gòu)造赫夫曼樹的基本步驟二、構(gòu)造赫夫曼樹的基本步驟1 1）根據(jù)給定的）根據(jù)給定的n n個(gè)權(quán)值個(gè)權(quán)值1 1，2 2，n n ，構(gòu)成，構(gòu)成n n棵二叉樹的棵二叉樹的集合集合F=TF=T1 1，T T2 2，T Tn n ，其中每棵二叉樹，其中每棵二叉樹T Ti i中只有一個(gè)帶權(quán)為中只有一個(gè)帶權(quán)為i i的根結(jié)點(diǎn)，其左右子樹均空；的根結(jié)點(diǎn)，其左右子樹均空；2 2）在）在F F中中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵樹作為左右子樹構(gòu)造一棵新的二叉樹，且

31、新的二叉樹的新的二叉樹，且新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和結(jié)點(diǎn)的權(quán)值之和；3 3）在）在F F中刪除這兩棵樹，同時(shí)中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入將新得到的二叉樹加入F F中中；4 4）重復(fù)）重復(fù)2 2）和）和3 3），直到），直到F F只含有一棵樹為止。只含有一棵樹為止。6.6 赫夫曼樹及其應(yīng)用46例：例：畫出以畫出以7 7、5 5、2 2、4 4四個(gè)權(quán)值構(gòu)造生成的赫夫曼樹。四個(gè)權(quán)值構(gòu)造生成的赫夫曼樹。7 75 54 42 2步驟步驟2 27 75 5步步驟驟3 37 74 42 26 65 511114 42 26 64 4驟步

32、驟步4 42 26 65 511117 71818步驟步驟1 1一棵有n個(gè)葉子結(jié)點(diǎn)的赫夫曼樹共有2n-1個(gè)結(jié)點(diǎn)。6.6 赫夫曼樹及其應(yīng)用47三、赫夫曼編碼三、赫夫曼編碼設(shè)有電文A B A C C D A 若若0000、0101、1010、1111，則，則00 01 00 10 10 11 0000 01 00 10 10 11 00，總長(zhǎng)，總長(zhǎng)1414位；位； 若若0 0、0000、1 1、0101，則，則0 00 0 1 1 01 00 00 0 1 1 01 0，總長(zhǎng)，總長(zhǎng)9 9位，但譯碼時(shí)位，但譯碼時(shí)產(chǎn)生二意性。產(chǎn)生二意性。 若要設(shè)計(jì)長(zhǎng)短不等的編碼，則必須是任一個(gè)字符的編碼都不是另一個(gè)字

33、符的編碼的前綴，稱為前綴編碼。 6.6 赫夫曼樹及其應(yīng)用48c cd db ba a左分支為左分支為0 0右分支為右分支為1 1HuffmanHuffman編碼的結(jié)果是：編碼的結(jié)果是：a=0a=0b=10b=10c=110c=110d=111d=111由于赫夫曼樹的由于赫夫曼樹的WPLWPL最小，說明編碼所需要的長(zhǎng)度最小。所以，最小，說明編碼所需要的長(zhǎng)度最小。所以，這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。設(shè)計(jì)電文總長(zhǎng)度最短的二進(jìn)制前綴編碼即為設(shè)計(jì)電文總長(zhǎng)度最短的二進(jìn)制前綴編碼即為以以n n種字符出現(xiàn)的頻率種字符出現(xiàn)的頻率作權(quán)值，設(shè)計(jì)一棵赫夫曼樹的問題作權(quán)值，設(shè)計(jì)一棵赫夫

34、曼樹的問題，由此得到的二進(jìn)制前綴編碼，由此得到的二進(jìn)制前綴編碼便稱為赫夫曼編碼。便稱為赫夫曼編碼。6.6 赫夫曼樹及其應(yīng)用49例：例：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.070.07，0.190.19，0.020.02，0.060.06，0.320.32，0.030.03，0.210.21，0.100.10，試設(shè)計(jì)赫夫曼編碼。，試設(shè)計(jì)赫夫曼編碼。解：解：先將概率放大先將概率放大100倍，以方便構(gòu)造赫夫曼樹。倍，以方便構(gòu)造赫夫曼樹。 權(quán)值集合權(quán)值集合w=7，19，2，6，32，3，21，102 23 35 56 6111

35、17 7101017172828323260601919 2121404010010011010.10010.21111110.03100.3211100.06111100.02000.1911000.07編碼頻率6.6 赫夫曼樹及其應(yīng)用50typedef struct int weight；/權(quán)值分量（可放大取整）權(quán)值分量（可放大取整） int parent，lchild，rchild； /雙親和孩子分量雙親和孩子分量HTNode，*HuffmanTree；/用動(dòng)態(tài)數(shù)組存儲(chǔ)用動(dòng)態(tài)數(shù)組存儲(chǔ)Huffman樹樹typedef char*HuffmanCode； /動(dòng)態(tài)數(shù)組存儲(chǔ)動(dòng)態(tài)數(shù)組存儲(chǔ)Huffm

36、an編碼表編碼表1、Huffman樹和樹和Huffman樹編碼的存儲(chǔ)表示：樹編碼的存儲(chǔ)表示：四、如何編程實(shí)現(xiàn)四、如何編程實(shí)現(xiàn)HuffmanHuffman編碼？編碼？參見教材參見教材P147建議建議1 1：HuffmanHuffman樹中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成樹中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成4 4分量形式：分量形式：rchildlchildparentweight建議建議2 2： HuffmanHuffman樹的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)結(jié)構(gòu)：樹的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)結(jié)構(gòu)：將整個(gè)將整個(gè)HuffmanHuffman樹的結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組樹的結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組HT1.n.mHT1.n.m中中; ;各葉子結(jié)點(diǎn)的各葉子

37、結(jié)點(diǎn)的編碼存儲(chǔ)在另一編碼存儲(chǔ)在另一“復(fù)合復(fù)合”數(shù)組數(shù)組HC1.nHC1.n中中指針型指針指針型指針6.6 赫夫曼樹及其應(yīng)用512、先構(gòu)造、先構(gòu)造Huffman樹樹HTVoid HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)if (n=1)return;m=2*n-1; /n 個(gè)葉子的個(gè)葉子的HuffmanTree共有共有2n-1個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)；HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0單元未用單元未用*w存放存放n個(gè)字符的權(quán)值個(gè)字符的權(quán)值for(p=HT,i=1; i

38、=n; +i,+p,+w)*p=*w,0,0,0; /初始化前初始化前n個(gè)單元個(gè)單元for(；i=m; +i,+p) *p =0,0,0,0; /對(duì)葉子之后的存儲(chǔ)單元清零對(duì)葉子之后的存儲(chǔ)單元清零for(i=n+1;i=m; +i) /建建Huffman樹樹(從從葉子開始葉子開始) Select(HT, i-1, s1, s2); /在在HT1i-1選擇選擇parent為為0且且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為S1和和s2 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weigh

39、t=HTs1.weight+ HTs2.weight;6.6 赫夫曼樹及其應(yīng)用523、求出、求出n個(gè)字符的個(gè)字符的Huffman編碼編碼HCHC=(HuffmanCode)malloc(n+1)*sizeof(char*); /分配分配n個(gè)字符編碼的頭指針個(gè)字符編碼的頭指針 向量（一維數(shù)組）向量（一維數(shù)組）cd=(char*) malloc(n*sizeof(char); /分配求編碼的工作空間分配求編碼的工作空間(n) cdn-1=0; /編碼結(jié)束符（從編碼結(jié)束符（從cd0cdn-1為合法空間）為合法空間）for(i=1;i=n;+i) /逐個(gè)字符求逐個(gè)字符求Huffman編碼編碼 star

40、t=n-1; /編碼結(jié)束符位置編碼結(jié)束符位置 for(c=i,f=HTi.parent; f!=0; c=f, f=HTf.parent)/從葉子到根逆向求編碼從葉子到根逆向求編碼if(HTf.lchild=c) cd-start=0;else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char);/為第為第i個(gè)字符編碼分配空間個(gè)字符編碼分配空間 strcpy(HCi,&cdstart); /從從cd復(fù)制編碼串到復(fù)制編碼串到HCfree(cd); /釋放工作空間釋放工作空間 6.6 赫夫曼樹及其應(yīng)用53存儲(chǔ)結(jié)構(gòu)遍歷先序遍歷后序遍歷雙親表示法孩子

41、表示法孩子兄弟法先 中序 序遍 遍歷 歷1、定義和性質(zhì)2、存儲(chǔ)結(jié)構(gòu)3、遍歷4、線索化順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)先序遍歷中序遍歷后序遍歷先序線索樹中序線索樹后序線索樹赫夫曼樹赫夫曼編碼小結(jié)小結(jié)54已知一棵樹的集合為, , , , , , , , , , , ，請(qǐng)畫出這棵樹，并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)G的雙親？（4）哪些是結(jié)點(diǎn)G的祖先？（5）哪些是結(jié)點(diǎn)G的孩子？（6）哪些是結(jié)點(diǎn)E的子孫？（7）哪些是結(jié)點(diǎn)E的兄弟？哪些是結(jié)點(diǎn)F的兄弟？（8）結(jié)點(diǎn)B和N的層次號(hào)分別是什么？（9）樹的深度是多少？（10）以C為根的子樹的深度是多少？課堂練習(xí)(一)55k1k2k3k4k

42、7k5k6一、對(duì)照右圖回答下列問題：一、對(duì)照右圖回答下列問題： 1、這棵樹的根結(jié)點(diǎn)？ 2、這棵樹的葉子結(jié)點(diǎn)？ 3、結(jié)點(diǎn)k3的度？ 4、這棵樹的度？ 5、這棵樹的深度？ 6、結(jié)點(diǎn)k1的孩子結(jié)點(diǎn)？ 7、結(jié)點(diǎn)k3的雙親結(jié)點(diǎn)？ 8、以k3為根的子樹的深度？二、已知樹的集合為二、已知樹的集合為,，分別用圖形表示，分別用圖形表示法、廣義表表示法、嵌套表示法、凹入表示法畫出這棵樹。法、廣義表表示法、嵌套表示法、凹入表示法畫出這棵樹。課堂練習(xí)(一)561. 設(shè)T是一棵完全二叉樹, 則T的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)n與右子樹的結(jié)點(diǎn)數(shù)n的大小關(guān)系是 。2. 一棵深度為6的滿二叉樹有 個(gè)葉子和 個(gè)分支結(jié)點(diǎn)。3. 設(shè)一棵

43、完全二叉樹具有36個(gè)結(jié)點(diǎn)，則此完全二叉樹有 個(gè)葉子結(jié)點(diǎn)，有 個(gè)度為2的結(jié)點(diǎn)，有 個(gè)結(jié)點(diǎn)只有非空左子樹，有 個(gè)結(jié)點(diǎn)只有非空右子樹。4. 一棵滿k叉樹上的葉子結(jié)點(diǎn)數(shù)n0和非葉子結(jié)點(diǎn)數(shù)n1之間滿足以下關(guān)系：n0 = ( k-1)* n1 + 1 5.一棵二叉樹若采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組T中，如下圖所示，請(qǐng)畫出該二叉樹的二叉鏈表存儲(chǔ)形式。1234567891011121314151617181920e a fdgc jh ib課堂練習(xí)(二)571. 設(shè)T是具有3個(gè)結(jié)點(diǎn)的二叉樹，且T的后序序列與中序序列相同，則T的形態(tài)為 。 A B C D2. 對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹為 。 A. 一

44、般二叉樹 B. 只有根結(jié)點(diǎn)的二叉樹 C. 根結(jié)點(diǎn)無(wú)左孩子的二叉樹 D. 根結(jié)點(diǎn)無(wú)右孩子的二叉樹3. 設(shè)n、m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷中，n在m前的條件是 。 A. n在m的右面 B. n是m的祖先 C. n在m的左面 D. n在m的子孫課堂練習(xí)(三)58-+/a*b-efcd4、寫出下列二叉樹的先序、中序和后序遍歷序列，并畫出其后序線索二叉樹。5、某二叉樹前序遍歷序列是ABDGCEFH， 中序遍歷序列是DGBAECHF，請(qǐng)寫出其后序遍歷結(jié)果。課堂練習(xí)(三)59ABCDEFGHIJKLMNO1、寫出下列樹的先序和后序遍歷序列，并將其轉(zhuǎn)換為相應(yīng)的二叉樹。課堂練習(xí)(四)602、把如圖所示

45、的森林轉(zhuǎn)換成二叉樹。課堂練習(xí)(四)613、把如圖所示的二叉樹轉(zhuǎn)換成森林。課堂練習(xí)(四)622、已知某字符串、已知某字符串S中共有中共有8種字符，各種字符分別種字符，各種字符分別出現(xiàn)出現(xiàn)2次、次、1次、次、4次、次、5次、次、7次、次、3次、次、4次和次和9次，次，對(duì)該字符串用對(duì)該字符串用0、1進(jìn)行前綴編碼。進(jìn)行前綴編碼。1、對(duì)給定的一組值、對(duì)給定的一組值5，2，9，11，8，3，7構(gòu)造赫構(gòu)造赫夫曼樹，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。夫曼樹，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。課堂練習(xí)(五)631 在任何非空二叉樹中，葉子結(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)+1，即n0=n2+1。 ( )2 在線索二叉樹中，根據(jù)線索可以找到樹

46、中任何一個(gè)結(jié)點(diǎn)在相應(yīng)遍歷序列中的直接前驅(qū)。( )3 在非空完全二叉樹中，若一個(gè)結(jié)點(diǎn)不存在左孩子，則該結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。( )4 在非空完全二叉樹中，若一個(gè)結(jié)點(diǎn)不存在右孩子，則該結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。( )5在一棵完全二叉樹中，對(duì)任一結(jié)點(diǎn)而言，若其左孩子不存在，則右孩子一定不存在。( )課堂練習(xí)641不含任何結(jié)點(diǎn)的空樹 。 （）是一棵樹; （）是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹 2二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。 它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); 它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ); 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ); 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 3. 具有n(n

47、0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。 () log2(n) () log2(n) () log2(n) +1 () log2(n)+1 4把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。 唯一的 有多種 有多種，但根結(jié)點(diǎn)都沒有左孩子 有多種，但根結(jié)點(diǎn)都沒有右孩子 課堂練習(xí)655. 樹是結(jié)點(diǎn)的有限集合，它 A 根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m0）個(gè) B 的集合T1，T2，Tm，每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1im）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 C 。供選擇的答案A：有0個(gè)或1個(gè) 有0個(gè)或多個(gè) 有且只有1個(gè) 有1個(gè)或1個(gè)以上 B: 互不相交 允許相交 允許

48、葉結(jié)點(diǎn)相交 允許樹枝結(jié)點(diǎn)相交C： 權(quán) 維數(shù) 度 序6. 在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒有 A ，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個(gè)結(jié)點(diǎn)N的左孩子是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)的 B ，而N的右子女是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)的 C 。A: 左結(jié)點(diǎn) 右結(jié)點(diǎn) 左結(jié)點(diǎn)或者沒有右結(jié)點(diǎn) 兄弟BC： 最左結(jié)點(diǎn) 最右結(jié)點(diǎn) 最鄰近的右兄弟 最鄰近的左兄弟 最左的兄弟 最右的兄弟課堂練習(xí)661.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。 2. 給定某二叉樹的中序序列為B R X S A C U Y V，后序序列為 B R S X C U V Y A，試畫出

49、該二叉樹的結(jié)構(gòu)圖。作業(yè)(一)673. 對(duì)所示二叉樹進(jìn)行后序線索化。作業(yè)(一)684. 將下列二叉鏈表改為先序線索鏈表。ABCDEFGHIJKLMNLtagLchild24607010012130000RtagRchild35008911000140001234 5 6 7 8 91011121314作業(yè)(一)69abcdefhgi1.寫出如圖所示樹的三種存儲(chǔ)結(jié)構(gòu)。作業(yè)(二)702、把如圖所示的樹轉(zhuǎn)換成二叉樹。課堂練習(xí)(四)713.把如圖所示的森林分別轉(zhuǎn)換成二叉樹。116718352491013141512作業(yè)(二)724.把如圖所示的二叉樹分別轉(zhuǎn)換成樹或森林。AABCABCBCADBCAEFIHLGKJ作業(yè)(二)731、設(shè)給定權(quán)值2，3，4，7，8，9，試構(gòu)造一棵赫夫曼樹，并求其加權(quán)路徑長(zhǎng)度WPL。2、已知某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。作業(yè)(三)74教學(xué)要求：教學(xué)要求：1 1、了解樹和森林的概念。包括樹的定義、樹的術(shù)語(yǔ)和性質(zhì)；、了解樹和森林的概念。包括樹的定義、樹的術(shù)語(yǔ)和性質(zhì)；2 2、熟練掌握二叉樹的結(jié)構(gòu)特性、遍歷方法，熟悉二叉樹的各、熟練掌握二叉樹的結(jié)構(gòu)特性、遍歷方法，熟悉二叉樹的各 種存儲(chǔ)結(jié)構(gòu)；種存儲(chǔ)結(jié)構(gòu)；3 3、熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹、森林與二叉樹、