第七章樹和二叉樹

樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，在計算機(jī)科學(xué)中有著廣泛的應(yīng)用。7.1樹的定義和術(shù)語7.1.1樹的定義樹（tree）是n(n≥0)個結(jié)點(diǎn)的有限集。在一棵非空樹中：（1）有且僅有一個特定的結(jié)點(diǎn),稱為根（root）（根結(jié)點(diǎn)無前驅(qū)結(jié)點(diǎn)）;（2）當(dāng)n>1時，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集（T1,T2,…Tm），其中每一集合本身又是一棵樹，并且稱為根的子樹（subtree）。第七章樹和二叉樹樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，在計1舉例例7．1（a）只有根結(jié)點(diǎn)的樹

（b）一般的樹（b）中A為根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成三個互不相交的子集：T1={B，E，F(xiàn)，K，L}，T2={C，G}，T3={D，H，I，J}而T1，T2，T3本身又都是只有一個根結(jié)點(diǎn)的樹。ALKEFGHIJDCBAM舉例例7．1（a）只有根結(jié)點(diǎn)的樹ALKE27.1.2基本術(shù)語：（1）結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向其子樹的分支（2）結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有子樹數(shù)目稱為結(jié)點(diǎn)的度。如圖7-1-1的（b）中，A的度為3；C的度為1；M的度為0。（3）葉子（或終端）結(jié)點(diǎn)：度為零的結(jié)點(diǎn)。（4）分支結(jié)點(diǎn)（或非終端結(jié)點(diǎn)）：除根結(jié)點(diǎn)外度不為零的結(jié)點(diǎn)，也稱為內(nèi)部結(jié)點(diǎn)。（5）樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。（6）孩子：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子。如圖7-1-1的（b）中，D為A的子樹T3的根，則D是A的孩子。（7）雙親：和孩子定義相應(yīng)地該結(jié)點(diǎn)稱為孩子的雙親。如圖7-1-1的（b）中，A為D的雙親。7.1.2基本術(shù)語：3（8）兄弟：同一個雙親的孩子之間互稱兄弟。如圖7-1-1的（b）中的H，I，J。（9）祖先：從根到該結(jié)點(diǎn)所經(jīng)過分支上的所有結(jié)點(diǎn)。如：M的祖先為A，D，H（10）子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。如圖7-1-1的（b）中B的子孫為E，F(xiàn)，K，L（11）層次：從根開始定義為第一層，根的孩子為第二層，依次例推。（12）深度（或高度）：樹中結(jié)點(diǎn)的最大層次。（13）有序樹：將樹中結(jié)點(diǎn)的各子樹看成從左到右是有序的。有序樹中最左邊的子樹的根稱第一個孩子，最右邊的稱為最后一個孩子。（14）無序樹：樹中結(jié)點(diǎn)的各子樹沒有次序的。（15）森林：是m(m≥0)棵互不相交的樹的集合，對樹中每個結(jié)點(diǎn)而言，其子樹的集合即為森林。（8）兄弟：同一個雙親的孩子之間互稱兄弟。如圖7-1-1的（4該樹的根結(jié)點(diǎn)為：a，分支結(jié)點(diǎn)為：b、c、e；葉子結(jié)點(diǎn)為d、f、g、h、i、j；該樹的度為3，高度為4；第一層有結(jié)點(diǎn)：a，第二層有結(jié)點(diǎn)：b、c；第三層有結(jié)點(diǎn)d、e、f、g、h，第四層有結(jié)點(diǎn)：i、j。abcdeigjhf該樹的根結(jié)點(diǎn)為：a，分支結(jié)點(diǎn)為：b、c、e；葉子結(jié)點(diǎn)為d、f57.2二叉樹7.2.1二叉樹的定義和性質(zhì)：1、定義：二叉樹是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且二叉樹的子樹有左右之分，其次序不能任意顛倒。2、如圖所示二叉樹的五種基本形態(tài)（a）(b)(c)(d)(e)7.2二叉樹7.2.1二叉樹的定義和性質(zhì)：67.2.2二叉樹的性質(zhì)

(1)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)（i≥1）。(2)性質(zhì)2：深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為2k-1(k≥1)。(3)性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1（4）一棵深度為k且有2k-1個結(jié)點(diǎn)的二叉樹稱滿二叉樹。特點(diǎn)：每層上的結(jié)點(diǎn)數(shù)都為最大結(jié)點(diǎn)數(shù)，除終端結(jié)點(diǎn)外，每個結(jié)點(diǎn)都有兩棵子樹。（5）完全二叉樹：如深度為k，有N個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到N的結(jié)點(diǎn)一一對時，稱之為完全二叉樹。特點(diǎn)：深度為k的完全二叉樹，其前k-1層是一棵滿二叉樹，最后第k層結(jié)點(diǎn)都盡量排在靠左的位置上。顯然一棵滿二叉樹一定是完全二叉樹，但一棵完全二叉樹不一定是滿二叉樹。7.2.2二叉樹的性質(zhì)7（6）完全二叉樹的兩個特性：性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為└Log2n┘+1。性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹（其深度為└Log2n┘+1）的結(jié)點(diǎn)按順序編號，則任一結(jié)點(diǎn)i(1≤i≤n)有：①若i=1,則結(jié)點(diǎn)i是二叉樹的根結(jié)點(diǎn)，若i>1，則i的雙親結(jié)點(diǎn)為結(jié)點(diǎn)┗i/2┛;②若2i≤n，則i的左孩子是結(jié)點(diǎn)2i，否則無左孩子；③若2i+1≤n，則i的右孩子是結(jié)點(diǎn)2i+1,否則無右孩子。（6）完全二叉樹的兩個特性：87.2.3二叉樹的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素，按滿二叉樹的結(jié)點(diǎn)順序編號依次存放二叉樹中數(shù)據(jù)元素。

