數(shù)據(jù)結構（Java語言實現(xiàn)） 課件 陳銳 第5、6章 樹和二叉樹、圖

第5章樹和二叉樹結構Java實據(jù)現(xiàn)數(shù)目錄CONTENTS5.1

樹的定義和抽象數(shù)據(jù)類型5.2二叉樹的定義、性質(zhì)5.3二叉樹的遍歷5.6并查集5.4二叉樹的線索化5.5樹、森林與二叉樹5.7哈夫曼樹5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。樹（Tree）是n(n≥0)個結點的有限集合。其中，當n=0時，稱為空樹。當n>0時，稱為非空樹，該集合滿足以下條件：（1）有且只有一個稱為根（root）的結點。（2）當n>1時，其余n-1個結點可以劃分為m個有限集合T1、T2、…、Tm，且這m個有限集合不相交，其中Ti（1≤i≤m）又是一棵樹，稱為根的子樹。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。圖5.1給出了一棵樹的邏輯結構，它如同一棵倒立的樹。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。樹的結點：包含一個數(shù)據(jù)元素及若干指向子樹分支的信息。結點的度：一個結點擁有子樹的個數(shù)稱為結點的度。例如，結點C有3個子樹，度為3。葉子結點：也稱為終端結點，沒有子樹的結點也就是度為零的結點稱為葉子結點。分支結點：也稱為非終端結點，度不為零的結點稱為非終端結點。孩子結點：一個結點的子樹的根結點稱為孩子結點。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。雙親結點：也稱父結點，如果一個結點存在孩子結點，則該結點就稱為孩子結點的雙親結點。子孫結點：在一個根結點的子樹中的任何一個結點都稱為該根結點的子孫結點。例如，{G,H,I,M,N}是C的子樹，子樹中的結點G、H、I、M和N都是C的子孫結點。祖先結點：從根結點開始到達一個結點，所經(jīng)過的所有分支結點，都稱為該結點的祖先結點。例如，N的祖先結點為A、C和I。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。兄弟結點：一個雙親結點的所有孩子結點之間互相稱為兄弟結點。例如，E和F是B的孩子結點，因此，E和F互為兄弟結點。樹的度：樹中所有結點的度的最大值。例如，圖5.1中右邊的樹的度為3，因為結點C的度為3，該結點的度是樹中擁有最大的度的結點。結點的層次：從根結點開始，根結點為第一層，根結點的孩子結點為第二層，依此類推，如果某一個結點是第L層，則其孩子結點位于第L+1層。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。樹的深度：也稱為樹的高度，樹中所有結點的層次最大值稱為樹的深度。例如，圖5.1中右邊的樹的深度為4。有序樹：如果樹中各個子樹的次序是有先后次序的，則稱該樹為有序樹。無序樹：如果樹中各個子樹的次序是沒有先后次序，則稱該樹為無序樹。森林：m棵互不相交的樹構成一個森林。如果把一棵非空的樹的根結點刪除，則該樹就變成了一個森林，森林中的樹由原來的根結點各個子樹構成。5.1樹的定義和抽象數(shù)據(jù)類型5.1.2樹的邏輯表示唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。（1）樹形表示法。（2）文氏圖表示法。（3）廣義表表示法。(A(B(E(K,L),F),C(G(M),H,I(N)),D(J)))（4）凹入表示法。5.1樹的定義和抽象數(shù)據(jù)類型5.1.3樹的抽象數(shù)據(jù)類型唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。ADTTree{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關系R：若D為空集，則稱為空樹。若D僅含一個數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關系H下無前驅(qū)；（2）若D-{root}≠￠，則存在D-{root}的一個劃分D1，D2，…，Dm(m>0)，對任意的j≠k(1≤j,k≤m)有Dj∩Dk=￠，且對任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H；（3）對應于D-{root}的劃分，H-{<root,x1>},…,<root,xn>}有唯一的一個劃分H1，H2，…，Hm(m>0)，對任意的j≠k(1≤j,k≤m)有Dj∩Dk=￠，且對任意的i(1≤i≤m)，Hi是Di上的二元關系，(Di,{Hi})是一棵符合本定義的樹，稱為root的子樹。5.1樹的定義和抽象數(shù)據(jù)類型5.1.3樹的抽象數(shù)據(jù)類型唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作?；静僮鳎海?）InitTree(&T)

初始條件：樹T不存在。操作結果：構造空樹T。（2）DestroyTree(&T)

初始條件：樹T存在。操作結果：銷毀樹T。（3）CreateTree(&T)

初始條件：樹T存在。操作結果：根據(jù)給定條件構造樹T。5.1樹的定義和抽象數(shù)據(jù)類型5.1.3樹的抽象數(shù)據(jù)類型唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。（10）DeleteChild(&T,p,i)

初始條件：樹T存在，p指向T中某個結點，1≤i≤d，d為p所指向結點的度。操作結果：將p所指向的結點的第i棵子樹刪除。如果刪除成功，返回1，否則返回0。（11）TraverseTree(T)

初始條件：樹T存在。操作結果：按照某種次序?qū)的每個結點訪問且僅訪問一次。（12）TreeDepth(T)

