計(jì)算機(jī)軟件基礎(chǔ)(自考本科樹(shù))

1、1. 樹(shù)的定義樹(shù)的定義樹(shù)：是一個(gè)具有樹(shù)：是一個(gè)具有n（n0）個(gè)節(jié)點(diǎn)的）個(gè)節(jié)點(diǎn)的有限有限集合集合T。滿足以下兩個(gè)條件：滿足以下兩個(gè)條件：（1） 任意一顆樹(shù)有且僅有一個(gè)特定的根節(jié)點(diǎn)（任意一顆樹(shù)有且僅有一個(gè)特定的根節(jié)點(diǎn)（root node）。）。（2）除根節(jié)點(diǎn)以外，其余節(jié)點(diǎn)可以分為）除根節(jié)點(diǎn)以外，其余節(jié)點(diǎn)可以分為m（m 0 ）個(gè)互不相交的子集個(gè)互不相交的子集T1，T2, Tm，其中每個(gè)子集本，其中每個(gè)子集本身又是一顆樹(shù)，稱為根的身又是一顆樹(shù)，稱為根的子樹(shù)子樹(shù)。結(jié)論：結(jié)論：一棵樹(shù)由若干子樹(shù)構(gòu)成，而每一顆子樹(shù)由一棵樹(shù)由若干子樹(shù)構(gòu)成，而每一顆子樹(shù)由若干顆子子樹(shù)構(gòu)成。若干顆子子樹(shù)構(gòu)成。2. 樹(shù)的表示形式樹(shù)的

2、表示形式3. 樹(shù)的有關(guān)名詞樹(shù)的有關(guān)名詞（1）節(jié)點(diǎn)的度：節(jié)點(diǎn)的孩子數(shù)。）節(jié)點(diǎn)的度：節(jié)點(diǎn)的孩子數(shù)。（2）樹(shù)的度）樹(shù)的度=樹(shù)的叉樹(shù)的叉=擁有孩子最多節(jié)點(diǎn)的孩子個(gè)數(shù)擁有孩子最多節(jié)點(diǎn)的孩子個(gè)數(shù)（3）葉子節(jié)點(diǎn)）葉子節(jié)點(diǎn)=終端節(jié)點(diǎn)終端節(jié)點(diǎn)=沒(méi)有孩子的節(jié)點(diǎn)沒(méi)有孩子的節(jié)點(diǎn)（4）雙親節(jié)點(diǎn)：指的是這個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)。）雙親節(jié)點(diǎn)：指的是這個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)。（5）樹(shù)的高度）樹(shù)的高度=樹(shù)的層數(shù)樹(shù)的層數(shù) 二叉樹(shù)：最多具有兩個(gè)樹(shù)杈的樹(shù)。其中，左邊的二叉樹(shù)：最多具有兩個(gè)樹(shù)杈的樹(shù)。其中，左邊的樹(shù)杈稱為該節(jié)點(diǎn)的左子樹(shù)，右邊的樹(shù)杈稱為該節(jié)點(diǎn)樹(shù)杈稱為該節(jié)點(diǎn)的左子樹(shù)，右邊的樹(shù)杈稱為該節(jié)點(diǎn)的右子樹(shù)。的右子樹(shù)。2. 二叉樹(shù)的基本形態(tài)：共二叉

3、樹(shù)的基本形態(tài)：共5種種3. 二叉樹(shù)與一般樹(shù)的區(qū)別：二叉樹(shù)與一般樹(shù)的區(qū)別：一般樹(shù)一般樹(shù)二叉樹(shù)二叉樹(shù)樹(shù)中至少有一個(gè)根節(jié)樹(shù)中至少有一個(gè)根節(jié)點(diǎn)（點(diǎn)（n0）可以一個(gè)根節(jié)點(diǎn)都沒(méi)可以一個(gè)根節(jié)點(diǎn)都沒(méi)有（有（n 0）樹(shù)的度樹(shù)的度0樹(shù)的度樹(shù)的度2不要求子樹(shù)木順序不要求子樹(shù)木順序（無(wú)序樹(shù)）（無(wú)序樹(shù)）子樹(shù)有左、右之分子樹(shù)有左、右之分（有序樹(shù)）（有序樹(shù)）4. 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)性質(zhì)性質(zhì)1：二叉樹(shù)的第：二叉樹(shù)的第 i 層上最多有層上最多有2i-1個(gè)節(jié)點(diǎn)（個(gè)節(jié)點(diǎn)（i ）；）；性質(zhì)性質(zhì)2：高度為：高度為 k 的二叉樹(shù)最多有的二叉樹(shù)最多有2k-1個(gè)節(jié)點(diǎn)（個(gè)節(jié)點(diǎn)（k ） ；性質(zhì)性質(zhì)3：任意一顆二叉樹(shù)中，如果沒(méi)有孩子的節(jié)點(diǎn)個(gè)

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