012345

T(6)圖7-3完全二叉樹ABCDEFABCDEF7.2.3二叉樹的存儲結(jié)構(gòu)ABCDEFABCDEF9數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件102.鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈表的結(jié)點(diǎn)至少包含：數(shù)據(jù)域和左右指針域的鏈有時還需增一指向雙親的指針域，有兩個指針域的鏈表稱為二叉鏈表，有三個指針域的鏈表稱為三叉鏈表，如圖5-5所示：

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)11數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件12例7-3分別畫出二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)例7-3分別畫出二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)13數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件14數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件157.3遍歷二叉樹

7.3.1二叉樹遍歷遍歷二叉樹：是指如何按某條搜索路徑巡訪樹中每個結(jié)點(diǎn)使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。簡言之，以一定規(guī)則將二叉樹中結(jié)點(diǎn)排列成一個線性序列。二叉樹的遍歷有三種方法：前序遍歷、中序遍歷、后序遍歷。1.先序遍歷：按先序遍歷根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)的左子樹；訪問根結(jié)點(diǎn)的右子樹；7.3遍歷二叉樹7.3.1二叉樹遍歷162.中序遍歷：按中序遍歷根結(jié)點(diǎn)的左子樹；訪問根結(jié)點(diǎn)；按中序遍歷根結(jié)點(diǎn)的右子樹；3.后序遍歷：按后序遍歷根結(jié)點(diǎn)的左子樹；按后序遍歷根結(jié)點(diǎn)的右子樹；訪問根結(jié)點(diǎn)；4.層次遍歷：按照自上而下（從根結(jié)點(diǎn)開始），從左到右（同一層）的順序逐層訪問二叉樹上的所有結(jié)點(diǎn)，這樣的遍歷方法稱為層次遍歷。2.中序遍歷：17例7．4例7．418用三種不同方法遍歷圖5-9所示的二叉樹得：前序遍歷結(jié)果為：124753689中序遍歷結(jié)果為：742513869后序遍歷結(jié)果為：745289631層次遍歷結(jié)果為：123456789用三種不同方法遍歷圖5-9所示的二叉樹得：19前序遍歷的序列為：abdgcefh中序遍歷的序列為：dgbaechf后序遍歷的序列為：gdbehfca層次遍歷的序列為：abcdefghabcdgefh如下圖所示的一棵二叉樹，寫出其前序遍歷、中序遍歷、后序遍歷的系列：前序遍歷的序列為：abdgcefhabcdgefh如下圖所示20舉例：如圖的一棵二叉樹：1、寫出先序遍歷、中序遍歷和后序遍歷的結(jié)果；2、寫出結(jié)點(diǎn)c的雙親結(jié)點(diǎn)、其左右孩子。eadcbjfghi舉例：如圖的一棵二叉樹：eadcbjfghi21先序遍歷序列：eadcbjfghi中序遍歷序列：abcdjefhgi后序遍歷序列：bcjdahigfec的雙親結(jié)點(diǎn)是e，左孩子為b，沒有右孩子。eadcbjfghi先序遍歷序列：eadcbjfghieadcbjfghi227.3.2恢復(fù)二叉樹1.由前序和中序恢復(fù)二叉樹（1）根據(jù)前序序列確定樹的根(第一個根),根據(jù)中序確定左子樹和右子樹。（2）分別找出左子樹和右子樹的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去。（3）再對左子樹和右子樹按此法找根結(jié)點(diǎn)和左、右子樹，直到子樹只剩下1個結(jié)點(diǎn)或2結(jié)點(diǎn)或空為止。2.由后序和中序恢復(fù)二叉樹（1）根據(jù)后序序列確定樹的根(最后一個),根據(jù)中序確定左子樹和右子樹。（2）分別找出左子樹和右子樹的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去。（3）再對左子樹和右子樹按此法找根結(jié)點(diǎn)和左、右子樹，直到子樹只剩下1個結(jié)點(diǎn)或2結(jié)點(diǎn)或空為止。7.3.2恢復(fù)二叉樹1.由前序和中序恢復(fù)二叉樹237.4二叉樹的轉(zhuǎn)換7.4.1一般樹轉(zhuǎn)換為二叉樹1.連線---連接樹中所有相鄰的兄弟結(jié)點(diǎn)。2.刪線---保留父親結(jié)點(diǎn)與長子的連線，打斷父親結(jié)點(diǎn)和非長子之間的連線。3.旋轉(zhuǎn)---以根結(jié)點(diǎn)為軸心，將整棵樹順時針旋轉(zhuǎn)一定角度，使之層次分明。轉(zhuǎn)換后的結(jié)論：（1）在轉(zhuǎn)換產(chǎn)生的二叉樹中，左分支上的各結(jié)點(diǎn)在原來的樹中是父子關(guān)系；而右分支上的各結(jié)點(diǎn)在原來的樹中是兄弟關(guān)系。（2）由于樹的根結(jié)點(diǎn)無兄弟，所以轉(zhuǎn)換后的二叉樹的根結(jié)點(diǎn)必定無右子樹。（3）一棵樹采用長子、兄弟表示法所建立的存儲結(jié)構(gòu)與它所對應(yīng)的二叉樹的二叉鏈表存儲結(jié)構(gòu)是完全相同的。（4）一般樹轉(zhuǎn)換為二叉樹以后，將使樹的深度增加。7.4二叉樹的轉(zhuǎn)換7.4.1一般樹轉(zhuǎn)換為二叉樹247.4.2森林轉(zhuǎn)換成二叉樹方法：（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2）第一棵二叉樹保持不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作前一棵二叉樹根結(jié)點(diǎn)的右子樹，直到把最后一棵二叉樹的根結(jié)點(diǎn)作其前一棵二叉樹的右子樹為止。7.4.2森林轉(zhuǎn)換成二叉樹方法：257.4.3二叉樹轉(zhuǎn)換成森林方法：（1）若某結(jié)點(diǎn)是其父結(jié)點(diǎn)連起來的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、直到最后一個右孩子都與該結(jié)點(diǎn)的父結(jié)點(diǎn)連接起來。（2）刪除原二叉樹中的所有的父結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。（3）整理（1）、（2）的結(jié)果，使之層次分明，顯示出樹或森林的形狀。7.4.3二叉樹轉(zhuǎn)換成森林方法：267.5二叉樹的應(yīng)用7.5.2標(biāo)識符樹與表達(dá)式將算術(shù)表達(dá)式用二叉樹來表示,稱為標(biāo)識符樹,又稱為二叉表示樹。1.標(biāo)識符樹的特點(diǎn)（1）運(yùn)算對象（標(biāo)識符）都是葉子結(jié)點(diǎn)。（2）運(yùn)算符都是根結(jié)點(diǎn)。2.從表達(dá)式產(chǎn)生標(biāo)識符樹的方法：（1）讀入表達(dá)式的一部分產(chǎn)生相應(yīng)的二叉樹后，再讀入運(yùn)算符時，運(yùn)算符與二叉樹根結(jié)點(diǎn)的運(yùn)算符比較優(yōu)先級的高低；（2）遇到括號，先使括號內(nèi)的表達(dá)式產(chǎn)生一棵二叉樹，再把它的根結(jié)點(diǎn)連到前面已產(chǎn)生的二叉樹根結(jié)點(diǎn)的右子樹上去。（3）單目運(yùn)算+、-，加運(yùn)算對象θ（表示0）。7.5二叉樹的應(yīng)用7.5.2標(biāo)識符樹與表達(dá)式277.6哈夫曼樹及其應(yīng)用7.6.1哈夫曼樹的引入哈夫曼樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。1.幾個術(shù)語（1）路徑：從樹中一結(jié)點(diǎn)到另一結(jié)點(diǎn)之間的分支構(gòu)成這兩點(diǎn)之間的路徑。（2）路徑長度：路徑上的分支數(shù)目稱做路徑長度。（3）樹的路徑長度：是從樹根到每一結(jié)點(diǎn)的路徑長度之和，路徑長度最短的二叉樹是完全二叉樹。（4）結(jié)點(diǎn)的帶權(quán)路徑長度：為從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。（5）樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，稱為樹的帶權(quán)路徑長度。（6）最優(yōu)二叉樹：帶權(quán)路徑長度最小的二叉樹，稱為最優(yōu)二叉樹。2.求樹的帶權(quán)路徑長度見書153頁例7-11

