數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第6章 樹(shù)和二叉樹(shù)

第6章樹(shù)和二叉樹(shù)請(qǐng)?jiān)O(shè)計(jì)一種存儲(chǔ)方法，能便捷地找到每個(gè)文件所在的存儲(chǔ)路徑。即要求輸入某個(gè)文件名稱后，顯示該文件在U盤中的存儲(chǔ)路徑，若U盤中無(wú)該文件，則顯示“文件未找到”。導(dǎo)學(xué)問(wèn)題1：查找U盤中文件的存儲(chǔ)路徑已知算術(shù)表達(dá)式6+(7-3)/2對(duì)應(yīng)的表達(dá)式樹(shù)如圖所示：請(qǐng)求出該表達(dá)式的值。導(dǎo)學(xué)問(wèn)題2：表達(dá)式樹(shù)中的算術(shù)表達(dá)式求值(a)一棵樹(shù)結(jié)構(gòu)(b)一個(gè)非樹(shù)結(jié)構(gòu)(c)一個(gè)非樹(shù)結(jié)構(gòu)ACBGFEDHIACBGFDACBGFDE6.1知識(shí)學(xué)習(xí)6.1.1樹(shù)樹(shù)的定義樹(shù)：n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí)，稱為空樹(shù)；任意一棵非空樹(shù)滿足以下條件：⑴有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；⑵當(dāng)n＞1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的有限集合T1,T2,…,Tm，其中每個(gè)集合又是一棵樹(shù)，并稱為這個(gè)根結(jié)點(diǎn)的子樹(shù)。樹(shù)的定義是采用遞歸方法6.1.1樹(shù)樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。樹(shù)的度：樹(shù)中各結(jié)點(diǎn)度的最大值。6.1.1樹(shù)樹(shù)的基本術(shù)語(yǔ)孩子、雙親：樹(shù)中某結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。

6.1.1樹(shù)樹(shù)的基本術(shù)語(yǔ)路徑：如果樹(shù)的結(jié)點(diǎn)序列n1,n2,…,nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親（1<=i<k），則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱為路徑長(zhǎng)度。6.1.1樹(shù)樹(shù)的基本術(shù)語(yǔ)祖先、子孫：在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，而y稱為x的子孫。6.1.1樹(shù)樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第i層，則其孩子結(jié)點(diǎn)在第i+1層。樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。6.1.1樹(shù)樹(shù)的基本術(shù)語(yǔ)有序樹(shù)、無(wú)序樹(shù)：如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，稱這棵樹(shù)為有序樹(shù)；反之，稱為無(wú)序樹(shù)。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹(shù)6.1.1樹(shù)樹(shù)的基本術(shù)語(yǔ)森林：m(m≥0)棵互不相交的樹(shù)的集合。6.1.1樹(shù)樹(shù)結(jié)構(gòu)和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素根結(jié)點(diǎn)（只有一個(gè)）無(wú)前驅(qū)無(wú)雙親最后一個(gè)數(shù)據(jù)元素葉子結(jié)點(diǎn)(可以有多個(gè))無(wú)后繼無(wú)孩子其它數(shù)據(jù)元素其它結(jié)點(diǎn)一個(gè)前驅(qū),一個(gè)后繼一個(gè)雙親,多個(gè)孩子一對(duì)一一對(duì)多6.1.1樹(shù)樹(shù)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)樹(shù)的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵是什么?如何表示樹(shù)中結(jié)點(diǎn)之間的邏輯關(guān)系。存儲(chǔ)問(wèn)題的出發(fā)點(diǎn)如何表示結(jié)點(diǎn)的雙親和孩子6.1.1樹(shù)1）多叉鏈表表示法二叉樹(shù)的二叉鏈表結(jié)構(gòu)采用兩個(gè)指針域存儲(chǔ)結(jié)點(diǎn)可能有的孩子指針。樹(shù)的多叉鏈表表示法延伸了這種結(jié)構(gòu)設(shè)計(jì)：若樹(shù)的度為K，則在結(jié)點(diǎn)結(jié)構(gòu)中設(shè)置K個(gè)孩子指針域，使所有結(jié)點(diǎn)同構(gòu)。

6.1.1樹(shù)2）雙親表示法以一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，在每個(gè)結(jié)點(diǎn)中設(shè)一個(gè)指示器指示雙親結(jié)點(diǎn)的位置。6.1.1樹(shù)3）孩子鏈表表示法每個(gè)結(jié)點(diǎn)的孩子以單鏈表的形式存儲(chǔ)，n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，n個(gè)頭指針又組成一個(gè)線性表，并以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。6.1.1樹(shù)4）孩子兄弟表示法以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)的兩個(gè)指針?lè)謩e指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。研究二叉樹(shù)的意義？二叉樹(shù)的結(jié)構(gòu)相對(duì)簡(jiǎn)單，其運(yùn)算也自然簡(jiǎn)單，便于初學(xué)者入門。由于多叉樹(shù)可以借助一定的規(guī)則轉(zhuǎn)換為二叉樹(shù)，因此二叉樹(shù)結(jié)構(gòu)在應(yīng)用中具有非常重要的地位。

