非線性數(shù)據(jù)結構《計算機軟件基礎》01.樹和二叉樹02.哈夫曼樹03.圖主要內(nèi)容04.最小生成樹和拓撲排序本章重點難點本章重點：二叉樹的遍歷；二叉樹的性質(zhì)；哈夫曼樹；圖的存儲結構；圖的遍歷；圖的連通分量和生成樹的區(qū)別；Kruskal算法；拓撲排序方法。本章難點：二叉樹的遍歷；Kruskal算法；拓撲排序方法。01樹和二叉樹1.樹的基本概念

樹形結構表示方法的多樣化a)自然表示法；b)是集合表示法；c)是層次表示法樹的基本術語1）結點的度：結點擁有的子樹數(shù)。2）樹的度：樹內(nèi)各結點的度的最大值。3）葉子結點（終端結點）：度為0的結點。4）孩子和雙親結點：結點的子樹的根稱為該結點的孩子，相應地，該結點稱為孩子的雙親。5）兄弟結點：用一雙親結點的孩子結點互稱為兄弟。6）樹的高度（深度）：樹的層數(shù)（根為第1層）2.二叉樹

二叉樹是一種特殊的樹形結構

特點：樹中每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點），并且二叉樹的子樹有左、右之分，其次序不能任意顛倒。a)空樹c)右子樹為空b)僅有根結點d)左子樹為空e)左右子樹皆不為空1）樹和二叉樹的區(qū)別樹二叉樹同一棵樹，不同的二叉樹2）二叉樹的性質(zhì)

滿二叉樹：高度為k的二叉樹，若具有2k-1個節(jié)點，稱為滿二叉樹。完全二叉樹：假設二叉樹具有n個節(jié)點，對二叉樹的節(jié)點進行編號，若二叉樹各節(jié)點與深度相同的滿二叉樹中編號相同的1~n個各節(jié)點一一對應，則稱為完全二叉樹。

3.二叉樹的存儲結構存儲元素，表示關系?？梢皂樞虼鎯?，也可以鏈式存儲。但：存儲元素簡單，表示關系困難！順序存儲分配連續(xù)空間，依次存放樹的各個元素。如何依次存放？例如，可約定：從上至下、從左至右將樹的節(jié)點依次存入連續(xù)內(nèi)存空間。優(yōu)點：簡單缺點：不能很好地表示出關系！123456789abcdefghiabcdeghif123456789鏈式存儲用任意的存儲空間，存放數(shù)據(jù)元素，在存儲元素的同時存放其相關元素的地址。二叉鏈表存儲結構的類型定義如下：typedefcharElemType;structbtlnode{ElemTypedata;structbtlnode*lchild,*rchild;};思考：其他鏈式存儲方法？？？4.二叉樹的遍歷二叉樹的遍歷是指按照某種順序訪問二叉樹中各個結點，使得每個結點被訪問一次且僅被訪問一次。遍歷方式：由于元素之間的關系復雜了，按什么樣的順序訪問數(shù)據(jù)元素？人們約定一個原則。深度優(yōu)先遍歷：廣度優(yōu)先遍歷1）深度優(yōu)先遍歷：中序遍歷其遍歷過程為：中序遍歷其左子樹；訪問根節(jié)點；中序遍歷其右子樹。voidInOrderTraversal(BinTreeBT){if(BT){InOrderTraversal(BT->Left);printf(“%d”,BT->Data);InOrderTraversal(BT->Right);}}中序遍歷結果序列為：DBGEHACIF2）深度優(yōu)先遍歷：先序遍歷voidPreOrderTraversal(BinTreeBT){if(BT){printf(“%d”,BT->Data);PreOrderTraversal(BT->Left);PreOrderTraversal(BT->Right);}}其遍歷過程為：訪問根節(jié)點；先序遍歷其左子樹；先序遍歷其右子樹。先序遍歷結果序列為：ABDEGHCFI3）深度優(yōu)先遍歷：后序遍歷voidPostOrderTraversal(BinTreeBT){if(BT){PostOrderTraversal(BT->Left);PostOrderTraversal(BT->Right);printf(“%d”,BT->Data);}}其遍歷過程為：后序遍歷其左子樹；后序遍歷其右子樹；訪問根節(jié)點。后序遍歷結果序列為：DGHEBIFCA訪問一個元素后，再依次訪問其各個后繼。對于二叉樹，從第1層開始，逐層訪問其元素，每一層從左向右。先訪問的元素，它們的孩子也先訪問！層次序遍歷結果序列為：ABCDEFGHI4）廣度優(yōu)先遍歷：層序（層次）遍歷用隊列數(shù)據(jù)結構輔助來完成層次遍歷。例9-6已知一個二叉樹的后序遍歷和中序遍歷結果分別為：DGHEBIFCA和DBGEHACIF，試確定該二叉樹。第1步：由后序遍歷結果確定整個二叉樹根為A，由中序結果確定A的左、右子樹中序遍歷結果分別為DBGEH和CIF。第2步：確定A的左子樹。第3步：確定A的右子樹。5.樹和森林1）樹的存儲表示①雙親表示法②孩子表示法③孩子兄弟表示法2)樹與二叉樹將一棵樹轉(zhuǎn)換成二叉樹的方法是：①加線。在兄弟之間加一連線。②抹線。對每個結點，除了其左孩子外，去除其與其余孩子之間的關系。③旋轉(zhuǎn)。以樹根為軸心，把孩子兄弟表示順時針旋轉(zhuǎn)45°。3)森林