初始條件：樹T存在。操作結果：若樹T非空，返回樹的深度，如果是空樹，返回0。}ADTTree5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.1二叉樹的定義二叉樹（BinaryTree）是另一種樹結構，它的特點是每個結點最多只有兩棵子樹。樹可以轉(zhuǎn)化為唯一一棵二叉樹，二叉樹可以簡化樹的處理。下面給出二叉樹的五種基本形態(tài)，如圖5.4所示。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.1二叉樹的定義一個由12個結點構成的二叉樹如圖5.5所示。F是C的左孩子結點，G是C的右孩子結點，L是G的右孩子結點，G的左孩子結點不存在。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型滿二叉樹和完全二叉樹每層結點都是滿的二叉樹稱為滿二叉樹，即在滿二叉樹中，每一層的結點都具有最大的結點個數(shù)。圖5.6所示就是一棵滿二叉樹。在滿二叉樹中，每個結點的度或者為2，或者為0（即葉子結點），不存在度為1的結點。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型滿二叉樹和完全二叉樹如果一棵二叉樹有n個結點，并且二叉樹的n個結點的結構與滿二叉樹的前n個結點的結構完全相同，則稱這樣的二叉樹為完全二叉樹。完全二叉樹及對應編號如圖5.8所示。而圖5.9所示就不是一棵完全二叉樹。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（1）性質(zhì)1：在二叉樹中，第m(m≥1)層上至多有2m-1個結點（規(guī)定根結點為第一層）。證明：利用數(shù)學歸納法證明。當m=1時，即根結點所在的層次，有2m-1=21-1=20=1，命題成立。假設當m=k時，命題成立，即第k層至多有2k-1個結點。因為在二叉樹中，每個結點的度最大為2，則在第k+1層，結點的個數(shù)最多是第k層的2倍，即2×2k-1=2k-1+1=2k。即當m=k+1時，命題成立。思考：第i層上至少有

1

個結點？5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（2）性質(zhì)2：深度為k(k≥1)的二叉樹至多有2k-1個結點。證明：第i層結點的最多個數(shù)2i-1，將深度為k的二叉樹中的每一層的結點的最大值相加，就得到二叉樹中結點的最大值，因此深度為k的二叉樹的結點總數(shù)至多有：

思考：深度為k時至少有

個結點？k5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（3）性質(zhì)3：對任何一棵二叉樹T，如果葉子結點總數(shù)為n0，度為2的結點總數(shù)為n2，則有n0=n2+1。證明：假設二叉樹中結點總數(shù)為n，度為1的結點總數(shù)為n1。則：n=n0+n1+n2。假設二叉樹的分支數(shù)為Y，有n=Y+1。二叉樹的所有分支都是由度為1和度為2的結點發(fā)出，所以分支數(shù)Y=n1+2×n2。故n=Y+1=n1+2×n2+1。聯(lián)合兩式，得到n0+n1+n2=n1+2×n2+1，即n0=n2+1。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（4）性質(zhì)4：如果完全二叉樹有n個結點，則深度為

log2n

+1。符號表示不大于x的最大整數(shù)。證明：假設具有n個結點的完全二叉樹的深度為k。k層完全二叉樹的結點個數(shù)介于k-1層滿二叉樹與k層滿二叉樹結點個數(shù)之間。根據(jù)性質(zhì)2，k-1層滿二叉樹的結點總數(shù)為n1=2k-1-1，k層滿二叉樹的結點總數(shù)為n2=2k-1。因此有n1<n≤n2，即n1+1≤n<n2+1，又n1=2k-1-1和n2=2k-1，故得到2k-1-1≤n<2k-1，同時對不等式兩邊取對數(shù)，有k-1≤log2n<k。因為k是整數(shù)，k-1也是整數(shù)，所以k-1=

log2n

，即k=

log2n

+1。命題成立。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（5）性質(zhì)5：如果完全二叉樹有n個結點，按照從上到下、從左到右的順序，對二叉樹中的每個結點從1到n進行編號，則對于任意結點i有以下性質(zhì)： 如果i=1，則序號i對應的結點就是根結點，該結點沒有雙親結點。如果i>1，則序號為i的結點的雙親結點的序號為。 如果2×i>n，則序號為i的結點沒有左孩子結點。如果2×i≤n，則序號為i的結點的左孩子結點的序號為2×i。 如果2×i+1>n，則序號為i的結點沒有右孩子結點。如果2×i+1≤n，則序號為i的結點的右孩子結點序號為2×i+1。

一棵完全二叉樹有2000個結點，則其葉結點的個數(shù)是（）。10005.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.3二叉樹的抽象數(shù)據(jù)類型ADTBinaryTree{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關系R：若D=￠，則稱BinaryTree為空二叉樹。若D≠￠，則R={H}，H是如下二元關系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關系H下無前驅(qū)；（2）若D-{root}≠￠，則存在D-{root}={Dl，Dr}，且Dl∩Dr=￠。（3）若Dl≠￠，則Dl中存在唯一的元素xl，<root,xl>∈H，且存在Dl上的關系HlH；若Dr≠￠，則Dr中存在唯一的元素xr，<root,xr>∈H，且存在Dr上的關系HrH；H={<root,xl>,<root,xr>,Hl,Hr}；（4）(Dl，{Hl})是一棵符合本定義的二叉樹，稱為根的左子樹，(Dr,{Hr})是一棵符合本定義的二叉樹，稱為根的右子樹。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.3二叉樹的抽象數(shù)據(jù)類型基本操作P：（1）InitBiTree(&T)

初始條件：二叉樹T不存在。操作結果：構造空二叉樹T。（2）CreateBiTree(&T)

初始條件：給出了二叉樹T的定義。操作結果：創(chuàng)建一棵非空的二叉樹T。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.3二叉樹的抽象數(shù)據(jù)類型（10）PreOrderTraverse(T)

初始條件：二叉樹T存在。操作結果：先序遍歷二叉樹T，即先訪問根結點、再訪問左子樹、最后訪問右子樹，對二叉樹中的每個結點訪問且僅訪問一次。（11）InOrderTraverse(T)

初始條件：二叉樹T存在。操作結果：中序遍歷二叉樹T，即先訪問左子樹、再訪問根結點、最后訪問右子樹，對二叉樹中的每個結點訪問，且僅訪問一次。（12）PostOrderTraverse(T)

初始條件：二叉樹T存在。操作結果：后序遍歷二叉樹T，即先訪問左子樹、再訪問右子樹、最后訪問根結點，對二叉樹中的每個結點訪問，且僅訪問一次。（13）LevelTraverse(T)

初始條件：二叉樹T存在。操作結果：對二叉樹進行層次遍歷。即按照從上到下、從左到右，依次對二叉樹中的每個結點進行訪問。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示1.二叉樹的順序存儲我們已經(jīng)知道，完全二叉樹中每個結點的編號可以通過公式計算得到，因此，完全二叉樹的存儲可以按照從上到下、從左到右的順序依次存儲在一維數(shù)組中。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示對于非完全二叉樹來說，這種存儲方式會浪費內(nèi)存空間的浪費。在最壞的情況下，如果每個結點只有右孩子結點，而沒有左孩子結點，則需要占用2k-1個存儲單元，而實際上，該二叉樹只有k個結點。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示2.二叉樹的鏈式存儲在二叉樹中，每個結點有一個雙親結點和兩個孩子結點。從一棵二叉樹的根結點開始，通過結點的左右孩子地址就可以找到二叉樹的每一個結點。因此二叉樹的鏈式存儲結構包括三個域：數(shù)據(jù)域、左孩子指針域和右孩子指針域。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示為了方便找到結點的雙親結點，在二叉鏈表的存儲結構中增加一個指向雙親結點的指針域parent。這種存儲結構稱為三叉鏈表結點存儲結構。classBiTreeNode//二叉樹的結點類型{chardata;BiTreeNodelchild,rchild;BiTreeNode(chardata)

{this.data=data;lchild=null;rchild=null;}}5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型創(chuàng)建二叉樹算法實現(xiàn)如下：BiTreeNodeCreateBiTree(charstr[])