7.6哈夫曼樹及其應(yīng)用7.6.1哈夫曼樹的引入28例：有三棵二叉樹都有4個葉子結(jié)點(diǎn)a,b,c,d,分別帶權(quán)7,5,2,4它們帶權(quán)路徑長度分別是多少？例：有三棵二叉樹都有4個葉子結(jié)點(diǎn)a,b,c,d,分別帶權(quán)7,29a)WPL=7*2+5*2+2*2+4*2=36b)WPL=4*2+2*1+7*3+5*3=46c)WPL=7*1+5*2+2*3+4*3=35由圖5-22可得：權(quán)值越大的葉子離根越近時，則二叉樹的帶權(quán)路徑長度越小，所以圖5-22中（c）圖即為哈夫曼樹。a)WPL=7*2+5*2+2*2+4*2=36307.6.2哈夫曼樹的構(gòu)造哈夫曼算法步驟如下：（1）根據(jù)給定的n個權(quán)值{W1,W2，…Wn}構(gòu)成n棵二叉樹的集合F={T1，T2，…Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹均空。（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的要結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。（3）在F中刪除這兩棵樹，同時將新得的二叉樹加入F（4）重復(fù)（2）和（3），直到F中只含一棵樹為止。7.6.2哈夫曼樹的構(gòu)造哈夫曼算法步驟如下：31例：有a~h8個葉結(jié)點(diǎn)的權(quán)值分別為:13,8,6,25,36,5,2,19求哈夫曼樹？例：有a~h8個葉結(jié)點(diǎn)的權(quán)值分別為:13,8,6,25,32數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件337.6.3哈夫曼編碼

哈夫曼編碼約定：左分支字符‘0’，右分支表示字符‘1’，則可從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑上分支組成字符串作為該葉子結(jié)點(diǎn)的字符編碼。7.6.3哈夫曼編碼哈夫曼編碼約定：左分支字符‘0’，34數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件35舉例1、以數(shù)據(jù)集{4,5,6,7,10,12,18}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹為__，其帶權(quán)路徑長度為__。并寫出各個結(jié)點(diǎn)的哈夫曼編碼。623725191391810124567分析：哈夫曼樹為：帶權(quán)路徑長度為：(4+5)*4+(10+6+7)*3+(18+12)*2=165舉例1、以數(shù)據(jù)集{4,5,6,7,10,12,18}為結(jié)點(diǎn)權(quán)36典型例題1.深度為6的二叉樹最多有()個結(jié)點(diǎn)。A)64B)63C)32D)31[分析]由二叉樹的性質(zhì)2知，最多結(jié)點(diǎn)個數(shù)26-1=64-1=63。[答案]B)2.任何一顆二叉樹的葉結(jié)點(diǎn)在其先根、中根、后跟遍歷序列中的相對位置()。A)肯定發(fā)生變化B)有時發(fā)生變化C)肯定不發(fā)生變化D)無法確定[分析]由于在三種遍歷中總是先遍歷左子數(shù)，后遍歷右子數(shù)，所以二叉樹的葉子結(jié)點(diǎn)在三種遍歷序列中的相對位置不好發(fā)生變化。[答案]C)。典型例題1.深度為6的二叉樹最多有()個結(jié)點(diǎn)。373.設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則這類二叉樹上所含結(jié)點(diǎn)總數(shù)最少()個。A)k+1B)2kC)2k-1D)2k+1[分析]因為不存在度為1的結(jié)點(diǎn)，所以二叉樹上除根結(jié)點(diǎn)外，每增加一層，至少要增加2個結(jié)點(diǎn)，如圖5-25所示。典型例題圖5-25因此當(dāng)h=1時，結(jié)點(diǎn)總數(shù)為1(2*1-1=1)，它是根結(jié)點(diǎn)；當(dāng)h=2時，結(jié)點(diǎn)總數(shù)為3(2*2-1=3)；當(dāng)h=2時，結(jié)點(diǎn)總數(shù)為5(2*3-1=5);…當(dāng)b=k時，結(jié)點(diǎn)總數(shù)為2*k-1。[答案]C)3.設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則這類二叉384.具有n個結(jié)點(diǎn)的完全二叉樹，若按層次從上到下，從左到右對其編號(根結(jié)點(diǎn)為1號)，則編號最大的分支結(jié)點(diǎn)序號是________，編號最小的分支結(jié)點(diǎn)序號是_________，編號最大的葉子結(jié)點(diǎn)序號是_________，編號最小的葉子結(jié)點(diǎn)序號是__________。[分析]由二叉樹的性質(zhì)5知，最后一個結(jié)點(diǎn)的編號是n，那么它的雙親結(jié)點(diǎn)編號是[n/2]，這個雙親結(jié)點(diǎn)應(yīng)該是二叉樹中最后一個分支結(jié)點(diǎn)。也就是說，在二叉樹中，編號1～[n/2]屬于分支結(jié)點(diǎn)，編號[n/2]+1-n屬于葉子結(jié)點(diǎn)。[答案][n/2]，1，n，[n/2]+1。典型例題4.具有n個結(jié)點(diǎn)的完全二叉樹，若按層次從上到下，從左到右對其395.已知一棵二叉樹的前根序列和中根序列分別為ABDGHECFIJ及GDHBEACIJF，請畫出這棵二叉樹。[分析]根據(jù)二叉樹的前根、中根遍歷特點(diǎn)可知，在二叉樹的前根遍歷序列中，第一個結(jié)點(diǎn)肯定是根結(jié)點(diǎn)；而其中根遍歷序列中，根結(jié)點(diǎn)將所有結(jié)點(diǎn)分為兩部分，左邊一部分對應(yīng)于二叉樹的左子樹，右邊一部分對應(yīng)于二叉樹的右子樹。依此類推，在左子樹的前根遍歷序列中，第一個結(jié)點(diǎn)一定是左子數(shù)的根結(jié)點(diǎn)；而其中根遍歷序列中，根結(jié)點(diǎn)又將左子樹的所有結(jié)點(diǎn)分為兩部分，左邊一部分對應(yīng)于左子樹的左子樹，右邊一部分對應(yīng)于左子樹的右子樹。同理，在右子樹的前根遍歷序列中，第一個結(jié)點(diǎn)也一定是右子樹的根結(jié)點(diǎn)；而其中根遍歷序列中，根結(jié)點(diǎn)又將右子樹的所以結(jié)點(diǎn)分為兩部分，左邊一部分對應(yīng)于右子樹的左子樹，右邊一部分對應(yīng)于右子樹的右子樹。如果按照上述思想遞歸下去，就可以完整地得到一顆所求的二叉樹。典型例題5.已知一棵二叉樹的前根序列和中根序列分別為ABDGHECF40[答案]應(yīng)用上面的思想,本題的解題過程如下:1)由前根序列知A是二叉樹的根結(jié)點(diǎn)；由中根序列知GDHBE是A的左子樹中的結(jié)點(diǎn)，CIJF是A的右子樹中的結(jié)點(diǎn)。2)由前根序列知B是A的左子樹的根結(jié)點(diǎn)；由中根序列知GDH是B的左子樹中的結(jié)點(diǎn)，E是B的右子樹中的結(jié)點(diǎn)。3)由前根序列知D是B的左子樹的根結(jié)點(diǎn)；由中根序列知G是D的左子樹中的結(jié)點(diǎn)，H是D的右子樹中的結(jié)點(diǎn)。4)由前根序列知C是A的右子樹的根結(jié)點(diǎn)；由中根序列知IJF是C的右子樹中的結(jié)點(diǎn)(C的左子樹為空)。5)由前根序列知F是C的右子樹的根結(jié)點(diǎn)；由中根序列知IJ是F的左子樹中的結(jié)點(diǎn)(F的右子樹為空)。6)由前根序列知I是F的左子樹的根結(jié)點(diǎn)；由中根序列知J是I的右子樹中的結(jié)點(diǎn)(F的左子樹為空)。圖5-26為上述解題過程的示意圖，完整的二叉樹如圖5-27所示。典型例題[答案]應(yīng)用上面的思想,本題的解題過程如下:典型例題41典型例題典型例題42典型例題典型例題43作業(yè)P169五.1,2,3,4,5,6作業(yè)P169五.1,2,3,4,5,644第七章樹和二叉樹

樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，在計算機(jī)科學(xué)中有著廣泛的應(yīng)用。7.1樹的定義和術(shù)語7.1.1樹的定義樹（tree）是n(n≥0)個結(jié)點(diǎn)的有限集。在一棵非空樹中：（1）有且僅有一個特定的結(jié)點(diǎn),稱為根（root）（根結(jié)點(diǎn)無前驅(qū)結(jié)點(diǎn)）;（2）當(dāng)n>1時，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集（T1,T2,…Tm），其中每一集合本身又是一棵樹，并且稱為根的子樹（subtree）。第七章樹和二叉樹樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，在計45舉例例7．1（a）只有根結(jié)點(diǎn)的樹

（b）一般的樹（b）中A為根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成三個互不相交的子集：T1={B，E，F(xiàn)，K，L}，T2={C，G}，T3={D，H，I，J}而T1，T2，T3本身又都是只有一個根結(jié)點(diǎn)的樹。ALKEFGHIJDCBAM舉例例7．1（a）只有根結(jié)點(diǎn)的樹ALKE467.1.2基本術(shù)語：（1）結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向其子樹的分支（2）結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有子樹數(shù)目稱為結(jié)點(diǎn)的度。如圖7-1-1的（b）中，A的度為3；C的度為1；M的度為0。（3）葉子（或終端）結(jié)點(diǎn)：度為零的結(jié)點(diǎn)。（4）分支結(jié)點(diǎn)（或非終端結(jié)點(diǎn)）：除根結(jié)點(diǎn)外度不為零的結(jié)點(diǎn)，也稱為內(nèi)部結(jié)點(diǎn)。（5）樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。（6）孩子：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子。如圖7-1-1的（b）中，D為A的子樹T3的根，則D是A的孩子。（7）雙親：和孩子定義相應(yīng)地該結(jié)點(diǎn)稱為孩子的雙親。如圖7-1-1的（b）中，A為D的雙親。7.1.2基本術(shù)語：47（8）兄弟：同一個雙親的孩子之間互稱兄弟。如圖7-1-1的（b）中的H，I，J。（9）祖先：從根到該結(jié)點(diǎn)所經(jīng)過分支上的所有結(jié)點(diǎn)。如：M的祖先為A，D，H（10）子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。如圖7-1-1的（b）中B的子孫為E，F(xiàn)，K，L（11）層次：從根開始定義為第一層，根的孩子為第二層，依次例推。（12）深度（或高度）：樹中結(jié)點(diǎn)的最大層次。（13）有序樹：將樹中結(jié)點(diǎn)的各子樹看成從左到右是有序的。有序樹中最左邊的子樹的根稱第一個孩子，最右邊的稱為最后一個孩子。（14）無序樹：樹中結(jié)點(diǎn)的各子樹沒有次序的。（15）森林：是m(m≥0)棵互不相交的樹的集合，對樹中每個結(jié)點(diǎn)而言，其子樹的集合即為森林。（8）兄弟：同一個雙親的孩子之間互稱兄弟。如圖7-1-1的（48該樹的根結(jié)點(diǎn)為：a，分支結(jié)點(diǎn)為：b、c、e；葉子結(jié)點(diǎn)為d、f、g、h、i、j；該樹的度為3，高度為4；第一層有結(jié)點(diǎn)：a，第二層有結(jié)點(diǎn)：b、c；第三層有結(jié)點(diǎn)d、e、f、g、h，第四層有結(jié)點(diǎn)：i、j。abcdeigjhf該樹的根結(jié)點(diǎn)為：a，分支結(jié)點(diǎn)為：b、c、e；葉子結(jié)點(diǎn)為d、f497.2二叉樹7.2.1二叉樹的定義和性質(zhì)：1、定義：二叉樹是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且二叉樹的子樹有左右之分，其次序不能任意顛倒。2、如圖所示二叉樹的五種基本形態(tài)（a）(b)(c)(d)(e)7.2二叉樹7.2.1二叉樹的定義和性質(zhì)：507.2.2二叉樹的性質(zhì)