5、度為單選）一個(gè)深度為 k 的完全二叉樹(shù)中的完全二叉樹(shù)中節(jié)點(diǎn)數(shù)至少有（節(jié)點(diǎn)數(shù)至少有（ ）。）。A 2k B 2k-1 C 2k+1 D 2k-1例例10-1 試寫(xiě)出具有試寫(xiě)出具有3個(gè)節(jié)點(diǎn)的所有不同形態(tài)的樹(shù)和個(gè)節(jié)點(diǎn)的所有不同形態(tài)的樹(shù)和二叉樹(shù)。二叉樹(shù)。二叉樹(shù)有五種：二叉樹(shù)有五種：樹(shù)有樹(shù)有2種：種：6. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)順序存儲(chǔ)操作步驟為：操作步驟為： step1：現(xiàn)將二叉樹(shù)變成完全二叉樹(shù)（給有關(guān)節(jié)點(diǎn)補(bǔ)：現(xiàn)將二叉樹(shù)變成完全二叉樹(shù)（給有關(guān)節(jié)點(diǎn)補(bǔ)夠兩個(gè)孩子，所補(bǔ)節(jié)點(diǎn)為虛擬節(jié)點(diǎn)，僅占個(gè)空間）夠兩個(gè)孩子，所補(bǔ)節(jié)點(diǎn)為虛擬節(jié)點(diǎn)，僅占個(gè)空間） step2：將這個(gè)完全二叉樹(shù)中各節(jié)點(diǎn)從上到下，逐

6、層：將這個(gè)完全二叉樹(shù)中各節(jié)點(diǎn)從上到下，逐層由左向右一次存放到計(jì)算機(jī)連續(xù)空間中。由左向右一次存放到計(jì)算機(jī)連續(xù)空間中。例例10-2：例例10-3 一個(gè)深度為一個(gè)深度為K且只有且只有K個(gè)節(jié)點(diǎn)的二叉樹(shù)順序存儲(chǔ)個(gè)節(jié)點(diǎn)的二叉樹(shù)順序存儲(chǔ)最多需要多少個(gè)存儲(chǔ)空間，最少需要多少個(gè)。最多需要多少個(gè)存儲(chǔ)空間，最少需要多少個(gè)。（2）完全二叉樹(shù)節(jié)點(diǎn)順序編號(hào)的意義）完全二叉樹(shù)節(jié)點(diǎn)順序編號(hào)的意義例例10-4 一個(gè)完全二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)為一個(gè)完全二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)為1000，則，則n0、n1、n2和高度和高度h各為多少各為多少?6. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)（1）二叉樹(shù)）二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)中，每個(gè)節(jié)點(diǎn)有鏈?zhǔn)酱鎯?chǔ)中，

7、每個(gè)節(jié)點(diǎn)有3個(gè)成員（域）個(gè)成員（域） 6. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)（2）二叉樹(shù)）二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)類型的定義鏈?zhǔn)酱鎯?chǔ)類型的定義例例10-51. 中序中序遍歷遍歷如果二叉樹(shù)不為空，則依次執(zhí)行如下操作：如果二叉樹(shù)不為空，則依次執(zhí)行如下操作：（1）先：）先：中序遍歷中序遍歷左子樹(shù)；左子樹(shù)；（2）再：）再：訪問(wèn)訪問(wèn)根節(jié)點(diǎn)；根節(jié)點(diǎn)；（3）最后：）最后：中序遍歷中序遍歷右子樹(shù)。右子樹(shù)。 二叉樹(shù)的遍歷：按照一定的順序訪問(wèn)樹(shù)中所有節(jié)點(diǎn)，二叉樹(shù)的遍歷：按照一定的順序訪問(wèn)樹(shù)中所有節(jié)點(diǎn)，而且每個(gè)節(jié)點(diǎn)僅被訪問(wèn)一次的操作。而且每個(gè)節(jié)點(diǎn)僅被訪問(wèn)一次的操作。例：如圖所示二叉樹(shù)，試寫(xiě)出對(duì)其例：如圖所示二