6.1.2二叉樹(shù)二叉樹(shù)的定義二叉樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹(shù)），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。6.1.2二叉樹(shù)二叉樹(shù)的特點(diǎn)每個(gè)結(jié)點(diǎn)的度只可能是0，1，2；二叉樹(shù)是有序樹(shù)，即使某結(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分該子樹(shù)是左子樹(shù)還是右子樹(shù)。

6.1.2二叉樹(shù)二叉樹(shù)的5種基本形態(tài)7.2二叉樹(shù)的概念和性質(zhì)例：畫出具有3個(gè)結(jié)點(diǎn)的樹(shù)和具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)的形態(tài)二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu)。6.1.2二叉樹(shù)性質(zhì)1

：二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。推廣：深度為h的k叉樹(shù)中，第i層上最多具有ki－1個(gè)結(jié)點(diǎn)。6.1.2二叉樹(shù)性質(zhì)2：一棵深度為k的二叉樹(shù)中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)一定是滿二叉樹(shù)，深度為k且具有k個(gè)結(jié)點(diǎn)的二叉樹(shù)不一定是斜樹(shù)。

6.1.2二叉樹(shù)性質(zhì)3：在一棵二叉樹(shù)中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1。

證明:抓住結(jié)點(diǎn)總數(shù)=結(jié)點(diǎn)總度數(shù)+1

n0+n1+n2=n1+2*n2+1n0=n2+1推廣：已知一棵樹(shù)度為m的樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少片葉子？證明：根據(jù)結(jié)點(diǎn)總數(shù)=結(jié)點(diǎn)總度數(shù)+1n0+n1+n2+…+nm=n1+2*n2+…+m*nm+1=>n0=1+n2+…+(m-1)nm6.1.2二叉樹(shù)特殊的二叉樹(shù)滿二叉樹(shù)在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上。滿二叉樹(shù)的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。6.1.2二叉樹(shù)不是滿二叉樹(shù)，雖然所有分支結(jié)點(diǎn)都有左右子樹(shù)，但葉子不在同一層上。滿二叉樹(shù)在同樣深度的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹(shù)在同樣深度的二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89特殊的二叉樹(shù)完全二叉樹(shù)對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同。6.1.2二叉樹(shù)在滿二叉樹(shù)中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹(shù)。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹(shù)，結(jié)點(diǎn)10與滿二叉樹(shù)中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)完全二叉樹(shù)的特點(diǎn)1.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的左部；2.完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。3.深度為k的完全二叉樹(shù)在k-1層上一定是滿二叉樹(shù)。CDEFGHIJ例：在有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)中，有多少個(gè)葉子結(jié)點(diǎn)？因?yàn)樵跐M二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，只有度為0的葉子結(jié)點(diǎn)和度為2的分支結(jié)點(diǎn)，所以，n＝n0+n2

n0＝n2+1

即葉子結(jié)點(diǎn)n0＝(n+1)/26.1.2二叉樹(shù)任一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，有m個(gè)葉子結(jié)點(diǎn)，則非葉子結(jié)點(diǎn)數(shù)（度為2）有多少個(gè)？因?yàn)閚0＝n2+1

n2＝n0–1

n2＝m-16.1.2二叉樹(shù)證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k，根據(jù)完全二叉樹(shù)的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)6.1.2二叉樹(shù)性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。

log2n+1[log2n]log2n[log2n]+1k所在區(qū)間證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k，根據(jù)完全二叉樹(shù)的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。

對(duì)不等式取對(duì)數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1。6.1.2二叉樹(shù)性質(zhì)5對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào)，則對(duì)于任意的序號(hào)為i（1≤i≤n）的結(jié)點(diǎn)（簡(jiǎn)稱為結(jié)點(diǎn)i），有：(1)如果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為

i/2；如果i＝1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)。(2)如果2i≤n，則結(jié)點(diǎn)i的左孩子的序號(hào)為2i；

如果2i＞n，則結(jié)點(diǎn)i無(wú)左孩子。(3)如果2i＋1≤n，則結(jié)點(diǎn)i的右孩子的序號(hào)為2i＋1

如果2i＋1＞n，則結(jié)點(diǎn)i無(wú)右孩子。

6.1.2二叉一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào)，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為

i/2；結(jié)點(diǎn)i的左孩子為2i；結(jié)點(diǎn)i的右孩子為2i＋1。

