pascal第十二讲树与图的简介

1、ascal第十二讲树与图的简介数据结构1. 线性结构（栈、队列）的回顾2. 非线性结构（树）的简介3. 非线性结构（图）的简介4. 数据结构之简单总结1. 线性结构（栈、队列）的回顾什么是栈？什么是队列？寿光现代中学栈的应用1【括号匹配】1、栈S初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是_ （noip1998） (A) 5,4,3,2,1 (B) 2,1(C) 2,3 (D) 3,4寿光现代中学栈的应用2【括号匹配】 判断包含有括号，的字符串是否匹配。

2、【样例1】 输入：abcabbmaa 输出：yes【样例2】 输入：abcabbmaa 输出：no寿光现代中学从字符串中读入一个左括号时，就将其压入栈s中；当读入一个右括号时,就从栈顶取出左括号检查比较,看是否匹配,如果匹配,就将左括号出栈;否则显示不匹配。全部字符串读完后,最后检查栈是否为空,如果不空,左括号无右括号与之匹配,显示不匹配。【问题分析】寿光现代中学var i,c:integer; s:string; a:array1.2000 of char; f:boolean;procedure push(l:char); begin inc(c); ac:=l; end;procedur

3、e pop; begin dec(c); end;【参考程序】寿光现代中学begin f:=true; readln(s); c:=0; for i:=1 to length(s) do begin if f=false then break; if si= then push(); if si= then push(); if si= then push( then begin if ac= then pop else f:=false;end; if si=) then begin if ac=( then pop else f:=false;end; end; if f and (c=0

4、) then writeln(yes) else writeln(no);end.n寿光现代中学 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。输入：整数m,n(m行，n列) （1=m=80,1=n0) and (x0) and (yw;直至队空为止 end;寿光现代中学begin fillchar(pic,sizeof(pic),0); num:=0; fillchar(h,sizeof(h),0); readln(m,n); for i:=1 to m do begin readln(s); for j:=

5、1 to n do if sj=0 then pici,j:=0 else pici,j:=1; end; for i:=1 to m do for j:=1 to n do if pici,j=1 then doing(i,j);在矩阵中寻找细胞 writeln(num);end.寿光现代中学数据结构树寿光现代中学 栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。 但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个

6、结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种：树 图树v0v3v1v6v2v4v5寿光现代中学一、树的概念1、树的定义 树是一种常见的非线性的数据结构。树的递归定义如下： 树是n(n0)个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； 除根外，其余的每个结点都有且仅有一个前驱； 除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；由上述定义可知，树结构没有封闭的回路。 寿光现代中学寿光现代中

7、学 2、结点的分类 结点一般分成三类根结点：没有父亲的结点。在树中有且仅有一个根结点。分支结点：除根结点外，有孩子的结点称为分支结点。b，c，x，t，d，i。分支结点亦是其子树的根；叶结点：没有孩子的结点称为树叶。w，h，e，f，s，m，o，n，j，u为叶结点。根结点到每一个分支结点或叶结点的路径是唯一的。从根r到结点i的唯一路径为rcti。寿光现代中学 3、有关度的定义 结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。 树的度：所有结点中最大的度称为该树的度(宽度）。图中树的度为3。寿光现代中学 4、

8、树的深度（高度） 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。 树中最大的层次称为树的深度，亦称高度。图中树的深度为5。寿光现代中学 二、树的表示方法和存储结构1、树的表示方法 树的表示方法一般有两种：自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。寿光现代中学 括号表示法： 先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号

9、隔开，最后用闭括号括起来。例如图可写成如下形式（r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）寿光现代中学 2、树的存储结构树的存储结构一般有两种静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n 为树的度)的数组，分别存储该结点的每一个儿子的下标Const n=树的度；max=结点数的上限； Type node=record 结点类型 data：datatype； 数据域 ch：array1n of integer； 指向各儿子的下标 end；treetype=array1.maxof node； Var tree：tr

10、eetype； 树数组寿光现代中学例如图的树，其记录数组如下。由于未规定同层结点的次序，因此每个结点儿子的下标序列（Treei.ch）任意。其中Treei.chj=0说明结点i的第j个儿子不存在。(编号按层编号)寿光现代中学 三、二叉树的概念 二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。1、二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；？ 二叉树是不是树？二叉树树？寿

11、光现代中学由上述定义可以看出，二叉树和树是两个不同的概念树的每一个结点可以有任意多个，而二叉树中每个结点的后继不能超过2；树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。寿光现代中学前面引入的有关树的一些基本术语对二叉树仍然适用。下图列出二叉树的五种基本形态：寿光现代中学 2、二叉树的两个特殊形态满二叉树： 如果一棵深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。(a)完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完

12、全二叉树（例如下图(b)）寿光现代中学 3、二叉树的三个主要性质性质1：在二叉树的第i（1）层上，最多有2i-1个结点证明 数学归纳法证明归纳基础 i=1时，有2i-1=20=1,因为第一层只有一个根结点，所以命题成立。归纳假设 假设对于所有的j（1=ji）命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。归纳步骤 根据归纳假设，第i-1层的结点数至多是第2i-2个结点。由于二叉树的每个结点至多有2个孩子，故第i层上至多有2*2i-2=2i-1个结点。寿光现代中学性质2：在深度为k(k1)的二叉树中最多有2k-1个结点。证明：根据性质1，深度为k的二叉树最多有：20+21+.+

13、2k-1=2k-1（等比数列求和乘2做减法）寿光现代中学性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。n0=n2+1设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然所有结点数目 n=n0+n1+n2 （1）所有这些分支同时又为度为1和度为2的结点发出的。再加上根结点，因此又有 n=1+n1+2n2 (2)由上两个等式求得：n0=1+n2寿光现代中学例题：如果一棵m度的树中有N1个度为1的顶点，N2个度为2的顶点，N3个度为3的顶点，Nm个度为m的顶点，求该树中叶子顶点个数。分析：设叶子结点数为N0 所有结点数为n，边数(分支）为b，则有： n

14、=b+1 (1) 又b= N1+2N2+3N3+.+M*NM (2)又：n= N0+N1+N2+.+NM (3) (2),(3)代入（1）得出： N0 =N2+2N3+3N4+.+(M-1)NM+1寿光现代中学四、二叉树的存储结构二叉树的存储结构有两种形式顺序存储结构链式存储结构寿光现代中学1、顺序存储结构将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括一个数据域（data）；三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。满二叉树和完全二叉树一般采用顺序存储结构 C

15、onst m=树中结点数上限； Type node=record 结点类型 data：datatype； 数据值 prt，lch，rch：0m； 父结点、左儿子、右儿子编号 end； treetype=array1m of node； 二叉树的顺序表类型 Var Tree：treetype； 二叉树寿光现代中学例如，采用数组tree存储二叉树（如下图）寿光现代中学五、二叉树的遍历 二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。 如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合 DLR、LD

16、R、 LRD这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。二叉树的存储采用动态的二重链表形式。寿光现代中学为了方便叙述，我们以下图为例解释三种遍历规则，我们在写遍历子过程前先定义树结构如下：program shudebianli;type asdf=record name:char;结点名字 father:integer;父结点信息 left:integer;左孩子信息 right:integer;右孩子信息 end;var l,i,h,a:longint; s:string; t:array1.100 of asdf;寿光现代中学前序遍历前序遍历的规则如下：若二叉树

17、为空，则退出。否则 访问处理根结点； 前序遍历左子树； 前序遍历右子树； a b d e h i c f g寿光现代中学 procedure front(i:integer);begin if # then begin write(); if ti.left0 then front(ti.left); if ti.right0 then front(ti.right);end;end;寿光现代中学中序遍历中序遍历的规则如下： 若二叉树为空，则退出；否则 中序遍历左子树； 访问处理根结点； 中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列： d b h

18、 e i a f c g 寿光现代中学 procedure mid(i:integer);begin if # then begin if ti.left0 then mid(ti.left); write(); if ti.right0 then mid(ti.right); end;end;寿光现代中学后序遍历后序遍历的规则如下： 若二叉树为空，则退出；否则 后序遍历左子树； 后序遍历右子树； 访问处理根结点； 若后序遍历上图中的二叉树，可以得到如下的后序序列 d h i e b f g c a寿光现代中学 procedure back(i:integer);b

19、egin if # then begin if ti.left0 then back(ti.left); if ti.right0 then back(ti.right); write(); end;end;寿光现代中学六、由二叉树的两种遍历顺序确定树结构遍历二叉树（如下图）有三种规则： 前序遍历：根左子树右子树； 中序遍历：左子树根右子树； 后序遍历：左子树右子树根；寿光现代中学【例题1】根据两种遍历顺序确定树结构输入：二叉树的前序遍历顺序与中序遍历顺序输出： 二叉树的后序遍历顺序样例：输入：abcdefgcbdafeg输出：cdbfgea寿光现代中学var sx

20、,sz:string; 算法procedure work(sx,sz:string);sx:先序序列; sz：中序序列 var l,k:integer; begin if sx then begin l:=length(sx); k:=pos(sx1,sz); 根在中序序列中的位置 work(copy(sx,2,k-1),copy(sz,1,k-1); 递归调用左子树 work(copy(sx,k+1,l-k),copy(sz,k+1,l-k); 递归调用右子树 write(sx1); 后序输出根结点 end; end;begin readln(sx); readln(sz); work(sx

21、,sz); writeln;end.寿光现代中学数据结构图寿光现代中学一、图的基本概念二、图的存储结构三、图的遍历寿光现代中学 图是由一个顶点的集合V和一个顶点间关系的集合E组成： 记 G=（V，E） V：顶点的有限非空集合。 E：顶点间关系的有限集合（边集）。 存在一个结点v，可能含有多个前驱结点和后继结点。一、 图的基本概念125341253412534图2图3图1 1、图的的定义寿光现代中学无向图： 在图G=（V，E）中，如果对于任意的顶点a，bV，当(a，b)E时，必有（b，a）E（即关系R对称），此图称为无向图。无向图中用不带箭头的边表示顶点的关系 V=1, 2, 3, 4, 5 E

22、=(1, 2),(1, 3),(1, 4),(2,3),(2,5),(3, 5),(4,5) 125342、无向图和有向图寿光现代中学有向图： 如果对于任意的顶点a，bV，当(a，b)E时 ，(b，a)E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点。V=1, 2, 3, 4,5 E= , , , , , 12534寿光现代中学在无向图中：顶点v的度是指与顶点v相连的边的数目D(v)。D(2)=33、顶点的度、入度和出度在有向图中：入度以该顶点为终点的边的数目和 . ID(3)=2 出度以该顶点为起点的边的数目和 . OD(3)=1度数为奇数的顶点叫做奇点，度数为

23、偶数的点叫做偶点。度：等于该顶点的入度与出度之和。 D(5)=ID(5)+OD(5)=1+2=3 1253412534结论：图中所有顶点的度=边数的两倍图1:无向图图2：有向图无向完全图寿光现代中学 在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1xk(k1) x1=a，xk=b (xi，xi+1)E i=1k-1则称结点序列x1=a，x2，xk=b为结点a到结点b的一条路径，而路径上边的数目（k-1）称为该路径的长度。1253412534图1图2图1: 1、(1,2,3,5) 长度=3 2、(1,2,3,5,2) 长度=4 3、(1,2,5,4,1) 长度=4图2:

24、(1,2,5,4) 长度=3（1）、如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。（2）、x1=xk的简单路径称为回路（也称为环）4、路径、简单路径、回路寿光现代中学5、连通、连通图、连通分量 (无向图)连通：“连成一片”。连通图：“能连成一片的图”。1253412534678图一：连通图图二：非连通图定义：连通：如果存在一条从顶点u到v有路径，则称u和v是连通的。连通图：图中任意的两个顶点u和v都是连通的，称为连通图。 否则称为非连通图。连通分量：无向图中的极大连通子图。图二中有3个连通分量：1 2 4 5 3 6 7 8求连通分量数，最大连

25、通分量等。有向图：强连通、强连通图、强连通分量 寿光现代中学6、带权图 图中的边可以加上表示某种含义的数值，数值称为边的权，此图称为带权图。也称为网。 一般的图边上没有数字，边仅表示两个顶点的相连接关系。12534234213212534寿光现代中学二、图的存储结构ABDCE12345顶点：数组或记录边：邻接矩阵/邻接表 G=( V,E )寿光现代中学 邻接矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的邻接矩阵是如下定义的二维数组 a1.n,1.n。ai,j=1 (或权值)：无向图：有边( i , j )和边( j , i ) 有向图：有边0: i 到 j 无边

26、1、图的邻接矩阵表示法寿光现代中学125340 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 10 1 1 1 01 2 3 4 51 23451253423421320 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 01 2 3 4 51 2345125340 1 0 1 00 0 1 0 11 0 0 0 00 0 0 0 00 0 1 1 01 2 3 4 51 2345对角线为0：自身不相连。无向图：是对称矩阵。有向图一般不是。第i行非0 的个数是结点i的度寿光现代中学具体到题目时，数据的给出格式多种多样：1）、直接给出邻接矩阵

27、，直接读即可。如：输入文件内容：50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0maxn=100a:array1.maxn,1.maxn of integerfillchar(a,sizeof(a),0);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);125342342132寿光现代中学2）、给出边的顶点。如输入文件：两个顶点及权值571 2 21 3 21 4 32 3 12 5 33 5 24 5 4125342342132readln(n); readln(m);for k:=1

28、to m do begin readln(i,j,x); ai,j:=x; aj,i:=x; end寿光现代中学62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 51235463)、给出每个顶点的邻接点 readln(n); for i:=1 to n do begin read(k); for j:=1 to k do begin read(x); ai,x:=1;ax,i:=1; end; end;寿光现代中学125344无权图:设置结点指针结点邻接点指针2、邻接表 :1234523413512515234邻结点头结点寿光现代中学type point=no

29、de; node=record v:integer; next:point; end;var a:array1.maxvof point;vnext readln(n1,n2); new(p); p.v:=n2; p.next:=an1; an1:=p; new(p); p.v:=n1; p.next:=an2; an2:=p;寿光现代中学125342342132123452232431231531221521354233244头指针邻接点指针结点邻接点指针邻接点边权值下一个邻接点指针有权图：寿光现代中学type edge = node; node = record v: integer; w

30、eight : integer; next : edge; end; vpoint = record v: integer; link : edge; end;var a : array1.maxn of vpoint;vlinkvweightnext寿光现代中学邻接矩阵和邻接表的优缺点：125340 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 10 1 1 1 01 2 3 4 51 23451234523413512515234邻结点头结点邻接表邻接矩阵寿光现代中学邻接矩阵：代码书写简单，找邻接点慢邻接表：代码书写较复杂，找邻接点快一般采用邻接矩阵寿光现代中学1763

31、245980 1 0 0 0 0 0 0 01 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 10 0 0 0 0 0 1 0 00 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 00 0 0 0 1 0 0 0 01234521679邻结点头结点67895邻接表邻接矩阵寿光现代中学稀疏图：边表type node=record w:integer; /边权 u,v:integer; /两个结点 end;var e: array1.maxn*(maxn-1) div 2 of node; /边寿光

32、现代中学三、图的遍历 给出一个图G，从某一个初始点出发，按照一定的搜索方法对图中的每一个结点访问仅且访问一次的过程。 访问结点：处理结点的过程。如输出、查找结点的信息。 按照搜索方法的不同，通常有两种遍历方法： 1、深度优先搜索dfs 2、广度优先搜索bfs 寿光现代中学1、深度优先搜索DFS遍历算法（递归过程）： 1)从某一初始出发点i开始访问： 输出该点编号；并对该点作被访问标志（以免被重复访问）。 2)再从i的其中一个未被访问的邻接点j作为初始点出发继续深搜。 当i的所有邻接点都被访问完，则退回到i的父结点的另一个邻接点k再继续深搜。直到全部结点访问完光现代中学