{

if(str[pi]=='#')//本層是構建root、root.lchild、root.rchild三個結點{

++pi;

returnnull;

}

BiTreeNoderoot=newBiTreeNode();

root.data=str[pi];

++pi;

root.lchild=CreateBiTree(str);//構造左子樹

root.rchild=CreateBiTree(str);//構造右子樹

returnroot;//遞歸結束返回構造好的樹的根結點

}5.3二叉樹的遍歷學習基礎學習認知能力二叉樹的遍歷，即按照某種規(guī)律對二叉樹的每個結點進行訪問，使得每個結點僅被訪問一次的操作。這里的訪問，可以是對結點的輸出、統(tǒng)計結點的個數(shù)等。如果限定先左后右的次序，則在以上6種遍歷方案中，只剩下3種方案：DLR、LDR和LRD。其中，DLR稱為先序遍歷，LDR稱為中序遍歷，LRD稱為后序遍歷。5.3.1二叉樹遍歷的定義5.3二叉樹的遍歷學習基礎學習認知能力5.3.2二叉樹的先序遍歷二叉樹的先序遍歷的遞歸定義如下：如果二叉樹為空，則執(zhí)行空操作。如果二叉樹非空，則執(zhí)行以下操作：（1）訪問根結點。（2）先序遍歷左子樹。（3）先序遍歷右子樹。根據(jù)二叉樹的先序遞歸定義，得到圖5.16所示的二叉樹的先序序列為：A、B、D、G、E、H、I、C、F、J。5.3二叉樹的遍歷學習基礎學習認知能力二叉樹的先序遞歸算法。publicvoidPreOrderTraverse(BiTreeNodeT)

//先序遍歷二叉樹的遞歸實現(xiàn)

{

if(T!=null){

System.out.print(T.data+"");//訪問根結點

PreOrderTraverse(T.lchild);//先序遍歷左子樹

PreOrderTraverse(T.rchild);//先序遍歷右子樹

}

}5.3二叉樹的遍歷二叉樹的先序非遞歸遍歷從二叉樹的根結點開始，訪問根結點，然后將根結點的指針入棧，重復執(zhí)行以下兩個步驟：（1）如果該結點的左孩子結點存在，訪問左孩子結點，并將左孩子結點的指針入棧。重復執(zhí)行此操作，直到結點的左孩子不存在；（2）將棧頂?shù)脑兀ㄖ羔槪┏鰲?，如果該指針指向的右孩子結點存在，則將當前指針指向右孩子結點。重復執(zhí)行以上兩個步驟，直到?？諡橹?。5.3二叉樹的遍歷publicvoidPreOrderTraverse2(BiTreeNodeT)

//先序遍歷二叉樹的非遞歸實現(xiàn)

{

BiTreeNodestack[]=newBiTreeNode[MAXSIZE];//定義一個棧，用于存放結點的指針

inttop=0;BiTreeNodep=T;

while(p!=null||top>0){

while(p!=null)//如果p不空，訪問根結點，遍歷左子樹

{

System.out.print(p.data+"");//訪問根結點

stack[top++]=p;

p=p.lchild;//遍歷左子樹

}

if(top>0)//如果棧不空

{

p=stack[--top];//棧頂元素出棧

p=p.rchild;//遍歷右子樹

}

}

}5.3二叉樹的遍歷5.3.3二叉樹的中序遍歷二叉樹的中序遍歷的遞歸定義如下：如果二叉樹為空，則執(zhí)行空操作。如果二叉樹非空，則執(zhí)行以下操作：（1）中序遍歷左子樹。（2）訪問根結點。（3）中序遍歷右子樹。根據(jù)二叉樹的中序遞歸定義，圖5.16的二叉樹的中序序列為：D、G、B、H、E、I、A、F、J、C。。5.3二叉樹的遍歷（1）如果該結點的左孩子結點存在，將左孩子結點的指針入棧。重復執(zhí)行此操作，直到結點的左孩子不存在；（2）將棧頂?shù)脑兀ㄖ羔槪┏鰲?，并訪問該指針指向的結點，如果該指針指向的右孩子結點存在，則將當前指針指向右孩子結點。重復執(zhí)行以上（1）和（2），直到棧空為止。publicvoidInOrderTraverse2(BiTreeNodeT)//中序遍歷二叉樹的非遞歸實現(xiàn){BiTreeNodestack[]=newBiTreeNode[MAXSIZE];//定義一個棧，用于存放結點的指針

inttop=0;//定義棧頂指針,初始化棧