(1)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)（i≥1）。(2)性質(zhì)2：深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為2k-1(k≥1)。(3)性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1（4）一棵深度為k且有2k-1個結(jié)點(diǎn)的二叉樹稱滿二叉樹。特點(diǎn)：每層上的結(jié)點(diǎn)數(shù)都為最大結(jié)點(diǎn)數(shù)，除終端結(jié)點(diǎn)外，每個結(jié)點(diǎn)都有兩棵子樹。（5）完全二叉樹：如深度為k，有N個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到N的結(jié)點(diǎn)一一對時，稱之為完全二叉樹。特點(diǎn)：深度為k的完全二叉樹，其前k-1層是一棵滿二叉樹，最后第k層結(jié)點(diǎn)都盡量排在靠左的位置上。顯然一棵滿二叉樹一定是完全二叉樹，但一棵完全二叉樹不一定是滿二叉樹。7.2.2二叉樹的性質(zhì)51（6）完全二叉樹的兩個特性：性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為└Log2n┘+1。性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹（其深度為└Log2n┘+1）的結(jié)點(diǎn)按順序編號，則任一結(jié)點(diǎn)i(1≤i≤n)有：①若i=1,則結(jié)點(diǎn)i是二叉樹的根結(jié)點(diǎn)，若i>1，則i的雙親結(jié)點(diǎn)為結(jié)點(diǎn)┗i/2┛;②若2i≤n，則i的左孩子是結(jié)點(diǎn)2i，否則無左孩子；③若2i+1≤n，則i的右孩子是結(jié)點(diǎn)2i+1,否則無右孩子。（6）完全二叉樹的兩個特性：527.2.3二叉樹的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素，按滿二叉樹的結(jié)點(diǎn)順序編號依次存放二叉樹中數(shù)據(jù)元素。