性質(zhì)5表明，在完全二叉樹(shù)中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。6.1.2二叉樹(shù)6.1.2二叉樹(shù)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系——父子關(guān)系。如何利用數(shù)組下標(biāo)來(lái)反映結(jié)點(diǎn)之間的邏輯關(guān)系?二叉樹(shù)的性質(zhì)5為二叉樹(shù)的順序存儲(chǔ)指明了存儲(chǔ)規(guī)則：依照完全二叉樹(shù)的結(jié)點(diǎn)編號(hào)次序，依次存放各個(gè)結(jié)點(diǎn)。注意：C/C++中數(shù)組的起始地址為0，編號(hào)為i的結(jié)點(diǎn)存儲(chǔ)在下標(biāo)為i

1的單元內(nèi)。完全二叉樹(shù)和滿二叉樹(shù)中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系。6.1.2二叉樹(shù)6.1.2二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，可以直接存取二叉樹(shù)中的任意數(shù)據(jù)元素。由于每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置暗藏彼此之間的關(guān)系，可以根據(jù)結(jié)點(diǎn)的編號(hào)，直接計(jì)算出它的父結(jié)點(diǎn)、左/右孩子結(jié)點(diǎn)的位置。類似地，結(jié)點(diǎn)的查找、統(tǒng)計(jì)，結(jié)點(diǎn)路徑的識(shí)別，都能非常便捷地計(jì)算出來(lái)。對(duì)于滿二叉樹(shù)、完全二叉樹(shù)來(lái)說(shuō)，順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)效率極高，所有的空間僅僅用來(lái)存儲(chǔ)數(shù)據(jù)元素的值，結(jié)點(diǎn)之間關(guān)系的存儲(chǔ)未占用任何空間。6.1.2二叉樹(shù)對(duì)于一般二叉樹(shù)而言，如何利用完全二叉樹(shù)的編碼規(guī)則來(lái)存儲(chǔ)數(shù)據(jù)呢？方法是補(bǔ)足不存在的結(jié)點(diǎn)，用特殊數(shù)據(jù)標(biāo)識(shí)這些替補(bǔ)結(jié)點(diǎn)，使整棵樹(shù)在形式上滿足完全二叉樹(shù)的定義。

ABC∧DE∧∧∧F∧∧G數(shù)組下標(biāo)12345678910111213ABCDEGF以編號(hào)為下標(biāo)ABCDEGF123561013按照完全二叉樹(shù)編號(hào)6.1.2二叉樹(shù)一棵斜樹(shù)的順序存儲(chǔ)會(huì)怎樣呢？深度為k的右斜樹(shù)，k個(gè)結(jié)點(diǎn)需分配2k－1個(gè)存儲(chǔ)單元。

一棵二叉樹(shù)改造后成完全二叉樹(shù)形態(tài)，需增加很多空結(jié)點(diǎn)，造成存儲(chǔ)空間的浪費(fèi)。二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹(shù)ABC137D156.1.2二叉樹(shù)6.1.2二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)基本思想：令二叉樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)除了存放與二叉樹(shù)結(jié)點(diǎn)有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針。結(jié)點(diǎn)結(jié)構(gòu)：

lchild

data

rchild其中，data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；lchild：左指針域，存放指向左孩子的指針；rchild：右指針域，存放指向右孩子的指針。

typedefstructBiTNode{ ElemTypedata; structBiTNode*lchild,*rchild;}*BiTree;lchild

datarchild左孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)二叉鏈表結(jié)構(gòu)定義GFEDBAABCDEFG∧∧∧∧∧∧∧∧C具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有多少個(gè)空指針？6.1.2二叉樹(shù)GFEDBAABCDEFG∧∧∧∧∧∧∧∧C具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針。6.1.2二叉樹(shù)6.1.2二叉樹(shù)二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。二叉樹(shù)遍歷操作的結(jié)果？非線性結(jié)構(gòu)線性化抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。先序遍歷中序遍歷后序遍歷層序遍歷

如果限定先左后右，則二叉樹(shù)遍歷方式有三種：先序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹(shù)的層序編號(hào)的次序訪問(wèn)各結(jié)點(diǎn)。

