計算機軟件基礎(chǔ)(自考本科樹)

計算機軟件基礎(chǔ)第二篇數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第十章樹和二叉樹一、樹（tree）1.樹的定義樹：是一個具有n（n≥0）個節(jié)點的有限集合T。滿足以下兩個條件：（1）任意一顆樹有且僅有一個特定的根節(jié)點（rootnode）。（2）除根節(jié)點以外，其余節(jié)點可以分為m（m≥0

）個互不相交的子集T1，T2,…Tm，其中每個子集本身又是一顆樹，稱為根的子樹。結(jié)論：一棵樹由若干子樹構(gòu)成，而每一顆子樹由若干顆子子樹構(gòu)成。一、樹（tree）2.樹的表示形式ABCDEF自然表示法集合表示法ABCEDF層次表示法1A1.1A1.2B1.2.1E1.2.2F1.3D一、樹（tree）3.樹的有關(guān)名詞（1）節(jié)點的度：節(jié)點的孩子數(shù)。（2）樹的度=樹的叉=擁有孩子最多節(jié)點的孩子個數(shù)（3）葉子節(jié)點=終端節(jié)點=沒有孩子的節(jié)點（4）雙親節(jié)點：指的是這個節(jié)點的父親節(jié)點。（5）樹的高度=樹的層數(shù)二、二叉樹二叉樹：最多具有兩個樹杈的樹。其中，左邊的樹杈稱為該節(jié)點的左子樹，右邊的樹杈稱為該節(jié)點的右子樹。2.二叉樹的基本形態(tài)：共5種一個節(jié)點也沒有只有一個根節(jié)點只有左子樹只有右子樹左、右子樹都有二、二叉樹3.二叉樹與一般樹的區(qū)別：一般樹二叉樹樹中至少有一個根節(jié)點（n>0）可以一個根節(jié)點都沒有（n≥0）樹的度≥0樹的度≤2不要求子樹木順序（無序樹）子樹有左、右之分（有序樹）二、二叉樹4.二叉樹的性質(zhì)性質(zhì)1：二叉樹的第i層上最多有2i-1個節(jié)點（i≥

1）；性質(zhì)2：高度為k的二叉樹最多有2k-1個節(jié)點（k≥

1）

；性質(zhì)3：任意一顆二叉樹中，如果沒有孩子的節(jié)點個數(shù)為n0，有兩個孩子的節(jié)點個數(shù)為n2，那么n0=n2+1二、二叉樹5.二叉樹的兩種特殊情形：（1）滿二叉樹：除葉子節(jié)點以外，其它節(jié)點都有兩個孩子，而且葉子節(jié)點位于同一層上的二叉樹。滿二叉樹（2）完全二叉樹：一個滿二叉樹的最下層，從右向左連續(xù)缺少n個節(jié)點的二叉樹。完全二叉樹注意：深度為k的滿二叉樹，有2k-1個節(jié)點二、二叉樹例：（2010.4單選）一個深度為k的完全二叉樹中節(jié)點數(shù)至少有（）。A2k

B2k-1C2k+1D2k-1二、二叉樹例10-1試寫出具有3個節(jié)點的所有不同形態(tài)的樹和二叉樹。二叉樹有五種：樹有2種：①②二、二叉樹6.二叉樹的存儲結(jié)構(gòu)———順序存儲操作步驟為：step1：現(xiàn)將二叉樹變成完全二叉樹（給有關(guān)節(jié)點補夠兩個孩子，所補節(jié)點為虛擬節(jié)點，僅占個空間）step2：將這個完全二叉樹中各節(jié)點從上到下，逐層由左向右一次存放到計算機連續(xù)空間中。二、二叉樹例10-2：12345789101112136abcdabcd13123456789101112abcd二、二叉樹例10-3一個深度為K且只有K個節(jié)點的二叉樹順序存儲最多需要多少個存儲空間，最少需要多少個。二、二叉樹（2）完全二叉樹節(jié)點順序編號的意義12436578109二、二叉樹例10-4一個完全二叉樹節(jié)點個數(shù)為1000，則n0、n1、n2和高度h各為多少?12436578109二、二叉樹6.二叉樹的存儲結(jié)構(gòu)———鏈?zhǔn)酱鎯Γ?）二叉樹鏈?zhǔn)酱鎯χ?，每個節(jié)點有3個成員（域）dataLchildRchild

Lchild——存放該節(jié)點左孩子的地址；

Rchild——存放該節(jié)點右孩子的地址；