012345

T(6)圖7-3完全二叉樹ABCDEFABCDEF7.2.3二叉樹的存儲結(jié)構(gòu)ABCDEFABCDEF53數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件542.鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈表的結(jié)點(diǎn)至少包含：數(shù)據(jù)域和左右指針域的鏈有時還需增一指向雙親的指針域，有兩個指針域的鏈表稱為二叉鏈表，有三個指針域的鏈表稱為三叉鏈表，如圖5-5所示：

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)55數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件56例7-3分別畫出二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)例7-3分別畫出二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)57數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件58數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件597.3遍歷二叉樹

7.3.1二叉樹遍歷遍歷二叉樹：是指如何按某條搜索路徑巡訪樹中每個結(jié)點(diǎn)使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。簡言之，以一定規(guī)則將二叉樹中結(jié)點(diǎn)排列成一個線性序列。二叉樹的遍歷有三種方法：前序遍歷、中序遍歷、后序遍歷。1.先序遍歷：按先序遍歷根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)的左子樹；訪問根結(jié)點(diǎn)的右子樹；7.3遍歷二叉樹7.3.1二叉樹遍歷602.中序遍歷：按中序遍歷根結(jié)點(diǎn)的左子樹；訪問根結(jié)點(diǎn)；按中序遍歷根結(jié)點(diǎn)的右子樹；3.后序遍歷：按后序遍歷根結(jié)點(diǎn)的左子樹；按后序遍歷根結(jié)點(diǎn)的右子樹；訪問根結(jié)點(diǎn)；4.層次遍歷：按照自上而下（從根結(jié)點(diǎn)開始），從左到右（同一層）的順序逐層訪問二叉樹上的所有結(jié)點(diǎn)，這樣的遍歷方法稱為層次遍歷。2.中序遍歷：61例7．4例7．462用三種不同方法遍歷圖5-9所示的二叉樹得：前序遍歷結(jié)果為：124753689中序遍歷結(jié)果為：742513869后序遍歷結(jié)果為：745289631層次遍歷結(jié)果為：123456789用三種不同方法遍歷圖5-9所示的二叉樹得：63前序遍歷的序列為：abdgcefh中序遍歷的序列為：dgbaechf后序遍歷的序列為：gdbehfca層次遍歷的序列為：abcdefghabcdgefh如下圖所示的一棵二叉樹，寫出其前序遍歷、中序遍歷、后序遍歷的系列：前序遍歷的序列為：abdgcefhabcdgefh如下圖所示64舉例：如圖的一棵二叉樹：1、寫出先序遍歷、中序遍歷和后序遍歷的結(jié)果；2、寫出結(jié)點(diǎn)c的雙親結(jié)點(diǎn)、其左右孩子。eadcbjfghi舉例：如圖的一棵二叉樹：eadcbjfghi65先序遍歷序列：eadcbjfghi中序遍歷序列：abcdjefhgi后序遍歷序列：bcjdahigfec的雙親結(jié)點(diǎn)是e，左孩子為b，沒有右孩子。eadcbjfghi先序遍歷序列：eadcbjfghieadcbjfghi667.3.2恢復(fù)二叉樹1.由前序和中序恢復(fù)二叉樹（1）根據(jù)前序序列確定樹的根(第一個根),根據(jù)中序確定左子樹和右子樹。（2）分別找出左子樹和右子樹的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去。（3）再對左子樹和右子樹按此法找根結(jié)點(diǎn)和左、右子樹，直到子樹只剩下1個結(jié)點(diǎn)或2結(jié)點(diǎn)或空為止。2.由后序和中序恢復(fù)二叉樹（1）根據(jù)后序序列確定樹的根(最后一個),根據(jù)中序確定左子樹和右子樹。（2）分別找出左子樹和右子樹的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)連到父結(jié)點(diǎn)上去。（3）再對左子樹和右子樹按此法找根結(jié)點(diǎn)和左、右子樹，直到子樹只剩下1個結(jié)點(diǎn)或2結(jié)點(diǎn)或空為止。7.3.2恢復(fù)二叉樹1.由前序和中序恢復(fù)二叉樹677.4二叉樹的轉(zhuǎn)換7.4.1一般樹轉(zhuǎn)換為二叉樹1.連線---連接樹中所有相鄰的兄弟結(jié)點(diǎn)。2.刪線---保留父親結(jié)點(diǎn)與長子的連線，打斷父親結(jié)點(diǎn)和非長子之間的連線。3.旋轉(zhuǎn)---以根結(jié)點(diǎn)為軸心，將整棵樹順時針旋轉(zhuǎn)一定角度，使之層次分明。轉(zhuǎn)換后的結(jié)論：（1）在轉(zhuǎn)換產(chǎn)生的二叉樹中，左分支上的各結(jié)點(diǎn)在原來的樹中是父子關(guān)系；而右分支上的各結(jié)點(diǎn)在原來的樹中是兄弟關(guān)系。（2）由于樹的根結(jié)點(diǎn)無兄弟，所以轉(zhuǎn)換后的二叉樹的根結(jié)點(diǎn)必定無右子樹。（3）一棵樹采用長子、兄弟表示法所建立的存儲結(jié)構(gòu)與它所對應(yīng)的二叉樹的二叉鏈表存儲結(jié)構(gòu)是完全相同的。（4）一般樹轉(zhuǎn)換為二叉樹以后，將使樹的深度增加。7.4二叉樹的轉(zhuǎn)換7.4.1一般樹轉(zhuǎn)換為二叉樹687.4.2森林轉(zhuǎn)換成二叉樹方法：（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2）第一棵二叉樹保持不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作前一棵二叉樹根結(jié)點(diǎn)的右子樹，直到把最后一棵二叉樹的根結(jié)點(diǎn)作其前一棵二叉樹的右子樹為止。7.4.2森林轉(zhuǎn)換成二叉樹方法：697.4.3二叉樹轉(zhuǎn)換成森林方法：（1）若某結(jié)點(diǎn)是其父結(jié)點(diǎn)連起來的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、直到最后一個右孩子都與該結(jié)點(diǎn)的父結(jié)點(diǎn)連接起來。（2）刪除原二叉樹中的所有的父結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。（3）整理（1）、（2）的結(jié)果，使之層次分明，顯示出樹或森林的形狀。7.4.3二叉樹轉(zhuǎn)換成森林方法：707.5二叉樹的應(yīng)用7.5.2標(biāo)識符樹與表達(dá)式將算術(shù)表達(dá)式用二叉樹來表示,稱為標(biāo)識符樹,又稱為二叉表示樹。1.標(biāo)識符樹的特點(diǎn)（1）運(yùn)算對象（標(biāo)識符）都是葉子結(jié)點(diǎn)。（2）運(yùn)算符都是根結(jié)點(diǎn)。2.從表達(dá)式產(chǎn)生標(biāo)識符樹的方法：（1）讀入表達(dá)式的一部分產(chǎn)生相應(yīng)的二叉樹后，再讀入運(yùn)算符時，運(yùn)算符與二叉樹根結(jié)點(diǎn)的運(yùn)算符比較優(yōu)先級的高低；（2）遇到括號，先使括號內(nèi)的表達(dá)式產(chǎn)生一棵二叉樹，再把它的根結(jié)點(diǎn)連到前面已產(chǎn)生的二叉樹根結(jié)點(diǎn)的右子樹上去。（3）單目運(yùn)算+、-，加運(yùn)算對象θ（表示0）。7.5二叉樹的應(yīng)用7.5.2標(biāo)識符樹與表達(dá)式717.6哈夫曼樹及其應(yīng)用7.6.1哈夫曼樹的引入哈夫曼樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。1.幾個術(shù)語（1）路徑：從樹中一結(jié)點(diǎn)到另一結(jié)點(diǎn)之間的分支構(gòu)成這兩點(diǎn)之間的路徑。（2）路徑長度：路徑上的分支數(shù)目稱做路徑長度。（3）樹的路徑長度：是從樹根到每一結(jié)點(diǎn)的路徑長度之和，路徑長度最短的二叉樹是完全二叉樹。（4）結(jié)點(diǎn)的帶權(quán)路徑長度：為從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。（5）樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，稱為樹的帶權(quán)路徑長度。（6）最優(yōu)二叉樹：帶權(quán)路徑長度最小的二叉樹，稱為最優(yōu)二叉樹。2.求樹的帶權(quán)路徑長度見書153頁例7-11