8、叉樹(shù)，試寫(xiě)出對(duì)其中序中序遍歷的結(jié)果。遍歷的結(jié)果。中序遍歷結(jié)果：中序遍歷結(jié)果： DBGEHACIF中中序遍歷的算法描述序遍歷的算法描述1. 先序先序遍歷遍歷如果二叉樹(shù)不為空，則依次執(zhí)行如下操作：如果二叉樹(shù)不為空，則依次執(zhí)行如下操作：（1）先：）先：訪問(wèn)訪問(wèn)根節(jié)點(diǎn)；根節(jié)點(diǎn)；（2）再：）再：先序遍歷先序遍歷左子樹(shù)；左子樹(shù)；（3）最后：）最后：先序遍歷先序遍歷右子樹(shù)。右子樹(shù)。例：如圖所示二叉樹(shù)，試寫(xiě)出對(duì)其例：如圖所示二叉樹(shù)，試寫(xiě)出對(duì)其先序先序遍歷的結(jié)果。遍歷的結(jié)果。先序遍歷結(jié)果：先序遍歷結(jié)果：ABDEGHCFI1. 后序后序遍歷遍歷如果二叉樹(shù)不為空，則依次執(zhí)行如下操作：如果二叉樹(shù)不為空，則依次執(zhí)行如下

9、操作：（1）先：）先：后序遍歷后序遍歷左子樹(shù)；左子樹(shù)；（2）再：）再：后序遍歷后序遍歷右子樹(shù)；右子樹(shù)；（3）最后：）最后：訪問(wèn)訪問(wèn)根節(jié)點(diǎn)根節(jié)點(diǎn) 。例：如圖所示二叉樹(shù)，試寫(xiě)出對(duì)其例：如圖所示二叉樹(shù)，試寫(xiě)出對(duì)其后序后序遍歷的結(jié)果。遍歷的結(jié)果。后序遍歷結(jié)果：后序遍歷結(jié)果：DGHEBIFCA結(jié)論：由結(jié)論：由先序和中序先序和中序或或后序和中序后序和中序遍歷結(jié)果，可以確遍歷結(jié)果，可以確定唯一的一棵二叉樹(shù)。定唯一的一棵二叉樹(shù)。口訣：口訣：先序后序定樹(shù)根；先序后序定樹(shù)根；中序區(qū)分左和右。中序區(qū)分左和右。例：（例：（2010.4）已知二叉樹(shù)的）已知二叉樹(shù)的后序后序遍歷序列是遍歷序列是dabec，中序中序遍歷序列

10、是遍歷序列是debac，它的前序遍歷序列，它的前序遍歷序列是是 。例例10-7 已知二叉樹(shù)的已知二叉樹(shù)的后序后序遍歷序列和遍歷序列和中序中序遍歷序列結(jié)遍歷序列結(jié)果分別是果分別是DGHEBIFCA和和DBGEHACIF，試確定這，試確定這個(gè)二叉樹(shù)。個(gè)二叉樹(shù)。一、一、 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)1、雙親靜態(tài)鏈表存儲(chǔ)法、雙親靜態(tài)鏈表存儲(chǔ)法序號(hào)節(jié)點(diǎn)雙親0A-11B02C03D04E25F2一、一、 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)2、孩子鏈表存儲(chǔ)法、孩子鏈表存儲(chǔ)法datanext0A1231B2C453D4E5F1）樹(shù)的孩子兄弟表示樹(shù)的孩子兄弟表示口訣：豎線連接口訣：豎線連接左左孩子，橫線連接孩子，橫線連接親親