data——存放該節(jié)點的數(shù)據(jù)；二、二叉樹6.二叉樹的存儲結(jié)構(gòu)———鏈?zhǔn)酱鎯Γ?）二叉樹鏈?zhǔn)酱鎯︻愋偷亩xstructnode{datatypedata;structnode*Lchild,*Rchild;};二、二叉樹例10-5ABCDA^A^A^A^^三、二叉樹的遍歷1.中序遍歷如果二叉樹不為空，則依次執(zhí)行如下操作：（1）先：中序遍歷左子樹；（2）再：訪問根節(jié)點；（3）最后：中序遍歷右子樹。根左子樹右子樹

二叉樹的遍歷：按照一定的順序訪問樹中所有節(jié)點，而且每個節(jié)點僅被訪問一次的操作。三、二叉樹的遍歷例：如圖所示二叉樹，試寫出對其中序遍歷的結(jié)果。ABDCEFGHI中序遍歷結(jié)果：DBGEHACIF三、二叉樹的遍歷中序遍歷的算法描述voidinorde(bitree*root)//root為指向根節(jié)點的指針{ if(root!=null) {

inorde(root->Lchild);//先遍歷左子樹

printf("%c",root->data);//然后訪問根節(jié)點

inorde(root->Rchild);//最后遍歷右子樹

}}三、二叉樹的遍歷1.先序遍歷如果二叉樹不為空，則依次執(zhí)行如下操作：（1）先：訪問根節(jié)點；（2）再：先序遍歷左子樹；（3）最后：先序遍歷右子樹。根左子樹右子樹三、二叉樹的遍歷例：如圖所示二叉樹，試寫出對其先序遍歷的結(jié)果。ABDCEFGHI先序遍歷結(jié)果：ABDEGHCFI三、二叉樹的遍歷1.后序遍歷如果二叉樹不為空，則依次執(zhí)行如下操作：（1）先：后序遍歷左子樹；（2）再：后序遍歷右子樹；（3）最后：訪問根節(jié)點

。根左子樹右子樹三、二叉樹的遍歷例：如圖所示二叉樹，試寫出對其后序遍歷的結(jié)果。ABDCEFGHI后序遍歷結(jié)果：DGHEBIFCA三、二叉樹的遍歷結(jié)論：由先序和中序或后序和中序遍歷結(jié)果，可以確定唯一的一棵二叉樹。口訣：先序后序定樹根；中序區(qū)分左和右。三、二叉樹的遍歷例：（2010.4）已知二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是。cedbacedba三、二叉樹的遍歷例10-7已知二叉樹的后序遍歷序列和中序遍歷序列結(jié)果分別是DGHEBIFCA和DBGEHACIF，試確定這個二叉樹。ACFIBDEGH四、樹、森林和二叉樹一、樹的存儲結(jié)構(gòu)1、雙親靜態(tài)鏈表存儲法ABDCEF序號節(jié)點雙親0A-11B02C03D04E25F2四、樹、森林和二叉樹一、樹的存儲結(jié)構(gòu)2、孩子鏈表存儲法ABDCEFdatanext0A

1

2

3^1B^2C

4

