回溯法與樹的遍歷及圖第1頁，課件共43頁，創作于2023年2月第6章樹和二叉樹

6.1樹的定義和基本術語

6.2二叉樹

6.3遍歷二叉樹和線索二叉樹

6.4樹和森林

6.5樹與等價問題

6.6赫夫曼樹及其應用

6.7回溯法與樹的遍歷

6.8樹的計數第2頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷回溯法(backtracking)，是解決問題的一種策略，是窮舉法的一種推廣，一種搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。如右圖：一個陌生人從甲地到乙地的策略甲乙第3頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷例：求含有n個元素的集合的冪集。若

A={1,2,3},則其冪集

P(A)={

{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}

}第4頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷可以用分治法來設計這個求冪集的遞歸過程。另一個角度：

冪集的每個元素是一個集合，它或是空集、或含集合A中的一個元素、或含集合A中的兩個元素、或等于集合A.

也就是說，

集合A中的元素x，對于冪集的每一個元素S而言，要么x屬于S，要么x不屬于S。

所以，求冪集的元素的過程可看成是依次對集合A中的元素進行取舍的過程。第5頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷1，2，31，21，312，3231，2121可以用一棵二叉樹來表示過程中冪集元素的變化狀況，求冪集的元素的過程即為先序遍歷這棵狀態樹的過程。第6頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷求冪集元素的過程即為先序遍歷這棵狀態樹的過程，算法如下：

voidPowerSet(inti,intn){

//求含n個元素的集合A的冪集，進入函數時

//已對A中前i-1個元素作了取舍處理，現從第i個元素起

//進行取舍處理，若i>n則求得冪集的一個元素，

//并輸出之。

//初始調用：PowerSet(1,n)

if(i>n)輸出冪集的一個元素

else{

取第i個元素，PowSet(i+1,n)

舍第i個元素，PowSet(i+1,n)

}

}//PowerSet第7頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷算法求精（用線性表表示集合）如下：

voidGetPowerSet(inti,ListA,List&B){

//線性表A表示集合A，線性表B表示集合冪集的一個元素

//局部變量k為進入函數時表B的當前長度，

//第一次調用本函數時，B為空表，i=1 if(i>ListLength(A))Output(B);

else{

GetElem(A,i,x);k=ListLength(B);

ListInsert(B,k+1,x);GetPowSet(i+1,A,B);

ListDelete(B,k+1,x);GetPowSet(i+1,A,B);

}

}//GetPowerSet第8頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷八皇后問題：

在國際象棋中，皇后可以向八個方向伸展去吃，問題是如何把八個皇后同時放在棋盤上，互相不被吃。第9頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷試試看：第10頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷一個答案：第11頁，課件共43頁，創作于2023年2月

6.7回溯法與樹的遍歷怎么找？

voidTrial(inti,intn){

//設nxn棋盤的前i-1行已放置了

//互不攻擊的i-1個棋子

if(i>n)輸出棋盤當前布局;

elsefor(j=1;j<=n;++j){

在第i行第j列放置一個棋子;

if(當前布局合法)Trial(i+1,n);

移走第i行第j列的棋子;

}

}//Trial第12頁，課件共43頁，創作于2023年2月

6.8樹的計數具有n個節點的不同形態的樹（二叉樹）有多少棵？二叉樹T和T’相似是指：二者都為空樹或者都不為空樹，且它們的左右子樹分別相似。二叉樹的計數問題就是討論具有n個節點、互不相似的二叉樹的數目bn第13頁，課件共43頁，創作于2023年2月

6.8樹的計數一棵具有n(n>1)個節點的二叉樹可以看成是由一個根節點、一棵具有i個節點的左子樹和一棵具有n-i-1個節點的右子樹組成，因此：第14頁，課件共43頁，創作于2023年2月

6.8樹的計數經演算可知：第15頁，課件共43頁，創作于2023年2月

6.8樹的計數另一個角度：