11、兄弟。兄弟。例：將如圖所示樹(shù)，用樹(shù)的孩子兄弟表示。例：將如圖所示樹(shù)，用樹(shù)的孩子兄弟表示。3、孩子兄弟鏈?zhǔn)酱鎯?chǔ)法、孩子兄弟鏈?zhǔn)酱鎯?chǔ)法2）用鏈連接各節(jié)點(diǎn)。用鏈連接各節(jié)點(diǎn)。3、孩子兄弟鏈?zhǔn)酱鎯?chǔ)法、孩子兄弟鏈?zhǔn)酱鎯?chǔ)法1. 樹(shù)變二叉樹(shù)樹(shù)變二叉樹(shù)step1:寫(xiě)出樹(shù)的孩子兄弟表示；寫(xiě)出樹(shù)的孩子兄弟表示；step2:將豎線變成左子樹(shù)，橫向變成右子樹(shù)。將豎線變成左子樹(shù)，橫向變成右子樹(shù)。一、一、 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)3. 樹(shù)的遍歷樹(shù)的遍歷樹(shù)的遍歷有：先序和后序樹(shù)的遍歷有：先序和后序注意：注意：樹(shù)的樹(shù)的先序先序遍歷結(jié)果與對(duì)應(yīng)二叉樹(shù)的遍歷結(jié)果與對(duì)應(yīng)二叉樹(shù)的先序先序遍歷結(jié)果相同；遍歷結(jié)果相同；樹(shù)的樹(shù)的后序后序遍歷結(jié)

12、果與對(duì)應(yīng)二叉樹(shù)的遍歷結(jié)果與對(duì)應(yīng)二叉樹(shù)的中序中序遍歷結(jié)果相同。遍歷結(jié)果相同。4. 森林變二叉樹(shù)森林變二叉樹(shù)step1: 把構(gòu)成森林的每一棵樹(shù)變成二叉樹(shù)；把構(gòu)成森林的每一棵樹(shù)變成二叉樹(shù)；step2: 依次把后一棵二叉樹(shù)連在前一棵二叉樹(shù)依次把后一棵二叉樹(shù)連在前一棵二叉樹(shù)根根的的右子樹(shù)上。右子樹(shù)上。4. 森林變二叉樹(shù)（續(xù)）森林變二叉樹(shù)（續(xù)）5. 森林的遍歷森林的遍歷森林的遍歷有：先序和后序森林的遍歷有：先序和后序注意：注意：森林的森林的先序先序遍歷結(jié)果與對(duì)應(yīng)二叉樹(shù)的遍歷結(jié)果與對(duì)應(yīng)二叉樹(shù)的先序先序遍歷結(jié)果相同；遍歷結(jié)果相同；森林的森林的后序后序遍歷結(jié)果與對(duì)應(yīng)二叉樹(shù)的遍歷結(jié)果與對(duì)應(yīng)二叉樹(shù)的中序中序遍歷結(jié)果

13、相同。遍歷結(jié)果相同。例例.（2010.4解答）已知下圖所示的二叉樹(shù)，要求：解答）已知下圖所示的二叉樹(shù)，要求：（1）將該二叉樹(shù)還原成森林；）將該二叉樹(shù)還原成森林；（2）寫(xiě)出森林的先根遍歷序列和后根遍歷序列）寫(xiě)出森林的先根遍歷序列和后根遍歷序列解（解（1）將該二叉樹(shù)還原成森林；）將該二叉樹(shù)還原成森林；（2）寫(xiě)出森林的先根遍歷序列和后根遍歷序列）寫(xiě)出森林的先根遍歷序列和后根遍歷序列解（解（1）將該二叉樹(shù)還原成森林；）將該二叉樹(shù)還原成森林；解（解（1）將該二叉樹(shù)還原成森林；）將該二叉樹(shù)還原成森林；解（解（2）先根遍歷序列：）先根遍歷序列：abdgcefhij后根遍歷序列：后根遍歷序列：bgdaecih