5^3D^4E^5F^四、樹、森林和二叉樹1）樹的孩子兄弟表示口訣：豎線連接左孩子，橫線連接親兄弟。例：將如圖所示樹，用樹的孩子兄弟表示。ABDCEFABDCEF3、孩子兄弟鏈?zhǔn)酱鎯Ψㄋ?、樹、森林和二叉?）用鏈連接各節(jié)點。ABDCEF3、孩子兄弟鏈?zhǔn)酱鎯Ψˋ^BCDEF^^^^^^存儲date指向大孩子指向下一個兄弟四、樹、森林和二叉樹1.樹變二叉樹step1:寫出樹的孩子兄弟表示；step2:將豎線變成左子樹，橫向變成右子樹。ABDCEFABDCEFABCDEFA一、樹的存儲結(jié)構(gòu)四、樹、森林和二叉樹3.樹的遍歷樹的遍歷有：先序和后序注意：樹的先序遍歷結(jié)果與對應(yīng)二叉樹的先序遍歷結(jié)果相同；樹的后序遍歷結(jié)果與對應(yīng)二叉樹的中序遍歷結(jié)果相同。四、樹、森林和二叉樹4.森林變二叉樹step1:把構(gòu)成森林的每一棵樹變成二叉樹；step2:依次把后一棵二叉樹連在前一棵二叉樹根的右子樹上。MJKLGHIABDCEFABCDEFGHIJKLM四、樹、森林和二叉樹4.森林變二叉樹（續(xù)）ABCDEFJKLMGHI四、樹、森林和二叉樹5.森林的遍歷森林的遍歷有：先序和后序注意：森林的先序遍歷結(jié)果與對應(yīng)二叉樹的先序遍歷結(jié)果相同；森林的后序遍歷結(jié)果與對應(yīng)二叉樹的中序遍歷結(jié)果相同。例.（2010.4解答）已知下圖所示的二叉樹，要求：（1）將該二叉樹還原成森林；（2）寫出森林的先根遍歷序列和后根遍歷序列abdcgefhij解（1）將該二叉樹還原成森林；（2）寫出森林的先根遍歷序列和后根遍歷序列abdgcefhij解（1）將該二叉樹還原成森林；abdgcefhijabdgcefhij解（1）將該二叉樹還原成森林；abdgcefhijabdgcefhij解（2）先根遍歷序列：abdgcefhijabdcgefhij后根遍歷序列：bgdaecihjf五、哈夫曼樹及其應(yīng)用1.幾個基本術(shù)語（1）第i個葉子節(jié)點的權(quán)值Wi：給第i個節(jié)點所賦予的重要程度值；（2）第i個葉子節(jié)點的路徑長度Li：從根到第i個節(jié)點所經(jīng)路徑的段數(shù)；（3）第i個葉子節(jié)點的帶權(quán)路徑長度WPLi：WPLi=Wi×Li；（4）樹的帶權(quán)路徑長度WPL：等于該樹中所有葉子的帶權(quán)路徑長度之和。五、哈夫曼樹及其應(yīng)用4259924529455429五、哈夫曼樹及其應(yīng)用2.哈夫曼樹哈夫曼樹：也稱為最優(yōu)二叉樹，就是帶權(quán)路徑長度為最小的二叉樹。3.根據(jù)已知樹，求對應(yīng)哈夫曼樹的方法step1：將該樹的葉子權(quán)值由小到大進行排序；step2：從所排序中取出兩個最小的權(quán)值和構(gòu)造二叉樹，該二叉樹的根節(jié)點為W（）step3：從權(quán)值序列中劃去和。劃去后，如果序列為空，說明所要求的二叉樹已經(jīng)構(gòu)成；否則，將W加入權(quán)值序列中，重復(fù)step1~step3。五、哈夫曼樹及其應(yīng)用例：（09.4月）給定一組權(quán)值：4、1、12、2、10，構(gòu)造對應(yīng)的哈夫曼樹（權(quán)值小的為左子樹，權(quán)值大的為右子樹），并求出該樹的帶權(quán)路徑長度。step1：按權(quán)值由小到大排序：1step2：取兩個最小權(quán)值，、2、4、1012、3構(gòu)建一顆二叉樹12step3：從原序列中劃去1和2將3插入到序列中3step3：重復(fù)步驟1~34771017121729五、哈夫曼樹及其應(yīng)用4.哈夫曼樹的性質(zhì)（1）給定權(quán)值樹所對應(yīng)的哈夫曼樹不是唯一的，但是，該樹的帶權(quán)路徑長度WPL肯定是唯一的；（2）權(quán)值越大的節(jié)點，距離根節(jié)點越近；（3）哈夫曼樹中，不存在只有一個孩子的節(jié)點；（4）哈夫曼樹的節(jié)點總數(shù)n：=2×葉子節(jié)點個數(shù)－1。五、哈夫曼樹及其應(yīng)用5.哈夫曼編碼（1）定義：長度最小的二進制串電文編碼。（2）求哈夫曼編碼的步驟：step1：構(gòu)造哈夫曼樹（依據(jù)：以電文中各字符出現(xiàn)的次數(shù)為權(quán)值）；step2：構(gòu)造哈夫曼編碼樹（方法：在哈夫曼樹左子樹的邊上添0，右子樹的邊上添1）；step3：求各字符的哈夫曼編碼（從根到各字符節(jié)點路徑上的二進制序列）；五、哈夫曼樹及其應(yīng)用例：（2008.04）假設(shè)字符a，b，c，d，e，f使用的頻率分別為0.07，0.09，0.13，0.21，0.23，0.27，構(gòu)造哈夫曼編碼樹（權(quán)值小的為左子樹，權(quán)值大的為右子樹），并根據(jù)哈夫曼編碼樹寫出a，b，c，d，e，f的編碼。step1:構(gòu)造哈夫曼樹791610013292123