考慮二叉樹(shù)的組成：根結(jié)點(diǎn)D左子樹(shù)L右子樹(shù)R二叉樹(shù)6.1.2二叉樹(shù)先序遍歷的概念①若二叉樹(shù)為空，則空操作返回；（否則）②訪問(wèn)根結(jié)點(diǎn)；③先序遍歷根結(jié)點(diǎn)的左子樹(shù)；④先序遍歷根結(jié)點(diǎn)的右子樹(shù)。先序遍歷序列：ABDGCEFABCDEFG6.1.2二叉樹(shù)先序遍歷——遞歸算法voidPreorder(BiTreeT){if(T)

{

cout<<T->data<<"";Preorder(T->lchild);Preorder(T->rchild);}}中序遍歷的概念①若二叉樹(shù)為空，則空操作返回；（否則）②中序遍歷根結(jié)點(diǎn)的左子樹(shù)；③訪問(wèn)根結(jié)點(diǎn)；④中序遍歷根結(jié)點(diǎn)的右子樹(shù)。

中序遍歷序列：DGBAECFABCDEFG6.1.2二叉樹(shù)中序遍歷——遞歸算法voidInorder(BiTreeT){if(T)

{Inorder(T->lchild);

cout<<T->data<<"";Inorder(T->rchild);}}后序遍歷的概念①若二叉樹(shù)為空，則空操作返回；（否則）②后序遍歷根結(jié)點(diǎn)的左子樹(shù)；③后序遍歷根結(jié)點(diǎn)的右子樹(shù)。④訪問(wèn)根結(jié)點(diǎn)；后序遍歷序列：GDBEFCAABCDEFG6.1.2二叉樹(shù)后序遍歷——遞歸算法voidPostorder(BiTreeT){if(T)

{Postorder(T->lchild);Postorder(T->rchild);

cout<<T->data<<"";}}--/+*abcdef二叉樹(shù)遍歷操作練習(xí)先序遍歷結(jié)果：-+a*b-cd/ef中序遍歷結(jié)果：a+b*c-d-e/f后序遍歷結(jié)果：abcd-*+ef/-6.1.2二叉樹(shù)二叉樹(shù)的建立遍歷是二叉樹(shù)各種操作的基礎(chǔ)，可以在遍歷的過(guò)程中進(jìn)行各種操作，例如建立一棵二叉樹(shù)。如何由一種遍歷序列生成該二叉樹(shù)？為了建立一棵二叉樹(shù)，將二叉樹(shù)中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一特定值如“#”，以標(biāo)識(shí)其為空，把這樣處理后的二叉樹(shù)稱為原二叉樹(shù)的擴(kuò)展二叉樹(shù)。擴(kuò)展二叉樹(shù)的先序遍歷序列：AB#

D##

C##DBAC*DBAC****先序遍歷①若二叉樹(shù)為空，則空操作返回；（否則）②訪問(wèn)根結(jié)點(diǎn)；③先序遍歷根結(jié)點(diǎn)的左子樹(shù)；④先序遍歷根結(jié)點(diǎn)的右子樹(shù)。DBAC先序創(chuàng)建①若輸入為#(空)，則root=NULL（否則）②創(chuàng)建根結(jié)點(diǎn)；③先序創(chuàng)建根結(jié)點(diǎn)的左子樹(shù)；④先序創(chuàng)建根結(jié)點(diǎn)的右子樹(shù)。由帶空指針標(biāo)記的先序序列構(gòu)造二叉樹(shù)的算法