14、jf1. 幾個(gè)基本術(shù)語(yǔ)幾個(gè)基本術(shù)語(yǔ) （1）第）第i個(gè)個(gè)葉子節(jié)點(diǎn)的葉子節(jié)點(diǎn)的權(quán)值權(quán)值Wi：給第：給第i個(gè)節(jié)點(diǎn)所賦予的個(gè)節(jié)點(diǎn)所賦予的重要程度值；重要程度值； （2）第）第i個(gè)葉子節(jié)點(diǎn)的個(gè)葉子節(jié)點(diǎn)的路徑長(zhǎng)度路徑長(zhǎng)度Li：從根到第：從根到第i個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)所經(jīng)路徑的段數(shù)；所經(jīng)路徑的段數(shù)； （3）第）第i個(gè)葉子節(jié)點(diǎn)的個(gè)葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度WPLi： WPLi=WiLi； （4）樹(shù)的）樹(shù)的帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度WPL：等于該樹(shù)中所有葉子：等于該樹(shù)中所有葉子 的帶權(quán)路徑長(zhǎng)度之和。的帶權(quán)路徑長(zhǎng)度之和。2.就是帶權(quán)路徑長(zhǎng)度為就是帶權(quán)路徑長(zhǎng)度為最小最小的的二叉樹(shù)二叉樹(shù)。3.step1：將該樹(shù)的葉子權(quán)

15、值：將該樹(shù)的葉子權(quán)值由小到大由小到大進(jìn)行排序；進(jìn)行排序；step2：從所排序中取出兩個(gè)最小的權(quán)值：從所排序中取出兩個(gè)最小的權(quán)值 和和 構(gòu)造構(gòu)造二叉樹(shù)，該二叉樹(shù)的根節(jié)點(diǎn)為二叉樹(shù)，該二叉樹(shù)的根節(jié)點(diǎn)為W（ ）iW1iW1iiWWWstep3：從權(quán)值序列中劃去：從權(quán)值序列中劃去 和和 。劃去后，如果。劃去后，如果序列為空，說(shuō)明所要求的二叉樹(shù)已經(jīng)構(gòu)成；否則，序列為空，說(shuō)明所要求的二叉樹(shù)已經(jīng)構(gòu)成；否則，將將W加入權(quán)值序列中，重復(fù)加入權(quán)值序列中，重復(fù)step1step3。iW1iW例：（例：（09.4月）給定一組權(quán)值：月）給定一組權(quán)值：4、1、12、2、10，構(gòu)，構(gòu)造對(duì)應(yīng)的造對(duì)應(yīng)的step1：按權(quán)值：按權(quán)值

16、由小到大由小到大排序：排序：1step2：取兩個(gè)最小權(quán)值，：取兩個(gè)最小權(quán)值，、2 、 4 、1012、3構(gòu)建一顆二叉樹(shù)構(gòu)建一顆二叉樹(shù)12step3：從原序列中劃去：從原序列中劃去1和和2將將3插入到序列中插入到序列中3step3：重復(fù)步驟：重復(fù)步驟1347710171217294.（1）（2）（3）（4）5. 哈夫曼編碼哈夫曼編碼（1）定義：長(zhǎng)度最小的二進(jìn)制串電文編碼。）定義：長(zhǎng)度最小的二進(jìn)制串電文編碼。（2）求哈夫曼編碼的步驟：）求哈夫曼編碼的步驟：step1：構(gòu)造哈夫曼樹(shù)構(gòu)造哈夫曼樹(shù)（依據(jù)：以電文中各字符出現(xiàn)的（依據(jù)：以電文中各字符出現(xiàn)的次數(shù)為權(quán)值）；次數(shù)為權(quán)值）；step2：構(gòu)造哈夫曼編碼樹(shù)構(gòu)造哈夫曼編碼樹(shù)（方法：（方法：在在哈夫曼樹(shù)哈夫曼樹(shù)左子左子樹(shù)的邊上添樹(shù)的邊上添0，右子樹(shù)的邊上添，右子樹(shù)的邊上添1）；）；step3：求各字符的哈夫曼編碼求各字符的哈夫曼編碼（從根到各字符節(jié)點(diǎn)（從根到各字符節(jié)點(diǎn)路徑上的二進(jìn)制序列路徑上的二進(jìn)制序列）；）；例：（例：（2008.04）假設(shè)字符）假設(shè)字符a，b，c，d，e，f使用的頻率分別為使用的頻率分別為0.