7.6哈夫曼樹及其應(yīng)用7.6.1哈夫曼樹的引入72例：有三棵二叉樹都有4個葉子結(jié)點(diǎn)a,b,c,d,分別帶權(quán)7,5,2,4它們帶權(quán)路徑長度分別是多少？例：有三棵二叉樹都有4個葉子結(jié)點(diǎn)a,b,c,d,分別帶權(quán)7,73a)WPL=7*2+5*2+2*2+4*2=36b)WPL=4*2+2*1+7*3+5*3=46c)WPL=7*1+5*2+2*3+4*3=35由圖5-22可得：權(quán)值越大的葉子離根越近時，則二叉樹的帶權(quán)路徑長度越小，所以圖5-22中（c）圖即為哈夫曼樹。a)WPL=7*2+5*2+2*2+4*2=36747.6.2哈夫曼樹的構(gòu)造哈夫曼算法步驟如下：（1）根據(jù)給定的n個權(quán)值{W1,W2，…Wn}構(gòu)成n棵二叉樹的集合F={T1，T2，…Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹均空。（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的要結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。（3）在F中刪除這兩棵樹，同時將新得的二叉樹加入F（4）重復(fù)（2）和（3），直到F中只含一棵樹為止。7.6.2哈夫曼樹的構(gòu)造哈夫曼算法步驟如下：75例：有a~h8個葉結(jié)點(diǎn)的權(quán)值分別為:13,8,6,25,36,5,2,19求哈夫曼樹？例：有a~h8個葉結(jié)點(diǎn)的權(quán)值分別為:13,8,6,25,76數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件777.6.3哈夫曼編碼

哈夫曼編碼約定：左分支字符‘0’，右分支表示字符‘1’，則可從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑上分支組成字符串作為該葉子結(jié)點(diǎn)的字符編碼。7.6.3哈夫曼編碼哈夫曼編碼約定：左分支字符‘0’，78數(shù)據(jù)結(jié)構(gòu)預(yù)算法第七章樹課件79舉例1、以數(shù)據(jù)集{4,5,6,7,10,12,18}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹為__，其帶權(quán)路徑長度為__。并寫出各個結(jié)點(diǎn)的哈夫曼編碼。623725191391810124567分析：哈夫曼樹為：帶權(quán)路徑長度為：(4+5)*4+(10+6+7)*3+(18+12)*2=165舉例1、以數(shù)據(jù)集{4,5,6,7,10,12,18}為結(jié)點(diǎn)權(quán)80典型例題1.深度為6的二叉樹最多有()個結(jié)點(diǎn)。A)64B)63C)32D)31[分析]由二叉樹的性質(zhì)2知，最多結(jié)點(diǎn)個數(shù)26-1=64-1=63。[答案]B)2.任何一顆二叉樹的葉結(jié)點(diǎn)在其先根、中根、后跟遍歷序列中的相對位置()。A)肯定發(fā)生變化B)有時發(fā)生變化C)肯定不發(fā)生變化D)無法確定[分析]由于在三種遍歷中總是先遍歷左子數(shù)，后遍歷右子數(shù)，所以二叉樹的葉子結(jié)點(diǎn)在三種遍歷序列中的相對位置不好發(fā)生變化。[答案]C)。典型例題1.深度