voidCreateBiTree(BiTree&T){charch;cin>>ch;if(ch=='#')T=NULL;else{T=newBiTNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}6.1.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)與二叉樹(shù)的轉(zhuǎn)換樹(shù)轉(zhuǎn)換成二叉樹(shù)二叉樹(shù)轉(zhuǎn)換成樹(shù)森林與二叉樹(shù)的轉(zhuǎn)換森林轉(zhuǎn)換成二叉樹(shù)二叉樹(shù)轉(zhuǎn)換成森林6.2知識(shí)應(yīng)用導(dǎo)學(xué)問(wèn)題1的實(shí)現(xiàn)該問(wèn)題可轉(zhuǎn)換為在二叉樹(shù)中已知葉子結(jié)點(diǎn)，求其雙親結(jié)點(diǎn)，即求從根節(jié)點(diǎn)到該結(jié)點(diǎn)的路徑。將圖6-1中的文件夾和文件抽象成一個(gè)結(jié)點(diǎn)，則圖6-7所示的就是其相應(yīng)的邏輯結(jié)構(gòu)和雙親表示法存儲(chǔ)結(jié)構(gòu)。6.2知識(shí)應(yīng)用導(dǎo)學(xué)問(wèn)題2的實(shí)現(xiàn)為簡(jiǎn)化討論，假設(shè)表達(dá)式中僅有四種雙目操作符：+、-、*、/。顯然，圖6-2所示的表達(dá)式樹(shù)是一棵二叉樹(shù)，其中葉子結(jié)點(diǎn)是操作數(shù)，非葉子結(jié)點(diǎn)是操作符。對(duì)該表達(dá)式樹(shù)進(jìn)行先序、中序和后序遍歷，便可得到表達(dá)式相應(yīng)的前綴、中綴和后綴表示?；诒磉_(dá)式樹(shù)的求值過(guò)程實(shí)際上是一個(gè)后序遍歷的過(guò)程。6.3知識(shí)拓展二叉樹(shù)的其他操作計(jì)算二叉樹(shù)的結(jié)點(diǎn)數(shù)。計(jì)算二叉樹(shù)的結(jié)點(diǎn)總數(shù)等于其左、右子樹(shù)結(jié)點(diǎn)樹(shù)加上1（根結(jié)點(diǎn)），因此可利用后序遍歷框架，將對(duì)整個(gè)二叉樹(shù)結(jié)點(diǎn)進(jìn)行技術(shù)的目標(biāo)分解成對(duì)左、右子樹(shù)的計(jì)數(shù)。6.3知識(shí)拓展二叉樹(shù)的其他操作計(jì)算二叉樹(shù)的高度。二叉樹(shù)中任一結(jié)點(diǎn)的高度是其左、右子樹(shù)高度的最大值加1，而根結(jié)點(diǎn)的高度就是整棵二叉樹(shù)的高度。因此，要計(jì)算根結(jié)點(diǎn)的高度，必須要先求得左、右子樹(shù)的高度，這可以利用后序遍歷實(shí)現(xiàn)。層次遍歷的概念二叉樹(shù)的層次遍歷是指從二叉樹(shù)的第一層（即根結(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。

層序遍歷序列：ABCDEFGABCDEFG6.3知識(shí)拓展層次遍歷ABCDEFG遍歷序列：AABCBDCEFGDEFG6.3知識(shí)拓展①若二叉樹(shù)為空，遍歷結(jié)束。②將根指針加入指針隊(duì)列。③若指針隊(duì)列不空，執(zhí)行步驟④；若指針隊(duì)列為空，則遍歷結(jié)束。④隊(duì)首元素出隊(duì)，記作p，p所指的結(jié)點(diǎn)稱為當(dāng)前結(jié)點(diǎn)，訪問(wèn)當(dāng)前結(jié)點(diǎn)。⑤若當(dāng)前結(jié)點(diǎn)的左孩子指針不空，將左孩子指針入隊(duì)；若當(dāng)前結(jié)點(diǎn)的右孩子指針不空，右孩子指針入隊(duì)。⑥轉(zhuǎn)步驟③。二叉樹(shù)的層次遍歷算法

若已知一棵二叉樹(shù)的先序（或中序，或后序，或?qū)有颍┬蛄校芊裎ㄒ淮_定這棵二叉樹(shù)呢？ABC例：已知先序序列為ABC，則可能的二叉樹(shù)有5種。ABC6.3知識(shí)拓展例：已知先序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹(shù)都滿足條件。ABCABC若已知一棵二叉樹(shù)的先序序列和后序序列，能否唯一確定這棵二叉樹(shù)呢？由兩個(gè)遍歷序列構(gòu)造二叉樹(shù)若已知一棵二叉樹(shù)的先序序列和中序序列，能否唯一確定這棵二叉樹(shù)呢？怎樣確定？

例如：已知一棵二叉樹(shù)的先序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構(gòu)造該二叉樹(shù)呢?

由兩個(gè)遍歷序列構(gòu)造二叉樹(shù)先序：ABCDEFG

HI中序：BCAEDGHFI先序：BC中序：BC

BCDEFGHIA先序：DEFGHI中序：EDGHFIABCDEFGHI先序：FG