BiTreeNodep=T;while(p!=null||top>0){while(p!=null)//如果p不空，則遍歷左子樹

{stack[top++]=p;//將p入棧

p=p.lchild;//遍歷左子樹

}if(top>0)//如果棧不空

{p=stack[--top];//棧頂元素出棧

System.out.print(p.data+"");//訪問根結點

p=p.rchild;//遍歷右子樹

}}}5.3二叉樹的遍歷5.3.4二叉樹的后序遍歷二叉樹的后序遍歷的遞歸定義如下：如果二叉樹為空，則執(zhí)行空操作。如果二叉樹非空，則執(zhí)行以下操作：（1）后序遍歷左子樹。（2）后序遍歷右子樹。（3）訪問根結點。根據(jù)二叉樹的后序遞歸定義，圖6.16所示的二叉樹的后序序列為：G、D、H、I、E、B、J、F、C、A。publicvoidPostOrderTraverse(BiTreeNodeT)//后序遍歷二叉樹的遞歸實現(xiàn){if(T!=null)//如果二叉樹不為空

{PostOrderTraverse(T.lchild);

PostOrderTraverse(T.rchild);

System.out.print(T.data+"");

}}5.3二叉樹的遍歷（1）如果該結點的左孩子結點存在，將左孩子結點的指針入棧。重復執(zhí)行此操作，直到結點的左孩子不存在；（2）取棧頂元素（指針）并賦給p，如果p沒有右孩子或右孩子結點已經(jīng)訪問過，則訪問根結點。否則，則執(zhí)行p=p.rchild。重復執(zhí)行以上（1）和（2），直到?？諡橹?。publicvoidPostOrderTraverse2(BiTreeNodeT)//后序遍歷二叉樹的非遞歸實現(xiàn){BiTreeNodestack[]=newBiTreeNode[MAXSIZE];

inttop=0;BiTreeNodep=T;BiTreeNodeq=null;

//初始化結點的指針

while(p!=null||top>0){while(p!=null)//如果p不空，則遍歷左子樹

{stack[top++]=p;//將p入棧

p=p.lchild;//遍歷左子樹

}if(top>0)//如果棧不空

{p=stack[top-1];//取棧頂元素

if(p.rchild==null||p.rchild==q)//如果p沒有右孩子結點，或右孩子結點已經(jīng)訪問過

{System.out.print(p.data+"");//訪問根結點

q=p;//記錄剛剛訪問過的結點

p=null;//為遍歷右子樹做準備

top--;//出棧

}

elsep=p.rchild;

}}}分析：n個結點，則共有2n個鏈域。除根結點外，每個結點都有一個鏈域指向自身，因此，有n－1個結點的鏈域存放有指針?？罩羔槀€數(shù)＝2n－(n-1)=n+1在n個結點的二叉鏈表中，有

個空指針域。AB

D

E

F

CG^^^^^^^^n+15.4二叉樹的線索化5.4二叉樹的線索化為了區(qū)分指針域指向的是左孩子結點還是直接前驅(qū)結點、右孩子結點還是直接后繼結點，增加兩個標志域ltag和rtag。結點的存儲結構如圖5.20所示。其中，當ltag=0時，lchild指示結點的左孩子；當ltag=1時，lchild指示結點的直接前驅(qū)結點。當rtag=0時，rchild指示結點的右孩子；當rtag=1時，rchild指示結點的直接后繼結點。：5.4二叉樹的線索化二叉樹按照某種遍歷方式使二叉樹變?yōu)榫€索二叉樹的過程稱為二叉樹的線索化。圖5.21所示就是將二叉樹進行先序、中序和后序遍歷得到的線索二叉樹。5.4二叉樹的線索化線索二叉樹的存儲結構類型描述如下：classBiThrNode//線索二叉樹結點{Stringdata;BiThrNodelchild,rchild;intltag,rtag;BiThrNode()

{this.data="NULL";//二叉樹的結點值

this.lchild=null;//左孩子

this.rchild=null;//右孩子

this.ltag=0;//線索標志域

this.rtag=0;//線索標志域

}5.4二叉樹的線索化為了方便，在二叉樹的線索化時，可增加一個頭結點。使頭結點的指針域lchild指向二叉樹的根結點，指針域rchild指向二叉樹中序遍歷時的最后一個結點，二叉樹中的第一個結點的線索指針指向頭結點。初始化時，使二叉樹的頭結點指針域lchild和rchild均指向頭結點，并將頭結點的標志域ltag置為Link，標志域rtag置為Thread。5.4二叉樹的線索化publicBiThrNodeInOrderThreading(BiThrNodeT)

//通過中序遍歷二叉樹T，使T中序線索化。thrt是指向頭結點的指針

{

BiThrNodethrt=newBiThrNode();

//將頭結點線索化

thrt.ltag=0;//修改前驅(qū)線索標志

thrt.rtag=1;//修改后繼線索標志

thrt.rchild=thrt;//將頭結點的rchild指針指向自己

if(T==null)//如果二叉樹為空，則將lchild指針指向自己

thrt.lchild=thrt;

else{

thrt.lchild=T;//將頭結點的左指針指向根結點

pre=thrt;//將pre指向已經(jīng)線索化的結點

T=InThreading(T);//中序遍歷進行中序線索化

//將最后一個結點線索化

pre.rchild=thrt;//將最后一個結點的右指針指向頭結點

pre.rtag=1;//修改最后一個結點的rtag標志域

thrt.rchild=pre;//將頭結點的rchild指針指向最后一個結點

thrt.lchild=T;//將頭結點的左指針指向根結點

}

returnthrt;

}5.4二叉樹的線索化publicBiThrNodeInThreading(BiThrNodep){

//二叉樹中序線索化

if(p!=null){

InThreading(p.lchild);//左子樹線索化

if(p.lchild==null)//前驅(qū)線索化

{

p.ltag=1;

p.lchild=pre;

}

if(pre.rchild==null)//后繼線索化

{

pre.rtag=1;

pre.rchild=p;

}

pre=p;//pre指向的結點線索化完畢，使p指向的結點成為前驅(qū)

InThreading(p.rchild);//右子樹線索化

}

returnp;

}5.4二叉樹的線索化查找指定結點的中序直接前驅(qū)的算法實現(xiàn)如下。publicBiThrNodeInOrderPre(BiThrNodep)

