pascal第12讲树与图的简介.ppt

数据结构之树图简介,王桐林 寿光现代中学,潍坊市2009信息学奥林匹克夏令营,寿光现代中学,数据结构,寿光现代中学,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【括号匹配】,判断包含有括号，的字符串是否匹配。 【样例1】 输入：abcabbmaa 输出：yes 【样例2】 输入：abcabbmaa 输出：no,寿光现代中学,从字符串中读入一个左括号时，就将其压入栈s中； 当读入一个右括号时,就从栈顶取出左括号检查比较,看是否匹配,如果匹配,就将左括号出栈;否则显示不匹配。 全部字符串读完后,最后检查栈是否为空,如果不空,左括号无右括号与之匹配,显示不匹配。,【问题分析】,寿光现代中学,var i,c:integer; s:string; a:array12000 of char; f:boolean; procedure push(l:char); begin inc(c); ac:=l; end; procedure 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(); if si=( then push();,寿光现代中学,if si= then begin if ac= then pop else f:=false;end; if si= then begin if ac= then pop else f:=false;end; if si= 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) then writeln(yes) else writeln(no); end.,n,寿光现代中学,一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 输入：整数m,n(m行，n列) （1=m=80,1=n=50） 矩阵 输出：细胞的个数。 样例: 输入: 4 10 0234500067 1034560500 2045600671 0000000089 输出:4,队列的应用【细胞】,寿光现代中学,0234500067 1034560500 2045600671 0000000089,共4个细胞,寿光现代中学,算法步骤： 1、从文件中读入m*n矩阵，将其转换为0、1矩阵存入pic数组中； 2、沿pic数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队h，并沿其上、下、左、右四个方向上搜索，如果遇到细胞(picI,j=1)则将其位置入队，入队后的位置picI,j数组置为0； 3、将h队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置入队，入队后的位置pic数组置为0； 4、重复3，直至h队空为止，则此时找出了一个细胞； 5、重复2，直至矩阵找不到细胞； 6、输出找到的细胞数。,寿光现代中学,const dx:array14 of -11=(-1,0,1,0); dy:array14 of -11=(0,1,0,-1); var s:string; pic:array180,150 of 01; 0:无细胞；1:有细胞 m,n,i,j,num:integer; h:array14000,12 of byte; 队列:存细胞的坐标，1：行；2：列,寿光现代中学,procedure doing(p,q:integer); 处理坐标（p,q）的细胞 var i,t,w,x,y:integer; begin inc(num); 细胞数量加1 picp,q:=0; t:=1; 队列头 w:=1; 队列尾 h1,1:=p;h1,2:=q;遇到的第一个细胞入队 repeat for i:=1 to 4 do 沿细胞的上下左右四个方向搜索细胞 begin x:=ht,1+dxi;y:=ht,2+dyi; if (x0) 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:=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.,寿光现代中学,数据结构,树,寿光现代中学,栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。 但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种： 树 图,树,寿光现代中学,一、树的概念 1、树的定义 树是一种常见的非线性的数据结构。树的递归定义如下： 树是n(n0)个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； 除根外，其余的每个结点都有且仅有一个前驱； 除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）； 由上述定义可知，树结构没有封闭的回路。,寿光现代中学,寿光现代中学,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、树的深度（高度） 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。 树中最大的层次称为树的深度，亦称高度。图中树的深度为5。,寿光现代中学,二、树的表示方法和存储结构 1、树的表示方法 树的表示方法一般有两种： 自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。,寿光现代中学,括号表示法： 先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式 （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=array1maxof node； Var tree：treetype； 树数组,寿光现代中学,例如图的树，其记录数组如下。由于未规定同层结点的次序，因此每个结点儿子的下标序列（Treei.ch）任意。其中Treei.chj=0说明结点i的第j个儿子不存在。(编号按层编号),寿光现代中学,三、二叉树的概念 二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。 1、二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件： 有一个特定的结点称为根； 余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树； ？ 二叉树是不是树？二叉树树？,寿光现代中学,由上述定义可以看出，二叉树和树是两个不同的概念 树的每一个结点可以有任意多个，而二叉树中每个结点的后继不能超过2； 树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。,寿光现代中学,前面引入的有关树的一些基本术语对二叉树仍然适用。下图列出二叉树的五种基本形态：,寿光现代中学,2、二叉树的两个特殊形态 满二叉树： 如果一棵深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。(a) 完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(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+.+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=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）。 满二叉树和完全二叉树一般采用顺序存储结构 Const m=树中结点数上限； Type node=record 结点类型 data：datatype； 数据值 prt，lch，rch：0m； 父结点、左儿子、右儿子编号 end； treetype=array1m of node； 二叉树的顺序表类型 Var Tree：treetype； 二叉树,寿光现代中学,例如，采用数组tree存储二叉树（如下图）,寿光现代中学,五、二叉树的遍历 二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。 如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合 DLR、LDR、 LRD 这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。二叉树的存储采用动态的二重链表形式。,寿光现代中学,为了方便叙述，我们以下图为例解释三种遍历规则，我们在写遍历子过程前先定义树结构如下： program shudebianli; type asdf=record name:char;结点名字 father:integer;父结点信息 left:integer;左孩子信息 right:integer;右孩子信息 end; var l,i,h,a:longint; s:string; t:array1100 of asdf;,寿光现代中学,前序遍历 前序遍历的规则如下： 若二叉树为空，则退出。否则 访问处理根结点； 前序遍历左子树； 前序遍历右子树； 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 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); begin if # then begin if ti.left0 then back(ti.left); if ti.right0 then back(ti.right); write(); end; end;,寿光现代中学,六、由二叉树的两种遍历顺序确定树结构 遍历二叉树（如下图）有三种规则： 前序遍历：根左子树右子树； 中序遍历：左子树根右子树； 后序遍历：左子树右子树根；,寿光现代中学,【例题1】根据两种遍历顺序确定树结构 输入： 二叉树的前序遍历顺序与中序遍历顺序 输出： 二叉树的后序遍历顺序 样例： 输入： abcdefg cbdafeg 输出： cdbfgea,寿光现代中学,var sx,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,sz); writeln; end.,寿光现代中学,数据结构,图,寿光现代中学,一、图的基本概念,二、图的存储结构,三、图的遍历,寿光现代中学,图是由一个顶点的集合V和一个顶点间关系的集合E组成： 记 G=（V，E） V：顶点的有限非空集合。 E：顶点间关系的有限集合（边集）。 存在一个结点v，可能含有多个前驱结点和后继结点。,一、 图的基本概念,图2,图3,图1,1、图的的定义,寿光现代中学,无向图： 在图G=（V，E）中，如果对于任意的顶点a，bV， 当(a，b)E时，必有（b，a）E（即关系R对称），此图称为无向图。 无向图中用不带箭头的边表示顶点的关系 V=1, 2, 3, 4, 5 E=(1, 2),(1, 3),(1, 4),(2,3),(2,5),(3, 5),(4,5),2、无向图和有向图,寿光现代中学,有向图： 如果对于任意的顶点a，bV，当(a，b)E时 ，(b，a)E未必成立，则称此图为有向图。 在有向图中，通常用带箭头的边连接两个有关联的结点。 V=1, 2, 3, 4,5 E= , , , , , ,寿光现代中学,在无向图中：顶点v的度是指与顶点v相连的边的数目D(v)。D(2)=3,3、顶点的度、入度和出度,在有向图中： 入度以该顶点为终点的边的数目和 . ID(3)=2 出度以该顶点为起点的边的数目和 . OD(3)=1 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。 度：等于该顶点的入度与出度之和。 D(5)=ID(5)+OD(5)=1+2=3,结论：图中所有顶点的度=边数的两倍,图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）称为该路径的长度。,图1,图2,图1: 1、(1,2,3,5) 长度=3 2、(1,2,3,5,2) 长度=4 3、(1,2,5,4,1) 长度=4,图2: (1,2,5,4) 长度=3,（1）、如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。 （2）、x1=xk的简单路径称为回路（也称为环）,4、路径、简单路径、回路,寿光现代中学,5、连通、连通图、连通分量 (无向图),连通：“连成一片”。 连通图：“能连成一片的图”。,图一：连通图,图二：非连通图,定义： 连通：如果存在一条从顶点u到v有路径，则称u和v是连通的。 连通图：图中任意的两个顶点u和v都是连通的，称为连通图。 否则称为非连通图。,连通分量：无向图中的极大连通子图。,图二中有3个连通分量： 1 2 4 5 3 6 7 8,求连通分量数，最大连通分量等。,有向图：强连通、强连通图、强连通分量,寿光现代中学,6、带权图,图中的边可以加上表示某种含义的数值，数值称为边的权，此图称为带权图。也称为网。,一般的图边上没有数字，边仅表示两个顶点的相连接关系。,寿光现代中学,二、图的存储结构,顶点：数组或记录,边：邻接矩阵/邻接表,G=( V,E ),寿光现代中学,邻接矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的邻接矩阵是如下定义的二维数组 a1n,1n。,1、图的邻接矩阵表示法,寿光现代中学,对角线为0：自身不相连。 无向图：是对称矩阵。有向图一般不是。 第i行非0 的个数是结点i的度,寿光现代中学,具体到题目时，数据的给出格式多种多样： 1）、直接给出邻接矩阵，直接读即可。 如： 输入文件内容： 5 0 2 2 3 0 2 0 1 0 3 2 1 0 0 2 3 0 0 0 4 0 3 2 4 0,maxn=100 a:array1maxn,1maxn of integer fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j);,寿光现代中学,2）、给出边的顶点。 如输入文件：两个顶点及权值 5 7 1 2 2 1 3 2 1 4 3 2 3 1 2 5 3 3 5 2 4 5 4,readln(n); readln(m); for k:=1 to m do begin readln(i,j,x); ai,j:=x; aj,i:=x; end,寿光现代中学,6 2 3 6 3 4 5 6 3 1 4 6 3 2 3 5 3 2 4 6 4 1 2 3 5,3)、给出每个顶点的邻接点,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;,寿光现代中学,无权图:设置结点指针,2、邻接表 :,寿光现代中学,type point=node; node=record v:integer; next:point; end; var a:array1maxvof point;,readln(n1,n2); new(p); p.v:=n2; p.next:=an1; an1:=p; new(p); p.v:=n1; p.next:=an2; an2:=p;,寿光现代中学,头指针,邻接点指针,有权图：,寿光现代中学,type edge = node; node = record v: integer; weight : integer; next : edge; end; vpoint = record v: integer; link : edge; end; var a : array1maxn of vpoint;,寿光现代中学,邻接矩阵和邻接表的优缺点：,邻接表,邻接矩阵,寿光现代中学,邻接矩阵：代码书写简单，找邻接点慢 邻接表：代码书写较复杂，找邻接点快,一般采用邻接矩阵,寿光现代中学,0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0,邻接表,邻接矩阵,寿光现代中学,稀疏图：边表,type node=record w:integer; /边权 u,v:integer; /两个结点 end; var e: array1maxn*(maxn-1) div 2 of node; /边,寿光现代中学,三、图的遍历 给出一个图G，从某一个初始点出发，按照一定的搜索方法对图中的每一个结点访问仅且访问一次的过程。 访问结点：处理结点的过程。如输出、查找结点的信息。 按照搜索方法的不同，通常有两种遍历方法： 1、深度优先搜索dfs 2、广度优先搜索bfs,寿光现代中学,1、深度优先搜索DFS 遍历算法（递归过程）： 1)从某一初始出发点i开始访问： 输出该点编号；并对该点作被访问标志（以免被重复访问）。 2)再从i的其中一个未被访问的邻接点j作为初始点出发继续深搜。 当i的所有邻接点都被访问完，则退回到i的父结点的另一个邻接点k再继续深搜。 直到全部结点访问完毕,寿光现代中学,实现:,a1maxn,1maxn:边的邻接矩阵。1：有边；0：无边 f1maxn:boolean 标记是否被访问过。 True: 已访问；flase：没访问。初始值：false,10 12 1 4 1 5 1 6 4 8 5 3 4 3 5 7 6 2 7 10 2 9 3 7 7 2,Procedure 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; /局部变量？ 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);,寿光现代中学,2、广度优先搜索(宽度优先搜索）BFS 按层次遍历： 从图中某结点i出发，在访问了i之后依次访问i的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。,寿光现代中学,实现： 队列：q1maxn f1n:boolean: 判重,head,tail,寿光现代中学,procedure bfs(i:integer);/ bfs.pas var j,k:integer; begin fillchar(q,sizeof(q),0); head:=0; tail:=1; q1:=i; fi:=true; 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个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一