HI中序：GHFI先序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH由兩個(gè)遍歷序列構(gòu)造二叉樹(shù)已知一棵二叉樹(shù)的先序序列和中序序列，構(gòu)造該二叉樹(shù)的過(guò)程如下：1.根據(jù)先序序列的第一個(gè)元素建立根結(jié)點(diǎn)；2.在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹(shù)的中序序列；3.在先序序列中確定左右子樹(shù)的先序序列；4.由左子樹(shù)的先序序列和中序序列建立左子樹(shù)；5.由右子樹(shù)的先序序列和中序序列建立右子樹(shù)。BiTreePreInCreate(charpre[],charin[],intipre,intimid,intn){ inti; if(n==0) returnNULL; BiTreep=newBiTNode; //創(chuàng)建根結(jié)點(diǎn) p->data=pre[ipre]; for(i=0;i<n;i++) //在中序序列中查找根結(jié)點(diǎn)位置 if(pre[ipre]==in[imid+i]) break; p->lchild=PreInCreate(pre,in,ipre+1,imid,i); p->rchild=PreInCreate(pre,in,ipre+i+1,imid+i+1,n-i-1); returnp;}根據(jù)關(guān)鍵值查找結(jié)點(diǎn)

BiTreeSearch(BiTreeT,ElemTypex){ BiTreeq; if(T==NULL) returnNULL; if(T->data==x) returnT; q=Search(T->lchild,x); if(q!=NULL)returnq; returnSearch(T->rchild,x); }查找結(jié)點(diǎn)的父結(jié)點(diǎn)BiTreeSearchParent(BiTreeT,BiTreechild){BiTreeq; if(T==NULL||child==NULL) returnNULL;if(T->lchild==child||T->rchild==child) returnT; q=SearchParent(T->lchild,child);if(q!=NULL)returnq; returnSearchParent(T->rchild,child); }6.3知識(shí)拓展——線索二叉樹(shù)在前面討論的二叉樹(shù)各種遍歷算法，其本質(zhì)是將樹(shù)形結(jié)構(gòu)轉(zhuǎn)換為線性序列，便于簡(jiǎn)化問(wèn)題。在遍歷序列中，每個(gè)結(jié)點(diǎn)都有自己的前驅(qū)和后繼，求結(jié)點(diǎn)的前驅(qū)和后繼屬于基本操作?？焖俚貙?shí)現(xiàn)這個(gè)基本操作，對(duì)二叉樹(shù)許多算法的性能有重要意義。最簡(jiǎn)單的方法是在遍歷過(guò)程中尋求答案，缺點(diǎn)是時(shí)間復(fù)雜度等同遍歷算法的時(shí)間復(fù)雜度O(n)，這對(duì)于基本操作而言，顯然效率太低。為了實(shí)現(xiàn)在遍歷序列中快速查找結(jié)點(diǎn)的前驅(qū)、后繼，可以利用二叉鏈表中空的指針域，指向結(jié)點(diǎn)在遍歷序列中的前驅(qū)、后繼，這些指向前驅(qū)和后繼的指針?lè)Q為線索。6.3知識(shí)拓展——線索二叉樹(shù)線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索；線索化：使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過(guò)程稱為線索化；線索二叉樹(shù)：加上線索的二叉樹(shù)稱為線索二叉樹(shù)。

ltype

lchild

data

childrtype0:lchild指向該結(jié)點(diǎn)的左孩子1:lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0:rchild指向該結(jié)點(diǎn)的右孩子1:rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltype=rtype=結(jié)點(diǎn)結(jié)構(gòu)6.3知識(shí)拓展——線索二叉樹(shù)

ltype

lchild

data

