《回溯法与树的遍历及图PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《回溯法与树的遍历及图PPT讲稿.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、回溯法与树的遍历及图第1页，共43页，编辑于2022年，星期六第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 树与等价问题 6.6 赫夫曼树及其应用 6.7 回溯法与树的遍历 6.8 树的计数第2页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历回溯法(backtracking)，是解决问题的一种策略，是穷举法的一种推广，一种搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。如右图：一个陌生人从甲地到乙地的策略甲乙第3页，共43页，编辑于2022年，星期六 6.7 回
2、溯法与树的遍历例：求含有n个元素的集合的幂集。若A=1,2,3,则其幂集P(A)=1,2,3,1,2,1,3,1,2,3,2,3,第4页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历可以用分治法来设计这个求幂集的递归过程。另一个角度：幂集的每个元素是一个集合，它或是空集、或含集合A中的一个元素、或含集合A中的两个元素、或等于集合A.也就是说，集合A中的元素x，对于幂集的每一个元素S而言，要么x属于S，要么x不属于S。所以，求幂集的元素的过程可看成是依次对集合A中的元素进行取舍的过程。第5页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历1，2，31，21，312，
3、3231，2121可以用一棵二叉树来表示过程中幂集元素的变化状况，求幂集的元素的过程即为先序遍历这棵状态树的过程。第6页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历求幂集元素的过程即为先序遍历这棵状态树的过程，算法如下：void PowerSet(int i,int n)/求含n个元素的集合A的幂集，进入函数时/已对A中前i-1个元素作了取舍处理，现从第i个元素起/进行取舍处理，若in则求得幂集的一个元素，/并输出之。/初始调用：PowerSet(1,n)if(in)输出幂集的一个元素else取第i个元素，PowSet(i+1,n)舍第i个元素，PowSet(i+1,n)/P
4、owerSet第7页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历算法求精（用线性表表示集合）如下：void GetPowerSet(int i,List A,List&B)/线性表A表示集合A，线性表B表示集合幂集的一个元素/局部变量k为进入函数时表B的当前长度，/第一次调用本函数时，B为空表，i=1if(iListLength(A)Output(B);elseGetElem(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);
5、/GetPowerSet第8页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历八皇后问题：在国际象棋中，皇后可以向八个方向伸展去吃，问题是如何把八个皇后同时放在棋盘上，互相不被吃。第9页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历试试看：第10页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历一个答案：第11页，共43页，编辑于2022年，星期六 6.7 回溯法与树的遍历怎么找？void Trial(int i,int n)/设nxn棋盘的前i-1行已放置了/互不攻击的i-1个棋子if(in)输出棋盘当前布局;else for(j=1;j1)个节点
6、的二叉树可以看成是由一个根节点、一棵具有i个节点的左子树和一棵具有n-i-1个节点的右子树组成，因此：第14页，共43页，编辑于2022年，星期六 6.8 树的计数经演算可知：第15页，共43页，编辑于2022年，星期六 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
7、的右子树的所有结点的前序序列确定 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页，编辑于2022年，星期六 6.8 树的计数设二叉树的前序的序列为 1、2、3、n 不同的中序序列对应着不同形态的二叉树不同的中序序列的总数=不同形态二叉树总数不同的中序序列在中
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、进栈、进栈
9、2、出栈、出栈3、进栈、进栈3、出栈、出栈第17页，共43页，编辑于2022年，星期六 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、出栈
10、、出栈2、进栈、进栈2、出栈、出栈3、进栈、进栈3、出栈、出栈 进出栈序列总数的计算为进出栈序列总数的计算为2n 个方格中放置个方格中放置 3 个个 1 的组合数的组合数 不合理的序列总数不合理的序列总数e.g:n=3 时，时，6格放置格放置3个个 1 的序列的序列情况：情况：1 代表进栈，代表进栈，0 表示出栈表示出栈 1 1 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0合合理理不不合合理理第18页，共43页，编辑于2022年，星期六 6.8 树的计数这个数目为：The sequ
11、ences of n left and n right parentheses that are not well formed correspond exactly to all sequences of n-1 left parentheses and n+1 right parentheses(in all possible orders).To prove this correspondence,let us start with a sequence of n left and n right parentheses that is not well formed.Let k be
12、the first position in which the sequence goes wrong,so the entry at position k is a right parenthesis,and there is one more right parenthesis than left up through this position.Hence strictly to the right of position k there is one fewer right parenthesis than left.Strictly to the right of position
13、k,then,let us replace all left parentheses by right and all right parentheses by left.The resulting sequence will have n-1 left parentheses and n+1 right parentheses altogether.Conversely,let us start with a sequence of n-1 left parentheses and n+1 right parentheses,and let k be the first position w
14、here the number of right parentheses exceeds the number of left(such a position must exist,since there are more right than left parentheses altogether).Again let us exchange left for right and right for left parentheses in the remainder of the sequence(positions after k).We thereby obtain a sequence
15、 of n left and n right parentheses that is not well formed,and we have constructed the one-to-one correspondence as desired.第19页，共43页，编辑于2022年，星期六 6.8 树的计数这个数称为Catalan数：Cat(n)同时也是把n+2边的凸多边形，连n-1条不相交的对角线，把这个凸多边形分成三角形的不同的方法的数目。第20页，共43页，编辑于2022年，星期六 6.8 树的计数由二叉树的计数可推得树的计数，由“森林与二叉树的转换”中可知一棵树可转换成唯一的一棵没有
16、右子树的二叉树，反之亦然。所以具有n个节点的不同形态的树的数目和具有n-1个节点的二叉树的数目相同。这里的树指的是有序树。第21页，共43页，编辑于2022年，星期六第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路经第22页，共43页，编辑于2022年，星期六第7章 图离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可
17、以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。第23页，共43页，编辑于2022年，星期六7.1 图的定义和术语图的抽象数据类型定义如下：ADT Graph 数据对象：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：VR|v,wV且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 第24页，共43页，编辑于2022年，星期六7.1 图的定义和术语基本操作P：结构初始化CreateGraph(&G,V,VR);初始条件：V 是图的顶点集，VR 是图中弧的集合。操作结果
18、：按 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);初
19、始条件：图 G 存在，v 是 G 中某个顶点，w 是 v 的邻接顶点。操作结果：返回 v 的（相对于 w 的）下一个邻接点。若 w 是 v 的最后一个邻接点，则返回空。第25页，共43页，编辑于2022年，星期六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 及
20、其相关的弧。InsertArc(&G,v,w);初始条件：图 G 存在，v 和 w 是 G 中两个顶点。操作结果：在 G 中增添弧，若 G 是无向的，则还增添对称弧。DeleteArc(&G,v,w);初始条件：图 G 存在，v 和 w 是 G 中两个顶点。操作结果：在 G 中删除弧，若 G 是无向的，则还删除对称弧。DFSTraverse(G,Visit();初始条件：图 G 存在，Visit 是顶点的应用函数。操作结果：对图 G 进行深度优先遍历。遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦 visit()失败，则操作失败。BFSTraverse(G,Visit();初始条件
21、：图 G 存在，Visit 是顶点的应用函数。操作结果：对图 G 进行广度优先遍历。遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦 visit()失败，则操作失败。ADT Graph第26页，共43页，编辑于2022年，星期六7.1 图的定义和术语图由一个顶点集和弧集构成，通常写作：Graph=(V,VR)。由于空的图在实际应用中没有意义，因此一般不讨论空的图，即V是顶点的有穷非空集合。表示从顶点 v 到顶点 w 的一条弧，其中顶点 v 被称为弧尾，顶点 w 被称作弧头。由于弧是有方向的，故称有向图。例如下列定义的有向图如右图所示。G1=(V1,VR1)其中：V1=A,B,C,D,
22、EVR1=,若R 必有R，则称(v,w)为顶点 v 和顶点 w 之间存在一条边。由顶点集和边集构成的图称作无向图。例如下列定义的无向图如右所示。G2=(V2,VR2)其中：V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)第27页，共43页，编辑于2022年，星期六7.1 图的定义和术语数学上的定义：图（graph）G是一个序偶，其中V是一个非空有限集合，称为图G的点集，E称为图G的弧集。第28页，共43页，编辑于2022年，星期六7.1 图的定义和术语几个有关图的常用术语顶点的度对无向图而言，邻接点的个数定义为顶点的度。对有
23、向图而言，顶点的度为其出度和入度之和，其中出度定义为以该顶点为弧尾的弧的个数，入度定义为以该顶点为弧头的弧的个数。子图假设有两个图 G=(V,E)和G=(V,E)，如果V is a subset of V 且 E is a subset of E，则称 G为G的子图(subgraph)。路径和回路若有向图 G 中 k+1 个顶点之间都有弧存在（即,都是图 G 中的弧），则这个顶点的序列 v0,v1,vk 为从顶点v0到顶点vk的一条有向路径，路径中弧的数目定义为路径长度，若序列中的顶点都不相同，则为简单路径。对无向图，相邻顶点之间存在边的 k+1 个顶点序列构成一条长度为 k 的无向路径。如果
24、v0和vk是同一个顶点，则是一条由某个顶点出发又回到自身的路径，称这种路径为回路或环。第29页，共43页，编辑于2022年，星期六7.1 图的定义和术语几个有关图的常用术语连通图和连通分量、强连通图和强连通分量 若无向图中任意两个顶点之间都存在一条无向路径，则称该无向图为连通图，否则称为非连通图。若有向图中任意两个顶点之间都存在一条有向路径，则称该有向图为强连通图。非连通图中各个极大连通子图称作该图的连通分量。非强连通的有向图中的极大强连通子图称作有向图的强连通分量。生成树和生成森林一个含 n 个顶点的连通图的生成树是该图中的一个极小连通子图，它包含图中 n 个顶点和足以构成一棵树的 n-1
25、条边。对于非连通图，对其每个连通分量可以构造一棵生成树，合成起来就是一个生成森林。无向网和有向网在实际应用中，图的弧或边往往与具有一定意义的数相关，称这些数为权，分别称带权的有向图和无向图为有向网和无向网。第30页，共43页，编辑于2022年，星期六7.2 图的存储结构7.2.1 数组表示法（邻接矩阵）7.2.2 邻接表7.2.3 十字链表7.2.4 邻接多重表第31页，共43页，编辑于2022年，星期六7.2.1 数组表示法假设图中顶点数为n，则邻接矩阵A=(ai,j)定义为 ai,j=1 若vi和vj有弧或边存在ai,j=0 否则网的邻接矩阵的定义为，当vi到vj有弧相邻接时，ai,j的值
26、应为该弧上的权值，否则为。将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。第32页，共43页，编辑于2022年，星期六7.2.1 数组表示法图的数组(邻接矩阵)存储表示const INFINITY=INT_MAX;/最大值const MAX_VERTEX_NUM=20;/最大顶点个数typedef enum DG,DN,AG,AN GraphKind;/类型标志有向图,有向网,无向图,无向网typedef struct ArcCell /弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；对带权图，则为权值类
27、型。InfoType*info;/该弧相关信息的指针 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义VertexType vexsMAX_VERTEX_NUM;/顶点信息AdjMatrix arcs;/表示顶点之间关系的二维数组int vexnum,arcnum;/图的当前顶点数和弧(边)数GraphKind kind;/图的种类标志 MGraph;第33页，共43页，编辑于2022年，星期六7.2.1 数组表示法无向图的数组表示存储结构有向图的数组表示存储结构第34页，共43页，编辑于2022年，星期六7.2.2 邻接表类
28、似于树的孩子链表，将和同一顶点相邻接的所有邻接点链接在一个单链表中，单链表的头指针则和顶点信息一起存储在一个一维数组中。第35页，共43页，编辑于2022年，星期六7.2.2 邻接表图的邻接表存储表示 const MAX_VERTEX_NUM=20;typedef struct ArcNode_ /弧结点的结构int adjvex;/该弧所指向的顶点的位置struct ArcNode_*nextarc;/指向下一条弧的指针VRType weight;/与弧相关的权值，无权则为0InfoType*info;/指向该弧相关信息的指针 ArcNode;typedef struct VNode/顶点结
29、点的结构VertexType data;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧 AdjListMAX_VERTEX_NUM;typedef struct /图的邻接表结构定义AdjList vertices;/顶点数组int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind;/图的种类标志 ALGraph;第36页，共43页，编辑于2022年，星期六7.2.2 邻接表有向图的邻接表中链接在每个顶点结点中的都是以该顶点为弧尾的弧，每个单链表中的弧结点的个数恰为弧尾顶点的出度，每一条弧在邻接表中只出现一次。虽然在邻接表中也能找到所有以某
30、个顶点为弧头的弧，但必须查询整个邻接表。若在应用问题中主要是对以某个顶点为弧头的弧进行操作，则可以为该有向图建立一个逆邻接表。第37页，共43页，编辑于2022年，星期六7.2.3 十字链表十字链表是有向图的另一种存储结构，目的是将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条出弧和第一条入弧的指针。第38页，共43页，编辑于2022年，星期六7.2.3 十字链表7.2.1中的有向图的十字链表如下所示第39页，共43页，编辑于2022年，星期六7.2.3 十字链表有向图的十字链表存储
31、表示const MAX_VERTEX_NUM=20;typedef struct ArcBox /弧结点结构定义int tailvex,headvex;/该弧的尾和头顶点的位置 struct ArcBox*hlink,*tlink;/分别为弧头相同和弧尾相同的弧的链域VRType weight;/与弧相关的权值，无权则为0InfoType*info;/该弧相关信息的指针 ArcBox;typedef struct VexNode/顶点结点结构定义VertexType data;ArcBox*firstin,*firstout;/分别指向该顶点第一条入弧和出弧 VexNode;typedef s
32、truct /十字链表结构定义VexNode xlistMAX_VERTEX_NUM;/表头向量int vexnum,arcnum;/有向图的当前顶点数和弧数GraphKind kind;/图的种类标志 OLGraph;第40页，共43页，编辑于2022年，星期六7.2.4 邻接多重表类似于有向图的十字链表，若将无向图中表示同一条边的两个结点合在一起，将得到无向图的另一种表示方法-邻接多重表。第41页，共43页，编辑于2022年，星期六7.2.4 邻接多重表7.2.1中无向图的邻接多重表如下所示第42页，共43页，编辑于2022年，星期六7.2.4 邻接多重表无向图的邻接多重表存储表示cons
33、t MAX_VERTEX_NUM=20;typedef emnu unvisited,visited VisitIf;typedef struct EdgeNode/边结点结构定义VisitIf mark;/访问标记int ivex,jvex;/该边依附的两个顶点的位置struct EdgeNode*ilink,*jlink;/分别指向依附这两个顶点的下一条边VRType weight;/与弧相关的权值，无权则为0InfoType*info;/与该边相关信息的指针;typedef struct /顶点结点结构定义VertexType data;EdgeNode*firstedge;/指向第一条依附该顶点的边 VexNode;typedef struct /多重链表结构定义VexNode adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/无向图的当前顶点数和边数GraphKind kind;/图的种类标志 AMLGraph;第43页，共43页，编辑于2022年，星期六