前序（后序）＋中序唯一確定一棵二叉樹e.g:

前序:A、B、D、E、F、C

中序:D、B、E、F、A、C確定過程:

1、定根A

2、在中序序列中找到A

3、中序序列中的A的左部為A的左子樹上的所有結點，A的右部為A的右子樹中的所有結點。

4、根據A的左子樹的所有結點的前序序列確定A的左子樹的根節點，它是A的左兒子。

5、根據A的右子樹的所有結點的前序序列確定A的右子樹的根節點，它是A的右兒子。

6、在左、右子樹中反復以上過程。至所有結點處理完畢。結束前序:A、B、D、E、F、C

中序:D、B、E、F、A、C前序:A、B、D、E、F、C

中序:D、B、E、F、A、CEF前序:B、D、E、F

中序:D、B、E、F前序:E、F

中序:E、FA

CA

D、E、FCBABCD

D、B、E、F第16頁，課件共43頁，創作于2023年2月

6.8樹的計數設二叉樹的前序的序列為1、2、3、…、n不同的中序序列對應著不同形態的二叉樹不同的中序序列的總數

=不同形態二叉樹總數不同的中序序列在中序遍歷時和相應的進出棧序列一一對應。不同的進出棧序列的總數

=不同形態的二叉樹的總數實例：e.g:當二叉樹的結點個數n=3 前序序列為1、2、3時1231231231231231、進棧2、進棧3、進棧3、出棧2、出棧1、出棧1、進棧2、進棧2、出棧3、進棧3、出棧1、出棧1、進棧2、進棧2、出棧1、出棧3、進棧3、出棧1、進棧1、出棧2、進棧3、進棧2、出棧3、出棧1、進棧1、出棧2、進棧2、出棧3、進棧3、出棧第17頁，課件共43頁，創作于2023年2月

6.8樹的計數實例：e.g:當二叉樹的結點個數n=3 前序序列為1、2、3時1231231231231231、進棧2、進棧3、進棧3、出棧2、出棧1、出棧1、進棧2、進棧2、出棧3、進棧3、出棧1、出棧1、進棧2、進棧2、出棧1、出棧3、進棧3、出棧1、進棧1、出棧2、進棧3、進棧2、出棧3、出棧1、進棧1、出棧2、進棧2、出棧3、進棧3、出棧進出棧序列總數的計算為2n個方格中放置3個1的組合數－不合理的序列總數e.g:n=3時，6格放置3個1的序列情況：1代表進棧，0表示出棧

111000

110010

110100

101100

101010

000111

100110合理不合理第18頁，課件共43頁，創作于2023年2月

6.8樹的計數這個數目為：Thesequencesofnleftandnrightparenthesesthatarenotwellformedcorrespondexactlytoallsequencesofn-1leftparenthesesandn+1rightparentheses(inallpossibleorders).Toprovethiscorrespondence,letusstartwithasequenceofnleftandnrightparenthesesthatisnotwellformed.Letkbethefirstpositioninwhichthesequencegoeswrong,sotheentryatpositionkisarightparenthesis,andthereisonemorerightparenthesisthanleftupthroughthisposition.Hencestrictlytotherightofpositionkthereisonefewerrightparenthesisthanleft.Strictlytotherightofpositionk,then,letusreplaceallleftparenthesesbyrightandallrightparenthesesbyleft.Theresultingsequencewillhaven-1leftparenthesesandn+1rightparenthesesaltogether.Conversely,letusstartwithasequenceofn-1leftparenthesesandn+1rightparentheses,andletkbethefirstpositionwherethenumberofrightparenthesesexceedsthenumberofleft(suchapositionmustexist,sincetherearemorerightthanleftparenthesesaltogether).Againletusexchangeleftforrightandrightforleftparenthesesintheremainderofthesequence(positionsafterk).Wetherebyobtainasequenceofnleftandnrightparenthesesthatisnotwellformed,andwehaveconstructedtheone-to-onecorrespondenceasdesired.第19頁，課件共43頁，創作于2023年2月