//在中序線索樹中找結點p的中序直接前趨

{

if(p.ltag==1)//如果p的標志域ltag為線索，則p的左子樹結點即為前驅(qū)

returnp.lchild;

else{

pre=p.lchild;//查找p的左孩子的最右下端結點

while(pre.rtag==0)//右子樹非空時，沿右鏈往下查找

pre=pre.rchild;

returnpre;//pre就是最右下端結點

}

}5.4.3線索二叉樹的遍歷5.4二叉樹的線索化中序遍歷線索二叉樹的算法實現(xiàn)如下。publicvoidInOrderTraverse(BiThrNodeT)

//中序遍歷線索二叉樹

{

BiThrNodep=T.lchild;//將根結點賦給p

while(p!=T){

while(p!=T&&p.ltag==0)//順著左孩子線索進行搜索

p=p.lchild;

Print(p);

while(p.rtag==1&&p.rchild!=T){//如果存在右孩子線索，搜索后繼結點

p=p.rchild;

Print(p);

}

p=p.rchild;

}

}5.4二叉樹的線索化【例5.1】編寫程序，建立如圖5-21所示的二叉樹，并將其中序線索化。任輸入一個結點，輸出該結點的中序前驅(qū)和中序后繼。例如，結點’D’的中序直接前驅(qū)是’G’，其中序直接后繼是’A’。線索二叉樹的輸出序列：0 Thread B Link 1 Thread G Thread 2 Link D Thread 3 Link A Link 4 Thread E Link 5 Thread H Thread 6 Link C Link 7 Thread F Thread 元素D的中序直接前驅(qū)元素是:G元素D的中序直接后繼元素是:A元素E的中序直接前驅(qū)元素是:A元素E的中序直接后繼元素是:H5.5樹、森林與二叉樹1.雙親表示法雙親表示法是利用一組連續(xù)的存儲單元存儲樹的每個結點，并利用一個指示器表示結點的雙親結點在樹中的相對位置。通常在Java語言中，利用數(shù)組實現(xiàn)連續(xù)的單元的存儲。樹的雙親表示法如圖5-23所示。5.5.1樹的存儲結構5.5樹、森林與二叉樹classPNode//雙親表示法的結點定義

{

Stringdata;

intparent;//指示結點的雙親

}

classPTree//雙親表示法的類型定義

{

PNodenode[];

intnum;//結點的個數(shù)

PTree()

{

node=newPNode[num];

}

}5.5.1樹的存儲結構5.5樹、森林與二叉樹2.孩子表示法把每個結點的孩子結點排列起來，看成是一個線性表，且以單鏈表作為存儲結構，則n個結點有n個孩子鏈表（葉子結點的孩子鏈表為空表），這樣的鏈表稱為孩子鏈表。5.5樹、森林與二叉樹classChildNode//孩子結點的類型定義{intchild;ChildNodenext;//指向下一個結點}classDataNode//n個結點數(shù)據(jù)與孩子鏈表的指針構成一個結構{intdata;ChildNodefirstchild;//孩子鏈表的指針}孩子表示法classCTree//孩子表示法類型定義{DataNodenode[];intnum;//結點的個數(shù)

introot;//根結點在順序表中的位置

CTree(){node=newDataNode[num];num=0;root=-1;}}5.5樹、森林與二叉樹3.孩子兄弟表示法孩子兄弟表示法，也稱為樹的二叉鏈表表示法。即以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點，分別命名為firstchild域和nextsibling域。5.5樹、森林與二叉樹3.孩子兄弟表示法樹的孩子兄弟表示法的類型描述如下。classCSNode//孩子兄弟表示法的類型定義{Stringdata;CSNodefirstchild,nextsibling;//指向第一個孩子和下一個兄弟}5.5樹、森林與二叉樹5.5.2樹轉(zhuǎn)換為二叉樹從樹的孩子兄弟表示和二叉樹的二叉鏈表表示來看，它們在物理上的存儲方式是相同的，也就是說，從它們的相同的物理結構可以得到一棵樹，也可以得到一棵二叉樹。5.5樹、森林與二叉樹5.5.2樹轉(zhuǎn)換為二叉樹按照以下步驟，可以將一棵樹轉(zhuǎn)換為對應的二叉樹。（1）在樹中的兄弟結點之間加一條連線。（2）在樹中，只保留雙親結點與第一個孩子結點之間的連線，將雙親結點與其他孩子結點的連線刪除。（3）將樹中的各個分支，以某個結點為中心進行旋轉(zhuǎn)，子樹以根結點成對稱形狀。5.5樹、森林與二叉樹5.5.3森林轉(zhuǎn)換為二叉樹按照以下步驟，可以將一棵樹轉(zhuǎn)換為對應的二叉樹。（1）把森林中的所有樹都轉(zhuǎn)換為對應的二叉樹。（2）從第二棵樹開始，將轉(zhuǎn)換后的二叉樹作為前一棵樹根結點的右孩子，插入到前一棵樹中。然后將轉(zhuǎn)換后的二叉樹進行相應的旋轉(zhuǎn)。5.5樹、森林與二叉樹5.5.4二叉樹轉(zhuǎn)換為樹和森林（1）在二叉樹中，將某結點的所有右孩子結點、右孩子的右孩子結點等等，都與該結點的雙親結點用線條連接。（2）刪除掉二叉樹中雙親結點與右孩子結點的原來的連線。（3）調(diào)整轉(zhuǎn)換后的樹或森林，使結點的所有孩子結點處于同一層次。5.6并查集對于并查集，在一些有N個元素的集合應用問題中，初始時通常將每個元素看成是一個單元素的集合，然后按一定次序?qū)儆谕唤M的元素所在的集合兩兩合并，其間要反復查找一個元素在哪個集合中。5.6并查集1.初始化每個元素代表一棵樹。假設有n個編號分別為1、2、...、n的元素，使用列表parent存儲每個元素的父結點，初始化時，先將父結點設為自身。publicclassDisjointSet{finalintMAXSIZE=100;intparent[];intrank[];DisjointSet(intn)