rchildrtype結(jié)點(diǎn)結(jié)構(gòu)6.3知識(shí)拓展——線索二叉樹(shù)enumflag{Child,Thread};typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*lchild,*rchild;flagltype,rtype;}*BiThrTree;線索二叉樹(shù)的畫法先序線索二叉樹(shù)：先序序列為：ABCD中序線索二叉樹(shù)：中序序列為：BADC線索二叉樹(shù)的畫法后序線索二叉樹(shù)：后序序列為：BDCA線索二叉樹(shù)的畫法template<classT>classInBiThrTree{ BiThrNode<T>*root;public:

InBiThrTree(){root=NULL;}

InBiThrTree(vector<T>&pre);//根據(jù)pre創(chuàng)建二叉樹(shù)

~InBiThrTree(); voidInThreaded();//中序線索化

BiThrNode<T>*GetNext(BiThrNode<T>*p);//求后繼

BiThrNode<T>*GetPrev(BiThrNode<T>*p);//求前驅(qū)

voidTravese();//中序遍歷private: BiThrNode<T>*CreateByPre(vector<T>&pre,int&i);//僅與InBiThrTree(vector<T>&pre)相關(guān)

voidFree(BiThrNode<T>*p);//僅與析構(gòu)相關(guān)

voidInThreaded(BiThrNode<T>*p,BiThrNode<T>*&pre);//僅與InThreaded()相關(guān)};線索二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)分析：建立線索鏈表，實(shí)質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷該二叉樹(shù)時(shí)才能得到。建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索中序線索鏈表的建立A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)p1中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧pre1p11中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧pre11p11中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000pre11p11中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧00000000000000pre11p1111中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧∧∧00000000000000pre11p1111中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧∧00000000000000pre11p11111中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索A頭指針BCDEFG∧∧00000000000000pre11111111中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)過(guò)的結(jié)點(diǎn)中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索遍歷二叉鏈表，建立線索：①如果二叉鏈表T為空，則空操作返回；②對(duì)T的左子樹(shù)建立線索；③對(duì)T所指結(jié)點(diǎn)建立線索；

若T沒(méi)有左孩子，則為T加上前驅(qū)線索;

若T沒(méi)有右孩子，則將T右標(biāo)志置為1；

若結(jié)點(diǎn)prenode右標(biāo)志為1，則為prenode加上后繼線索；

令prenode指向剛剛訪問(wèn)的結(jié)點(diǎn)T；④對(duì)T的右子樹(shù)建立線索。建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索中序線索鏈表的建立過(guò)程建立二叉鏈表遍歷二叉樹(shù)，將空指針改為線索中序線索鏈表的建立過(guò)程voidInThreaded(BiThrTree&T){ if(T==NULL)//如果二叉鏈表p為空，則空操作返回 return; InThreaded(T->lchild);//線索化左子樹(shù)

if(T->lchild==NULL) //對(duì)p的左指針處理 { T->ltype=Thread; T->lchild=prenode; } if(T->rchild==NULL) //對(duì)p的右指針處理 T->rtype=Thread; if(prenode!=NULL) { if(prenode->rtype==Thread) prenode->rchild=T; } prenode=T;

InThreaded(T->rchild);//線索化右子樹(shù)}中序線索鏈表上查找結(jié)點(diǎn)P的后繼對(duì)于中序線索二叉樹(shù)上的任一結(jié)點(diǎn)，尋找其中序的后繼結(jié)點(diǎn)，有以下兩種情況：1）如果該結(jié)點(diǎn)的右標(biāo)志為1，即無(wú)右孩子，那么其右指針域所指向的結(jié)點(diǎn)便是它的后繼結(jié)點(diǎn)；2）如果該結(jié)點(diǎn)的右標(biāo)志為0，表明該結(jié)點(diǎn)有右孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的子樹(shù)的最左結(jié)點(diǎn)，即沿著其右子樹(shù)的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為1時(shí)，它就是所要找的后繼結(jié)點(diǎn)。

if(p->rtype==Thread)returnp->rchild;p=p->rchild;while(p->ltype==Child)p=p->lchild;中序線索鏈表上查找結(jié)點(diǎn)P的前驅(qū)對(duì)于中序線索二叉樹(shù)上的任一結(jié)點(diǎn)，尋找其中序的前驅(qū)結(jié)點(diǎn)，有以下兩種情況：1）如果該結(jié)點(diǎn)的左標(biāo)志為1，即無(wú)左孩子，那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)；2）如果該結(jié)點(diǎn)的左標(biāo)志為0，即有左孩子，表明該結(jié)點(diǎn)有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的子樹(shù)的最右結(jié)點(diǎn)，即沿著其左子樹(shù)的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí)，它就是所要找的前驅(qū)結(jié)點(diǎn)。if(p->ltype==Thread)returnp->lchild;p=p->lchild;while(p->rtype==Child)p=p->rchild;在中序線索二叉樹(shù)上遍歷利用在中序線索二叉樹(shù)上尋找后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的算法，就可以遍歷到二叉樹(shù)的所有結(jié)點(diǎn)。比如，先找到按某序遍歷的第一個(gè)結(jié)點(diǎn)，然后再依次查詢其后繼；或先找到按某序遍歷的最后一個(gè)結(jié)點(diǎn)，然后再依次查詢其前驅(qū)。這樣，既不用棧也不用遞歸就可以訪問(wèn)到二叉樹(shù)的所有結(jié)點(diǎn)。在中序線索二叉樹(shù)上查找值為x的結(jié)點(diǎn)在中序線索二叉樹(shù)上查找值為x的結(jié)點(diǎn)，實(shí)質(zhì)上就是在線索二叉樹(shù)上進(jìn)行遍歷，將訪問(wèn)結(jié)點(diǎn)的操作具體寫為那結(jié)點(diǎn)的值與x比較的語(yǔ)句。6.3知識(shí)拓展——Huffman樹(shù)與Huffman編碼

信息編碼問(wèn)題假設(shè)給定一個(gè)字符串“ADCBDABDCBDBCDCDCD”，請(qǐng)對(duì)其中字符進(jìn)行編碼，使得該字符串的編碼存儲(chǔ)空間最少，且從存儲(chǔ)空間取出編碼也能還原成唯一的原字符串。Huffman樹(shù)與Huffman編碼

問(wèn)題分析信息編碼是指將信息符號(hào)串轉(zhuǎn)換為編碼文件，其主要目標(biāo)之一是提高信息的存儲(chǔ)效率。存儲(chǔ)效率可以用編碼系統(tǒng)的平均碼長(zhǎng)來(lái)衡量。設(shè)編碼系統(tǒng)中有

個(gè)符號(hào)，每個(gè)符號(hào)的編碼長(zhǎng)度為L(zhǎng)1,L2,…,Ln，各符號(hào)出現(xiàn)的頻率分別是F1,F2,…,Fn，則Huffman樹(shù)與Huffman編碼