①將森林中各棵樹轉(zhuǎn)換成二叉樹。②依次把后一個二叉樹連在前一個二叉樹根的右子樹上。02哈夫曼樹1.哈夫曼樹的概念路徑和路徑長度從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。路徑上的分支條數(shù)稱為路徑長度。哈夫曼樹概念帶權路徑長度最小的二叉樹，也稱為最優(yōu)二叉樹。樹的路徑長度從樹的根結點到每一結點的路徑長度之和。結點的權：樹中結點賦予一個具有某種含義的數(shù)值樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和。2.哈夫曼樹的構造例9-8

求圖中給出的四個權值9、5、2、4的哈夫曼樹及帶權路徑長度WPL。此時，WPL=9*1+5*2+(2+4)*3=37。

同一組權值構造的哈夫曼樹不唯一，但WPL相同。權值越大的結點離根結點越近。3.哈夫曼樹的性質(zhì)4.哈夫曼樹的應用例9-9

某工廠對其產(chǎn)品質(zhì)量進行自動檢測，并根據(jù)檢測結果劃分產(chǎn)品的質(zhì)量等級。等級標準如表所示。試設計一個分類算法，根據(jù)產(chǎn)品的檢測結果d值能快速確定其質(zhì)量等級。等級EDCBA檢測值dd<55≤d<66≤d<77≤d<88≤d百分比0.10.20.350.250.1例9-10

已知一串電文內(nèi)容如下：AACBDADACBAADCADCADA。試為電文中各字符設計最優(yōu)的二進制電文編碼，即哈夫曼編碼。求哈夫曼編碼的方法是：①以電文中各字符出現(xiàn)的次數(shù)為權值，構造哈夫曼樹，該樹的葉子結點表示電文中的一個字符。上述電文中A、B、C、D四個字符出現(xiàn)的次數(shù)依次為9、2、4、5。所構造的哈夫曼樹如圖a)所示。

②將哈夫曼樹左子樹邊上置0，右子樹邊上置1。電文中各字符的哈夫曼編碼為：從根到葉子（字符）結點路徑上的二進制序列。此樹稱為哈夫曼編碼樹，如圖b)所示。A——1、B——010、C——011、D——00。利用哈夫曼樹為電文中各字符設計最優(yōu)的二進制電文編碼。03圖1.圖的概念圖G由頂點和邊組成，G=(V,E)。V是頂點的有窮非空集合，E是邊（弧）的有窮集合。1）圖

請在圖中分別舉例：鄰接點？度？路徑？回路？2.圖的存儲結構鄰接矩陣是用矩陣表示圖中各頂點之間的鄰接關系和權值，是圖的一種順序存儲結構。鄰接表是圖的一種順序存儲與鏈式存儲結合的存儲結構，由單鏈表組成，每個表頭結點對應圖中的一個頂點，表結點存放表頭結點的鄰接點。1）鄰接矩陣2）鄰接表3.圖的遍歷深度優(yōu)先遍歷是樹的先序遍歷，從A頂點出發(fā)，先訪問A點，再訪問A的第1個尚未訪問的鄰接點B，再訪問B的第1個尚未訪問的鄰接點C，以此類推，直到所有頂點訪問完畢。1）深度優(yōu)先遍歷圖的廣度優(yōu)先遍歷類似于樹的按層次序遍歷。從圖中某頂點A出發(fā)，在訪問了A之后依次訪問A的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，先被訪問的頂點其鄰接點也先被訪問，直至圖中所有頂點都被訪問到為止。結果不唯一。2）廣度優(yōu)先遍歷04最小生成樹和拓撲排序1.生成樹和最小生成樹

1）圖的連通分量連通圖：如果圖中任意兩頂點都是連通的。連通分量：無向圖的極大連通子圖稱為連通分量。連通分量的概念包含以下要點：①子圖：連通分量應該是原圖的子圖；②連通：連通分量本身應該是連通的；③極大頂點數(shù)：連通子圖包含有極大頂點數(shù)，即再加入其他頂點將會導致子圖不連通；④極大邊數(shù)：具有極大頂點數(shù)的連通子圖包含依附于這些頂點的所有邊。

3）最小生成樹

如果無向連通圖的邊上帶有權值，那么它的生成樹中必有一棵邊的權值總和最小的生成樹，稱這棵生成樹為最小生成樹。當然，對任意一個帶權的連通圖來說，最小生成樹也未必是唯一的。4）Kruskal算法Kruskal算法是一種按照圖中邊的權值遞增的順序構造最小生成樹的方法。基本思路是對一個有n個頂點的連通圖G=(V,E)，令最小生成樹的初值狀態(tài)為只有n個頂點而無任何邊的非連通圖T，此時圖中每個頂點自成一個連通分量。按照權值遞增的順序依次選擇E中的邊，若該邊依附于T中兩個不同的連通