{parent=newint[n+1];rank=newint[n+1];for(inti=0;i<n+1;i++)parent[i]=i;}}5.6并查集將a和f所在的集合（即把a和f兩棵樹）合并后，使a成為兩個結點構成樹的父結點。如圖5-32(b)所示。如圖5-32(c)所示。繼續(xù)將其他結點進行合并操作，直到所有結點構成一棵樹。5.6并查集查找publicintFind(intx){

if(parent[x]==x)

returnx;

else

returnFind(parent[x]);

}5.6并查集查找publicintFind2(intx){

if(parent[x]==x)

returnx;

parent[x]=Find2(x);

returnparent[x];

}帶路徑壓縮的查找算法實現(xiàn)如下：publicintFind_NonRec(intx)

{introot=x;

while(parent[root]!=root)//查找根結點root

root=parent[root];

inty=x;

while(y!=root)//路徑壓縮

{parent[y]=root;

y=parent[y];

}

returnroot;

}5.6并查集3.合并合并算法主要思想：找到x和y所屬子樹的根結點root_x和root_y，若root_x==root_y，則表明它們屬于同一棵子樹，不需合并；否則，需要比較兩棵子樹的高度，即秩，使合并后的子樹高度盡可能小：給你一個由'1'（陸地）和'0'（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網(wǎng)格的四條邊均被水包圍。grid=[

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]5.6并查集算法思想：該題要找到島嶼的數(shù)量，就是一個利用并查集的合并操作，將所有的元素都合并完，再去還剩下多少個獨立集合的問題。每一個島嶼就是一個獨立的集合。這里有一個注意點就是需要區(qū)分不同的樣本，顯然要進行合并的樣本的值都是字符’1’。5.6并查集發(fā)送電文過程中，要將待傳字符轉(zhuǎn)換成二進制的字符串，怎樣編碼才能使轉(zhuǎn)換后的報文盡快發(fā)送？BAAACCCADB010000001010100011010000011100100原則：頻率高的字符編碼盡可能地短5.7哈夫曼樹哈夫曼（Huffman）樹，也稱最優(yōu)二叉樹。它是一種帶權路徑長度最短的樹。A：00B：01C：10D：11A：0B：00C：1D：01編碼短注意：在編碼時，必須保證任何一個字符的編碼不能是其他字符編碼的前綴字符串。AAAAAAAABBAAABBA歧義BAAACCCADB00000111001005.7哈夫曼樹A：0B：00C：1D：01DCAB000111A：110B：111C：10D：0

1111101101101010101100111BAAACCCADBACDB000111A：0B：110C：10D：111

10100011111101111105.7哈夫曼樹使用二叉樹對結點進行編碼是無歧義的，這種編碼就是前綴編碼譯碼時，從根結點出發(fā)，掃描字符串，遇到0訪問左孩子結點，遇到1訪問右孩子結點，直到葉子結點，葉子結點的字符即為該編碼對應的字符。BAAACCCADB特點：每一個字符的編碼都不是其他字符編碼的前綴，絕不會錯譯!稱為前綴碼5.7哈夫曼樹1010001111110111110ACDB0001115.7哈夫曼樹1.路徑和路徑長度路徑是指在樹中，從一個結點到另一個結點所走過的路程。路徑長度是一個結點到另一個結點的分支數(shù)目。2.樹的帶權路徑長度在一些實際應用中，根據(jù)結點的重要程度，將樹中的某一個結點賦予一個有意義的值，則這個值就是結點的權。（1）WPL=8×2+4×2+2×2+3×2=38（2）WPL=8×2+4×3+2×3+3×1=37（3）WPL=8×1+4×2+2×3+3×3=315.7哈夫曼樹（1）由給定的n個權值{w1,w2,…,wn}，構成n棵只有根結點的二叉樹集合F={T1,T2,…,Tn}，每個結點的左右子樹均為空。（2）在二叉樹集合F中，找兩個根結點的權值最小和次小的樹，作為左、右子樹構造一棵新的二叉樹，新二叉樹的根結點的權重為左、右子樹根結點的權重之和。（3）在二叉樹集合F中，刪除作為左、右子樹的兩個二叉樹，并將新二叉樹加入到集合F中。（4）重復執(zhí)行步驟（2）和（3），直到集合F中只剩下一棵二叉樹為止。這顆二叉樹就是要構造的哈夫曼樹。5.7哈夫曼樹例如，假設給定一組權值{1,3,6,9}，按照哈夫曼構造的算法對集合的權重構造哈夫曼樹的過程如圖5.38所示。classHTNode//哈夫曼樹類型定義

{

intweight;

intparent,lchild,rchild;

HTNode()

{

this.weight=weight;

this.parent=parent;

this.lchild=lchild;

this.rchild=rchild;

}

}5.7哈夫曼樹若一棵哈夫曼樹的葉子結點為n個，則該哈夫曼樹結點總數(shù)為2n-1算法實現(xiàn)：定義一個類型為HuffmanCode的變量HT，用來存放每一個葉子結點的哈夫曼編碼。初始時，將每一個葉子結點的雙親結點域、左孩子域和右孩子域初始化為0。如果有n個葉子結點，則非葉子結點有n-1個，所以總共結點數(shù)目是2*n-1個。5.7哈夫曼樹若n=4,w={1,3,6,9}，請構造哈夫曼樹和哈夫曼編碼結點總個數(shù)：m=2*4-1=7weightparentlchrch11000230003600049000567weightparentlchrch1150023500366004970054612610753719046a9c6a1b35.7哈夫曼樹初始狀態(tài)最終狀態(tài)000publicvoidHuffmanCoding(HTNodeHT[],StringHC[],intw[],intn)//構造哈夫曼樹HT，哈夫曼樹的編碼存放在HC中，w為n個字符的權值{if(n<=1)return;intm=2*n-1;for(inti=1;i<=n;i++)//初始化n個葉子結點