33、实现:a1.maxn,1.maxn:边的邻接矩阵。1：有边；0：无边f1.maxn:boolean 标记是否被访问过。 True: 已访问；flase：没访问。初始值：false10121 41 51 64 8 5 34 35 76 27 102 93 77 2Procedure init; /初始化 begin readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; end;寿光现代中学procedure dfs(k:integer);/从k点出发遍历 var j:integer; /局

34、部变量？ begin write(k, ); fk:=true; for j:=1 to n do if (fj=false)and(ak,j=1) then dfs(j); end;上图的遍历结果：Dfs(1)?寿光现代中学主程序begin fillchar(f,sizeof(f),false); for i:=1 to n do if not fi then dfs(i);end;寿光现代中学求无向的连通分量 sum:=0; for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum);12534678寿

35、光现代中学2、广度优先搜索(宽度优先搜索）BFS 按层次遍历： 从图中某结点i出发，在访问了i之后依次访问i的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到光现代中现： 队列：q1.maxn f1.n:boolean: 判重headtail寿光现代中学procedure bfs(i:integer);/ bfs.pas var j,k:integer; begin fillchar(q,sizeof(q),0); head:=0; tail:=1; q1:=i; fi:=true

36、; while headtail do /队列非空 begin inc(head); /出队 k:=qhead; write(k, ); for j:=1 to n do if (ak,j=1)and(fj=false) then begin inc(tail); /进队 qtail:=j; fj:=true; end; end; end;寿光现代中学3、图的遍历的简单应用1、犯罪团伙【问题描述】 警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识，有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。【输入】 第一行：n（1000,罪犯数量）。 第二行：m（5000，关系数量）。 以下m行，每行两个数：i 和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。【输出】 一个整数，犯罪团伙的数量。寿光现代中学【样例输入】118 1 24 53 41 35 67 105 108 9【样例输出】 3样例说明：共三个集团。寿光现代中学把n个人看成图的n个顶点；相互认识的连一无向条边。相互认识的所有人构成一个极大连通子图。问题转化为：求无向图的连通分量 （有多少个极大