6.8樹的計數這個數稱為Catalan數：Cat(n)同時也是把n+2邊的凸多邊形，連n-1條不相交的對角線，把這個凸多邊形分成三角形的不同的方法的數目。第20頁，課件共43頁，創作于2023年2月

6.8樹的計數由二叉樹的計數可推得樹的計數，由“森林與二叉樹的轉換”中可知一棵樹可轉換成唯一的一棵沒有右子樹的二叉樹，反之亦然。所以具有n個節點的不同形態的樹的數目和具有n-1個節點的二叉樹的數目相同。這里的樹指的是有序樹。第21頁，課件共43頁，創作于2023年2月第7章圖

7.1圖的定義和術語

7.2圖的存儲結構

7.3圖的遍歷

7.4圖的連通性問題

7.5有向無環圖及其應用

7.6最短路經第22頁，課件共43頁，創作于2023年2月第7章圖離散數學中的圖論是專門研究圖性質的一個數學分支，但圖論注重研究圖的純數學性質，而數據結構中對圖的討論則側重于在計算機中如何表示圖以及如何實現圖的操作和應用等。圖是較線性表和樹更為復雜的數據結構，因此和線性表、樹不同，雖然在遍歷圖的同時可以對頂點或弧進行各種操作，但更多圖的應用問題如求最小生成樹和最短路徑等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們在計算機中的具體實現。第23頁，課件共43頁，創作于2023年2月7.1圖的定義和術語圖的抽象數據類型定義如下：

ADTGraph{

數據對象：

V是具有相同特性的數據元素的集合，稱為頂點集。

數據關系：

VR＝{<v,w>|v,w∈V且P(v,w)，<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}第24頁，課件共43頁，創作于2023年2月7.1圖的定義和術語基本操作P：

{結構初始化}

CreateGraph(&G,V,VR);初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結果：按V和VR的定義構造圖G。

{銷毀結構}

DestroyGraph(&G);初始條件：圖G存在。操作結果：銷毀圖G。

{引用型操作}

LocateVex(G,u);初始條件：圖G存在，u和G中頂點有相同特征。操作結果：若G中存在和u相同的頂點，則返回該頂點在圖中位置；否則返回其它信息。

GetVex(G,v);初始條件：圖G存在，v是G中某個頂點。操作結果：返回v的值。

FirstAdjVex(G,v);初始條件：圖G存在，v是G中某個頂點。操作結果：返回v的第一個鄰接點。若該頂點在G中沒有鄰接點，則返回"空"。

NextAdjVex(G,v,w);初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點。操作結果：返回v的（相對于w的）下一個鄰接點。若w是v的最后一個鄰接點，則返回"空"。第25頁，課件共43頁，創作于2023年2月7.1圖的定義和術語……

{加工型操作}

PutVex(&G,v,value);初始條件：圖G存在，v是G中某個頂點。操作結果：對v賦值value。

InsertVex(&G,v);初始條件：圖G存在，v和圖中頂點有相同特征。操作結果：在圖G中增添新頂點v。

DeleteVex(&G,v);初始條件：圖G存在，v是G中某個頂點。操作結果：刪除G中頂點v及其相關的弧。

InsertArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個頂點。操作結果：在G中增添弧<v,w>，若G是無向的，則還增添對稱弧<w,v>。

DeleteArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個頂點。操作結果：在G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<w,v>。

DFSTraverse(G,Visit());初始條件：圖G存在，Visit是頂點的應用函數。操作結果：對圖G進行深度優先遍歷。遍歷過程中對每個頂點調用函數Visit一次且僅一次。一旦visit()失敗，則操作失敗。

BFSTraverse(G,Visit());初始條件：圖G存在，Visit是頂點的應用函數。操作結果：對圖G進行廣度優先遍歷。遍歷過程中對每個頂點調用函數Visit一次且僅一次。一旦visit()失敗，則操作失敗。}ADTGraph第26頁，課件共43頁，創作于2023年2月7.1圖的定義和術語圖由一個頂點集和弧集構成，通常寫作：Graph=(V,VR)。由于空的圖在實際應用中沒有意義，因此一般不討論空的圖，即V是頂點的有窮非空集合。<v,w>表示從頂點v到頂點w的一條弧，其中頂點v被稱為弧尾，頂點w被稱作弧頭。由于弧是有方向的，故稱有向圖。例如下列定義的有向圖如右圖所示。G1=(V1,VR1)其中：V1={A,B,C,D,E}VR1=