問(wèn)題分析信息編碼的方法可分為定長(zhǎng)編碼和不定長(zhǎng)編碼兩大類。定長(zhǎng)編碼是指在編碼系統(tǒng)中，每個(gè)符號(hào)的代碼長(zhǎng)度相等，如常用的ASCII碼，每個(gè)符號(hào)的編碼都是一個(gè)字節(jié)。不定長(zhǎng)編碼應(yīng)用于各種符號(hào)的使用頻率差異較大的場(chǎng)合。其基本思想是利用各種符號(hào)出現(xiàn)的統(tǒng)計(jì)頻率來(lái)編碼，使經(jīng)常出現(xiàn)的符號(hào)的編碼較短，不常出現(xiàn)的符號(hào)的編碼較長(zhǎng)，目的是使信息經(jīng)過(guò)編碼后的編碼文件長(zhǎng)度盡可能短。因此不定長(zhǎng)編碼也稱為統(tǒng)計(jì)編碼。統(tǒng)計(jì)編碼相比定長(zhǎng)編碼不僅節(jié)省磁盤空間，還能起到提高傳遞、運(yùn)算速度的效果。Huffman樹(shù)與Huffman編碼

問(wèn)題分析信息編碼的方法可分為定長(zhǎng)編碼和不定長(zhǎng)編碼兩大類。不定長(zhǎng)編碼的優(yōu)點(diǎn)：存儲(chǔ)效率優(yōu)于定長(zhǎng)編碼的效率。缺點(diǎn)：不定長(zhǎng)編碼由于碼長(zhǎng)不固定，在還原字符時(shí)，存在各符號(hào)的碼串相互混淆的可能。如問(wèn)題中原字符串前兩個(gè)字符為“AD”，用上述不定長(zhǎng)編碼，編碼串為“101”，進(jìn)行還原時(shí)，可以解釋為“AD”也可以解釋為“DB”，因此這樣的編碼方式不能還原成唯一的原字符串。不定長(zhǎng)編碼必須增加約束條件：在同一編碼系統(tǒng)中，任何符號(hào)的編碼不能是另一符號(hào)編碼的前綴。滿足此條件的編碼也被稱為前綴編碼，有效的統(tǒng)計(jì)編碼一定是前綴編碼。Huffman樹(shù)與Huffman編碼

問(wèn)題分析如何設(shè)計(jì)高效率的前綴編碼？1952年正在麻省理工攻讀博士學(xué)位的DavidA.Huffman給出了最優(yōu)解決方案，即Huffman編碼，中文通常寫作哈夫曼編碼。葉子結(jié)點(diǎn)的權(quán)值：對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。二叉樹(shù)的帶權(quán)路徑長(zhǎng)度：設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。

記為：WPL=?=nkkklw1第k個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長(zhǎng)度Huffman樹(shù)

Huffman樹(shù)：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。例：對(duì)于“ADCBDABDCBDBCDCDCD”，4個(gè)葉子結(jié)點(diǎn)ABCD，其權(quán)值分別為{2，4，5，7}，可以構(gòu)造出形狀不同的多個(gè)二叉樹(shù)。WPL=36WPL=46WPL=41245724574527Huffman樹(shù)

圖中有Huffman樹(shù)嗎？如何快速地構(gòu)造一棵Huffman？第1步：初始化W＝{2，4，5，7}Huffman樹(shù)的構(gòu)造過(guò)程7524第2步：選取與合并42

6第3步：刪除與加入7542

6Huffman樹(shù)的構(gòu)造

重復(fù)第2步7542

65

11W＝{2，4，5，7}Huffman樹(shù)的構(gòu)造過(guò)程42

6重復(fù)第3步W＝{2，4，5，7}Huffman樹(shù)的構(gòu)造過(guò)程75

1142

65

1142

67

18重復(fù)第2步Huffman樹(shù)的特點(diǎn)：1.權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2.只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn)。

7524Huffman樹(shù)

Huffman樹(shù)的存儲(chǔ)結(jié)構(gòu)設(shè)置一個(gè)數(shù)組（向量）huffTree[2n-1]保存哈夫曼樹(shù)中各點(diǎn)的信息，數(shù)組（向量）元素的結(jié)點(diǎn)結(jié)構(gòu)。data：編碼值weight：權(quán)值域，保存該結(jié)點(diǎn)的權(quán)值；lchild：指針域，結(jié)點(diǎn)的左孩子結(jié)點(diǎn)在數(shù)組中的下標(biāo)；rchild：指針域，結(jié)點(diǎn)的右孩子結(jié)點(diǎn)在數(shù)組中的下標(biāo)；parent：指針域，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的下標(biāo)。

dataweightlchildrchildparentweightparentlchildrchild-1-1-1-1-1-1-1-1-1-1-1-10123456初態(tài)752424572-1-1-14-1-1