回溯法与树的遍历及图

回溯法与树的遍历及图第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;

//与