{<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}若<v,w>∈R必有<w,v>∈R，則稱(v,w)為頂點v和頂點w之間存在一條邊。由頂點集和邊集構成的圖稱作無向圖。例如下列定義的無向圖如右所示。G2=(V2,VR2)其中：V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}第27頁，課件共43頁，創作于2023年2月7.1圖的定義和術語數學上的定義：圖（graph）G是一個序偶<V,E>，

其中

V是一個非空有限集合，

稱為圖G的點集，

E稱為圖G的弧集。第28頁，課件共43頁，創作于2023年2月7.1圖的定義和術語幾個有關圖的常用術語頂點的度

對無向圖而言，鄰接點的個數定義為頂點的度。

對有向圖而言，頂點的度為其出度和入度之和，其中出度定義為以該頂點為弧尾的弧的個數，入度定義為以該頂點為弧頭的弧的個數。子圖

假設有兩個圖G=(V,E)和G‘=(V’,E‘)，如果V’isasubsetofV且E’isasubsetofE，則稱G‘為G的子圖(subgraph)。路徑和回路

若有向圖G中k+1個頂點之間都有弧存在（即<v0,v1>,<v1,v2>,…<vk-1,vk>都是圖G中的弧），則這個頂點的序列{v0,v1,…,vk}為從頂點v0到頂點vk的一條有向路徑，路徑中弧的數目定義為路徑長度，若序列中的頂點都不相同，則為簡單路徑。對無向圖，相鄰頂點之間存在邊的k+1個頂點序列構成一條長度為k的無向路徑。如果v0和vk是同一個頂點，則是一條由某個頂點出發又回到自身的路徑，稱這種路徑為回路或環。第29頁，課件共43頁，創作于2023年2月7.1圖的定義和術語幾個有關圖的常用術語連通圖和連通分量、強連通圖和強連通分量

若無向圖中任意兩個頂點之間都存在一條無向路徑，則稱該無向圖為連通圖，否則稱為非連通圖。若有向圖中任意兩個頂點之間都存在一條有向路徑，則稱該有向圖為強連通圖。

非連通圖中各個極大連通子圖稱作該圖的連通分量。非強連通的有向圖中的極大強連通子圖稱作有向圖的強連通分量。生成樹和生成森林

一個含n個頂點的連通圖的生成樹是該圖中的一個極小連通子圖，它包含圖中n個頂點和足以構成一棵樹的n-1條邊。對于非連通圖，對其每個連通分量可以構造一棵生成樹，合成起來就是一個生成森林。無向網和有向網

在實際應用中，圖的弧或邊往往與具有一定意義的數相關，稱這些數為"權"，分別稱帶權的有向圖和無向圖為有向網和無向網。第30頁，課件共43頁，創作于2023年2月7.2圖的存儲結構7.2.1數組表示法（鄰接矩陣）7.2.2鄰接表7.2.3十字鏈表7.2.4鄰接多重表第31頁，課件共43頁，創作于2023年2月7.2.1數組表示法假設圖中頂點數為n，則鄰接矩陣A=(ai,j)定義為

ai,j=1若vi和vj有弧或邊存在

