《pascal-第12讲-树与图的简介》由会员分享，可在线阅读，更多相关《pascal-第12讲-树与图的简介（98页珍藏版）》请在金锄头文库上搜索。
1、数据结构之树图简介,王桐林 寿光现代中学,潍坊市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】输入：
2、abcabbmaa输出：yes 【样例2】输入：abcabbmaa输出：no,寿光现代中学,从字符串中读入一个左括号时，就将其压入栈s中； 当读入一个右括号时,就从栈顶取出左括号检查比较,看是否匹配,如果匹配,就将左括号出栈;否则显示不匹配。 全部字符串读完后,最后检查栈是否为空,如果不空,左括号无右括号与之匹配,显示不匹配。,【问题分析】,寿光现代中学,var i,c:integer;s:string;a:array12000 of char;f:boolean; procedure push(l:char);begininc(c);ac:=l;end; procedure pop;begi
3、ndec(c);end;,【参考程序】,寿光现代中学,beginf:=true;readln(s);c:=0;for i:=1 to length(s) dobeginif 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) then writeln(yes) el
4、se writeln(no); end.,n,寿光现代中学,一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 输入：整数m,n(m行，n列) （1=m=80,1=n0) and (x0) and (yw;直至队空为止end;,寿光现代中学,beginfillchar(pic,sizeof(pic),0); num:=0;fillchar(h,sizeof(h),0);readln(m,n);for i:=1 to m dobeginreadln(s);for j:=1 to n doif sj=0 then pi
5、ci,j:=0 else pici,j:=1;end;for i:=1 to m dofor j:=1 to n do if pici,j=1 then doing(i,j);在矩阵中寻找细胞writeln(num); end.,寿光现代中学,数据结构,树,寿光现代中学,栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为
6、非线性结构。具有非线性结构特征的数据结构有两种：树 图,树,寿光现代中学,一、树的概念 1、树的定义树是一种常见的非线性的数据结构。树的递归定义如下：树是n(n0)个结点的有限集，这个集合满足以下条件：有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；除根外，其余的每个结点都有且仅有一个前驱；除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）； 由上述定义可知，树结构没有封闭的回路。,寿光现代中学,寿光现代中学,2、结点的分类 结点一般分成三类 根结点：没有父亲的结点。在树中有且仅有
7、一个根结点。 分支结点：除根结点外，有孩子的结点称为分支结点。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、树的表示方法树的表示方法一般有两种：自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。,寿光现代中学,括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式 （r（a（w，x（d（
9、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； 树数组,寿光现代中学,例如图的树，其记录数组如下。
10、由于未规定同层结点的次序，因此每个结点儿子的下标序列（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，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）,寿光现代中
12、学,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,
