ds上機考試題目概述第60a76413c

1、Algorithms and Data Structures樹第六章學習要點:理解樹的定義和與樹相關(guān)的結(jié)點、度、路徑等術(shù)語。理解樹是一個非線性層次數(shù)據(jù)結(jié)構(gòu)。掌握樹的前序遍歷、中序遍歷和后序遍歷方法。了解樹的父結(jié)點數(shù)組表示法。了解樹的兒子鏈表表示法。了解樹的左兒子右兄弟表示法。理解二叉樹和ADT二叉樹的概念。了解二叉樹的順序結(jié)構(gòu)。了解二叉樹的結(jié)點度表示法。掌握用指針實現(xiàn)二叉樹的方法。理解線索二叉樹結(jié)構(gòu)及其適用范圍。2011/10/211Algorithms and Data Structures樹第六章樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)6.1 樹的定義定義遞歸定義(1)單個

2、結(jié)點是一棵樹，該結(jié)點就是樹根。(2)設T1,T2，,Tk都是樹，它們的根結(jié)點分別為n1,n2nk,而n是另一個結(jié)點且以n1,n2nk為兒子，則T1,T2，,Tk和n構(gòu)成一棵新樹。結(jié)點n就是新樹的根。稱n1,n2nk為一組兄弟結(jié)點。還稱T1,T2，,Tk為結(jié)點n的子樹。為了方便起見，空集合也看作是樹，稱為空樹，并用來表示。空樹中沒有結(jié)點。2011/10/212Algorithms and Data Structures只有根結(jié)點的樹A有子樹的樹根ABCDEFGHIJKLM子樹2011/10/213Algorithms and Data Structures基本術(shù)語結(jié)點表示樹中的元素，包括數(shù)據(jù)項及

3、若干指向其子樹的分支結(jié)點的度結(jié)點的兒子結(jié)點個數(shù) 樹的度一棵樹中最大的結(jié)點度數(shù)葉結(jié)點度為0的結(jié)點分枝結(jié)點度不為0的結(jié)點路徑若存在樹中的一個節(jié)點序列k1，k2，kj，使得結(jié)點ki是ki+1的父結(jié)點(1i1，則其雙親是i/2如果2in，則結(jié)點i無左孩子；如果2in，則其左孩子是2i如果2i+1n，則結(jié)點i無右孩子；如果2i+1n，則其右孩子是2i+12011/10/2123Algorithms and Data StructuresADT二叉樹6.56.5.1 ADT二叉樹用來存放有二叉樹結(jié)構(gòu)的數(shù)據(jù)集ADT二叉樹支持的主要基本運算：(1)BinaryInit()創(chuàng)建一棵空二叉樹。(2)BinaryE

4、mpty()判斷給定的二叉樹是否為空。(3)Root(T)返回給定二叉樹的根結(jié)點標號。MakeTree(x,T,L,R)以x為根結(jié)點元素,以L和R分別為左、右子樹,構(gòu)建一棵新的二叉樹T。BreakTree(T,L,R)函數(shù)MakeTree的逆運算，即將二叉樹拆分為根結(jié)點元素，左子樹L和右子樹R等3部分。2011/10/2124Algorithms and Data Structures6.5 ADT二叉樹6.5.1 ADT二叉樹用來存放有二叉樹結(jié)構(gòu)的數(shù)據(jù)集ADT二叉樹支持的主要基本運算(續(xù))(6)PreOrder(visit,t(7)InOrder(visit,t)前序遍歷給定的二叉樹。中序遍

5、歷給定的二叉樹。(8)tOrder(visit,t)后序遍歷給定的二叉樹。(9)PreOut(10)InOut(T)(T)給定的二叉樹的前序列表。給定的二叉樹的中序列表。(11)tOut(T)給定的二叉樹的后序列表。(12)Delete(t)(13)Height(t)刪除給定的二叉樹。求給定的二叉樹的高度。(14)Size(t)2011/10/21求給定的二叉樹的結(jié)點數(shù)。25Algorithms and Data Structures6.5 ADT二叉樹6.5.2 ADT二叉樹的實現(xiàn)6.5.2.1用順序結(jié)構(gòu)實現(xiàn)(一種無邊表示)適用的對象：近似滿二叉樹基本想法：若將所有的結(jié)點按層自上而下每層自左

6、至右，從1開始編號。123456789101112ABC2011/10/21JK26DEFGHIAlgorithms and Data Structures不適用的例子：abcdef1a2b3c4d5e6070809010f1102011/10/2127Algorithms and Data Structures6.5 ADT二叉樹6.5.2 ADT二叉樹的實現(xiàn)6.5.2.2二叉樹的結(jié)點度表示法(另一種無邊表示)基本想法：若將所有的結(jié)點按后序列表從1開始,并在每個結(jié)點中附加一個0到3之間的整數(shù)，以表示該結(jié)點的分叉特征。該整數(shù)為0時，表示相應的結(jié)點無兒子；為1時，表示相應結(jié)點只有左兒子；為2時，

7、表示相應結(jié)點只有右兒子；為3時，表示相應結(jié)點既有左兒子又有右兒子。那么,結(jié)點之間有如下隱含關(guān)系：若結(jié)點i有右兒子，則i-1一定是其右兒子結(jié)點。另一方面，結(jié)點i的左兒子結(jié)點必在i之前，而其父結(jié)點必在i之后。照此，二叉樹可以用記錄數(shù)組來表示2011/10/2128Algorithms and Data Structures6.5 ADT二叉樹ADT二叉樹的實現(xiàn)二叉樹的結(jié)點度表示法(另一種無邊表示)6.5.26.5.2.2例2011/10/2129Algorithms and Data Structures6.5 ADT二叉樹6.5.2 ADT二叉樹的實現(xiàn)6.5.2.3二叉樹的指針實現(xiàn)帶兩個指針的結(jié)

8、點的實現(xiàn)P116-1202011/10/2130Algorithms and Data Structures前序遍歷:AACBBCD先序遍歷序列：ABDCD2011/10/2131DLRDLRDLRDLRAlgorithms and Data Structures中序遍歷:AACBDBC中序遍歷序列：BDACD2011/10/2132LDRLDRL DRLDRAlgorithms and Data Structures后序遍歷:AACBBDC后序遍歷序列： DB CAD2011/10/2133LRDLRDL RDLRDAlgorithms and Data Structures二叉樹的應用6.

9、5.1樹(Huffman)帶權(quán)路徑長度最短的樹定義路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支結(jié)點間的路徑路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和這兩個樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和n w kwpl記作：klk 1w k 權(quán)值其中：l k 結(jié)點到根的路徑長度Huffman樹設有n個權(quán)值w1,w2,wn，構(gòu)造一棵有 n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫Huffman樹1/10/2120134Algorithms and Data Structures有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹例nWP

10、k1a7b5c2d4c2WPL=7*2+5*2+2*2+4*2=364da7a7b5b5WPL=7*3+5*3+2*1+4*2=46cd24WPL=7*1+5*2+2*3+4*3=35352011/10/21Algorithms and Data Structures構(gòu)造Huffman樹的方法Huffman算法構(gòu)造Huffman樹步驟根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中重復上述兩步，直到只含一棵樹為止，這棵樹即樹2011/10/2136Alg