{HT[i]=newHTNode();HT[i].weight=w[i-1];HT[i].parent=0；

HT[i].lchild=HT[i].rchild=0;}for(inti=n+1;i<=m;i++)//將n-1個非葉子結點的雙親結點初始化化為0

{HT[i]=newHTNode();HT[i].parent=0;}for(inti=n+1;i<=m;i++)//構造哈夫曼樹

{List<Integer>s=Select(HT,i-1);//查找樹中權值最小的兩個結點

ints1=s.get(0),s2=s.get(1);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}5.7哈夫曼樹

//從葉子結點到根結點求每個字符的哈夫曼編碼

//求n個葉子結點的哈夫曼編碼

for(inti=1;i<=n;i++)

{charcd[]=newchar[n+1];intstart=n-1;for(intc=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子結點到根結點求編碼

{if(HT[f].lchild==c)cd[--start]='0';

elsecd[--start]='1';}HC[i]=newString()；

Stringstr=newString(cd);HC[i]=str;//將當前求出結點的哈夫曼編碼復制到HC}}5.7哈夫曼樹請輸入葉子結點的個數(shù):4請輸入第1個結點的權值:1請輸入第2個結點的權值:3請輸入第3個結點的權值:6請輸入第4個結點的權值:9哈夫曼編碼:100哈夫曼編碼:101哈夫曼編碼:11哈夫曼編碼:0"100101011"的譯碼結果：ABDC【例5.6】通過鍵盤輸入一個表達式，如6+(7-1)*3+9/2，將其轉(zhuǎn)換為二叉樹，即表達式樹，然后通過二叉樹的遍歷操作求解表達式的值。1）初始化棧，并將’#’入棧；2）若當前讀入的字符?2是操作數(shù)，則將該操作數(shù)壓入ExpTreeStack棧，并讀入下一個字符；3）若當前字符?2是運算符，則將?2與棧頂?shù)倪\算符?1比較。（1）若?1優(yōu)先級低于?2，則將?2壓入OptrStack棧，繼續(xù)讀入下一個字符；（2）若?1優(yōu)先級高于?2，則從OptrStack棧中彈出?1，將其作為子樹的根結點，并使ExpTreeStack棧執(zhí)行兩次出棧操作，彈出的兩個表達式rcd和lcd分別作為?1的右子樹和左子樹，從而創(chuàng)建二叉樹，并將該二叉樹的根結點壓入ExpTreeStack棧中。（3）若?1的優(yōu)先級與?2相等，且?1為’(‘，?2為’)’，則將?1出棧，繼續(xù)讀入下一個字符；4）如果?2的優(yōu)先級與?1相等，且?1和?2都為’#‘，從OptrStack棧中將?1彈出，則OptrStack棧為空。則完成中綴表達式轉(zhuǎn)換為表達式樹，ExpTreeStack的棧頂元素就是表達式樹的根結點，算法結束。重復執(zhí)行2）~4），直到所有字符讀取完畢且OptrStack為空。請輸入算術表達式串：6+(7-1)*3+9/2#先序遍歷：++6*-713/92中序遍歷：6+7-1*3+9/2表達式的值：28.55.8小結樹中結點與結點之間是一種一對多的關系。樹的定義是遞歸的。一棵樹或者為空，或者是由m棵子樹T1、T2、…、Tm組成，這m棵子樹又是由其他子樹構成的。樹中的孩子結點沒有次序之分，是一種無序樹。二叉樹的兩棵子樹有次序之分。二叉樹也是遞歸定義的，二叉樹的兩棵子樹又是由左子樹和右子樹構成。在二叉樹中，有兩種特殊的樹：滿二叉樹和完全二叉樹。滿二叉樹中每個非葉子結點都存在左子樹和右子樹，所有的葉子結點都處在同一層次上。完全二叉樹是指與滿二叉樹的前n個結點結構相同，滿二叉樹是一種特殊的完全二叉樹。5.8小結二叉樹的遍歷分為先序遍歷、中序遍歷和后序遍歷。二叉樹遍歷的過程就是將二叉樹這種非線性結構轉(zhuǎn)換成線性結構。通過將二叉樹線索化，不僅可充分利用二叉鏈表中的空指針域，還能很方便地找到指定結點的前驅(qū)結點。在哈夫曼樹中，只有葉子結點和度為2的結點。哈夫曼樹是帶權路徑最小的二叉樹，通常用于解決最優(yōu)化問題。感謝聆聽主講：結構Java實據(jù)現(xiàn)數(shù)第6章圖結構Java實據(jù)現(xiàn)數(shù)目錄CONTENTS6.1

圖的定義及相關概念6.2圖的存儲結構6.3圖的遍歷6.6最短路徑6.4圖的連通性問題6.5有向無環(huán)圖6.7小結6.1圖的定義及相關概念6.1.1圖的定義圖由數(shù)據(jù)元素集合與邊的集合構成。數(shù)據(jù)元素常稱為頂點（Vertex），頂點集合（V）不能為空，邊（E）表示頂點之間的關系，用連線表示。圖（G）的形式化定義為：G=(V,E)，其中，V={x|x∈數(shù)據(jù)元素集合}，E={<x,y>|Path(x,y)/\(x∈V,y∈V)}。Path(x,y)表示從x與y的關系屬性。如果<x,y>∈E，則<x,y>表示從頂點x到頂點y的一條弧（Arc），x稱為弧尾（Tail）或起始點（Initialnode），y稱為弧頭（Head）或終端點（Terminalnode）。6.1圖的定義及相關概念6.1.1圖的定義如果<x,y>∈E且有<y,x>∈E，則用無序?qū)?x,y)代替有序?qū)?lt;x,y>和<y,x>，表示x與y之間存在一條邊（Edge），將這樣的圖稱為無向圖。6.1圖的定義及相關概念6.1.1圖的定義對于無向圖，邊數(shù)e的取值范圍為0~n(n-1)/2。將具有n(n-1)/2條邊的無向圖稱為完全圖。對于有向圖，弧度e的取值范圍是0~n(n-1)。將具有n(n-1)條弧的有向圖稱為有向完全圖。具有e<nlogn條弧或邊的圖，稱為稀疏圖（Sparsegraph）。具有e>nlogn條弧或邊的圖，稱為稠密圖（Densegraph）。6.1圖的定義及相關概念6.1.2圖的相關概念1.鄰接點在無向圖G=(V,E)中，如果存在邊(vi,vj)∈E，則稱vi和vj互為鄰接點（Adjacent），即vi和vj相互鄰接。邊(vi,vj)依附于頂點vi和vj，或者稱邊(vi,vj)與頂點vi和vj相互關聯(lián)。2.頂點的度在無向圖中，頂點v的度是指與v相關聯(lián)的邊的數(shù)目，記作TD(v)。在有向圖中，以頂點v為弧頭的數(shù)目稱為頂點v的入度（InDegree），記作ID(v)。以頂點v為弧尾的數(shù)目稱為v的出度（OutDegree），記作OD(v)。頂點v的度為以v為頂點的入度和出度之和，即TD(v)=ID(v)+OD(v)。6.1圖的定義及相關概念6.1.2圖的相關概念3.路徑在圖中，從頂點vi出發(fā)經(jīng)過一系列的頂點序列到達頂點vj稱為從頂點vi到vj的路徑（Path）。路徑的長度是路徑上弧或邊的數(shù)目。4.子圖假設存在兩個圖G={V,E}和G’={V’,E’}，如果G’的頂點和關系都是V的子集，即有V’V，E’E，則G’為G的子圖。6.1圖的定義及相關概念6.1.2圖的相關概念5.連通圖和強連通圖在無向圖中，如果從頂點vi到頂點vj存在路徑，則稱頂點vi到vj是連通的。推廣到圖的所有頂點，如果圖中的任何兩個頂點之間都是連通的，則稱圖是連通圖（ConnectedGraph）。無向圖中的極大連通子圖稱為連通分量（ConnectedComponent）。6.1圖的定義及相關概念6.1.2圖的相關概念6.生成樹一個連通圖（假設有n個頂點）的生成樹是一個極小連通子圖，它含有圖中的全部頂點，但只有足以構成一棵樹的n-1條邊。6.1圖的定義及相關概念6.1.2圖的相關概念7.網(wǎng)在實際應用中，圖的邊或弧往往與具有一定意義的數(shù)有關，即每一條邊都有與它相關的數(shù)，稱為權，這些權可以表示從一個頂點到另一個頂點的距離或花費等信息。這種帶權的圖稱為帶權圖或網(wǎng)。一個網(wǎng)如圖6.6所示。6.1圖的定義及相關概念6.1.3圖的抽象數(shù)據(jù)類型7.網(wǎng)在實際應用中，圖的邊或弧往往與具有一定意義的數(shù)有關，即每一條邊都有與它相關的數(shù)，稱為權，這些權可以表示從一個頂點到另一個頂點的距離或花費等信息。這種帶權的圖稱為帶權圖或網(wǎng)。一個網(wǎng)如圖6.6所示。ADTGraph{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系R：R={VR}VR={<x,y>|x,y∈V且P(x,y>，<x,y>表示從x到y(tǒng)的弧，謂詞P(x,y>定義了弧<x,y>的意義或信息}6.1圖的定義及相關概念6.1.3圖的抽象數(shù)據(jù)類型基本操作：

（1）CreateGraph(&G)

初始條件：圖G不存在。

操作結果：創(chuàng)建一個圖G。

（2）DestroyGraph(&T)

初始條件：圖G存在。

操作結果：銷毀圖G。

（3）LocateVertex(G,v)

初始條件：圖G存在，頂點v合法。

操作結果：若圖G存在頂點v，則返回頂點v在圖G中的位置。若圖G中沒有頂點v，則函數(shù)返回值為空。

（4）GetVertex(G,i)

初始條件：圖G存在。

操作結果：返回圖G中序號i對應的值。i是圖G某個頂點的序號，返回圖G中序號i對應的值。6.1圖的定義及相關概念6.1.3圖的抽象數(shù)據(jù)類型（5）FirstAdjVertex(G,v)

初始條件：圖G存在，頂點v的值合法。操作結果：返回圖G中v的第一個鄰接頂點。若v無鄰接頂點或圖G中無頂點v，則函數(shù)返回-1。（6）NextAdjVertex(G,v,w)

初始條件：圖G存在，w是圖G中頂點v的某個鄰接頂點。操作結果：返回頂點v的下一個鄰接頂點。若w是v的最后一個鄰接頂點，則函數(shù)返回-1。（11）DFSTraverseGraph(G)

初始條件：圖G存在。操作結果：從圖中的某個頂點出發(fā)，對圖進行深度遍歷。（12）BFSTraverseGraph(G)

初始條件：圖G存在。操作結果：從圖中的某個頂點出發(fā)，對圖進行廣度遍歷。}ADTGraph6.2圖的存儲結構6.2.1鄰接矩陣表示法圖的鄰接矩陣表示（AdjacencyMatrix）也稱為數(shù)組表示。它采用兩個數(shù)組來表示圖：一個是用于存儲頂點信息的一維數(shù)組，另一個是用于存儲圖中頂點之間的關聯(lián)關系的二維數(shù)組，這個關聯(lián)關系數(shù)組稱為鄰接矩陣。6.2圖的存儲結構學習基礎學習認知能力兩個圖弧和邊的集合分別為A={<A,B>,<A,C>,<A,D>,<C,A>,<C,B>,<D,A>}和E={(A,B),(A,D),(B,C),(B,D),(C,D)}。它們的鄰接矩陣表示如圖6.7所示。6.2圖的存儲結構學習基礎學習認知能力enumKind{DG,DN,UG,UN}//圖的類型publicclassMGraph{Stringve