ai,j=0否則網的鄰接矩陣的定義為，當vi到vj有弧相鄰接時，ai,j的值應為該弧上的權值，否則為∞。將圖的頂點信息存儲在一個一維數組中，并將它的鄰接矩陣存儲在一個二維數組中即構成圖的數組表示。第32頁，課件共43頁，創作于2023年2月7.2.1數組表示法圖的數組(鄰接矩陣)存儲表示

constINFINITY=INT_MAX;

//最大值∞

constMAX_VERTEX_NUM=20;

//最大頂點個數

typedefenum{DG,DN,AG,AN}GraphKind;

//類型標志{有向圖,有向網,無向圖,無向網}

typedefstructArcCell{

//弧的定義

VRTypeadj;

//VRType是頂點關系類型。

//對無權圖，用1或0表示相鄰否；對帶權圖，則為權值類型。

InfoType*info;

//該弧相關信息的指針

}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct{

//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點信息

AdjMatrixarcs;

//表示頂點之間關系的二維數組

intvexnum,arcnum;

//圖的當前頂點數和弧(邊)數

GraphKindkind;

//圖的種類標志

}MGraph;第33頁，課件共43頁，創作于2023年2月7.2.1數組表示法無向圖的數組表示存儲結構有向圖的數組表示存儲結構第34頁，課件共43頁，創作于2023年2月7.2.2鄰接表類似于樹的孩子鏈表，將和同一頂點"相鄰接"的所有鄰接點鏈接在一個單鏈表中，單鏈表的頭指針則和頂點信息一起存儲在一個一維數組中。第35頁，課件共43頁，創作于2023年2月7.2.2鄰接表圖的鄰接表存儲表示

constMAX_VERTEX_NUM=20;

typedefstructArcNode__{

//弧結點的結構

intadjvex;

//該弧所指向的頂點的位置

structArcNode__*nextarc;

//指向下一條弧的指針

VRTypeweight;

//與弧相關的權值，無權則為0

InfoType*info;

//指向該弧相關信息的指針

}ArcNode;

typedefstructVNode{

//頂點結點的結構

VertexTypedata;

//頂點信息

ArcNode*firstarc;

//指向第一條依附該頂點的弧

}AdjList[MAX_VERTEX_NUM];

typedefstruct{

//圖的鄰接表結構定義

AdjListvertices;

//頂點數組

intvexnum,arcnum;

//圖的當前頂點數和弧數

GraphKindkind;

//圖的種類標志

}ALGraph;第36頁，課件共43頁，創作于2023年2月7.2.2鄰接表有向圖的鄰接表中鏈接在每個頂點結點中的都是以該頂點為弧尾的弧，每個單鏈表中的弧結點的個數恰為弧尾頂點的出度，每一條弧在鄰接表中只出現一次。雖然在鄰接表中也能找到所有以某個頂點為弧頭的弧，但必須查詢整個鄰接表。若在應用問題中主要是對以某個頂點為弧頭的弧進行操作，則可以為該有向圖建立一個"逆鄰接表"。第37頁，課件共43頁，創作于2023年2月7.2.3十字鏈表十字鏈表是有向圖的另一種存儲結構，目的是將在有向圖的鄰接表和逆鄰接表中兩次出現的同一條弧用一個結點表示，由于在鄰接表和逆鄰接表中的頂點數據是相同的，則在十字鏈表中只需要出現一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。第38頁，課件共43頁，創作于2023年2月7.2.3十字鏈表7.2.1中的有向圖的十字鏈表如下所示第39頁，課件共43頁，創作于2023年2月7.2.3十字鏈表有向圖的十字鏈表存儲表示

constMAX_VERTEX_NUM=20;

typedefstructArcBox{

//弧結點結構定義

inttailvex,headvex;

//該弧的尾和頭頂點的位置

structArcBox*hlink,*tlink;//分別為弧頭相同和弧尾相同的弧的鏈域

VRTypeweight;

//與