树及其应用(精)

线形结构:数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。不管其存储方式（顺序和链式）如何.栈、队列非线形结构:至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。树、图数据结构:一、树的概念1、树的定义树是一种常见的非线性的数据结构：树型结构。空树（不含结点）；非空树（至少一个结点）树树的递归定义如下：树是n(n=0)个结点的有限集，这个集合满足以下条件：⑴有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；⑵除根外，其余的每个结点都有且仅有一个前驱；⑶除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；由上述定义可知，树结构没有封闭的回路。思考：树中结点和边的关系2、结点的分类结点一般分成三类⑴根结点：没有父亲的结点。在树中有且仅有一个根结点。⑵分支结点：除根结点外，有孩子的结点称为分支结点。⑶叶结点：没有孩子的结点称为树叶。根结点到每一个分支结点或叶结点的路径是唯一的。从根A到结点M的唯一路径为ADHM。3、树的度⑴结点的度：一个结点的子树数目称为该结点的度。⑵树的度：所有结点中最大的度称为该树的度(宽度）。4、树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有4层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图中树的深度为4。12345、森林所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点A，其原来的三棵子树Tb，Tc，Td的集合{Tb，Tc，Td}就为森林，这三棵子树的具体形态如图（c）。6、有序树和无序树按照树中同层结点是否保持有序性，可将树分为有序树和无序树。(1)如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；(2)如果同层结点的次序任意，这样的树称为无序树。二、树的表示方法树的表示方法一般有两种：⑴自然界的树形表示法：用结点和边表示树，例如下图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。优点:直观,形象;缺点:保存困难.⑵括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如下图可写成如下形式(A(B(E(K,L),F),C(G),D(H(M),I,J)))优点:易于保存;缺点:不直观.树的存储结构一般有两种1、静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标Constn=树的度；max=结点数的上限；Typenode=record{结点类型}data：datatype；{数据域}child：array[1‥n]ofinteger；{指向各儿子的下标}end；treetype=array[1..max]ofnode；Vartree：treetype；{树数组}三、存储结构12345678910111213下标信息儿子1A2342B5603C7004D89105E111206F0007G0008H13009I00010J00011K00012L00013M000Idatach[1..m]2、动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n为树的度)个指针域共n+1个域组成，其表示方法如下：Constn=树的度；Typetreetype=^node；{结点类型}node=recorddata：datatype；{数据域}next：array[1‥n]oftreetype；{指向各儿子的指针域}end；Varroot：treetype；{根结点指针}1、家族的统计一已知某个村子中人员关系，统计该村子中含有几个家族，并求出每个家族中的祖先的编号。输入：第一行：n：该村子人的数量；（n=10000）以下若干行：每行两个结点编号：i，j：i是j的父结点(I,j=1000)。输出：第一行：该村中家族的数量。第二行：依次输出每个家族中祖先的编号（从小到大）。样例输入：912234645789194四、简单的应用举例:输出：279分析：father:array[1..10000]ofinteger;father[i]:记录i的父亲结点。初始时：father[i]=0;读入：i，j执行：father[j]:=i;最后统计father[i]=0的结点，即是老祖宗结点。时间复杂度：O(n)已知一个家族中各成员之间的关系，并知道其中有唯一的祖先。完成下列要求。输入：第一行：n（人数），m（关系数）。以下m行；每行两个人x和y，表示y是x的儿子。输出：第一行：祖先（树根）：root。第二行：儿子最多的成员max。第三行：max的儿子。样例输入：8741421315262728样例输出：426782、家族的统计二（treea.pas）constmaxn=100;typetreetype=recordfather:integer;{父结点}num:integer;{儿子个数}child:array[1..maxn]ofinteger;end;vartree:array[1..maxn]oftreetype;n,m:integer;procedureinit;vare,i,j,k,x,y:integer;beginassign(input,'a.in');reset(input);fillchar(tree,sizeof(tree),0);readln(n,m);fori:=1tomdobeginreadln(x,y);tree[y].father:=x;inc(tree[x].num);tree[x].child[tree[x].num]:=y;end;end;functionroot:integer;vari:integer;beginfori:=1tondoiftree[i].father=0thenbeginroot:=i;exit;end;end;procedurefind;vark,i,max:integer;begink:=1;max:=0;fori:=1tondoiftree[i].nummaxthenbegink:=i;max:=tree[i].num;end;writeln(k);fori:=1tomax-1dowrite(tree[k].child[i],'');writeln(tree[k].child[max]);end;BEGINinit;writeln(root);find;END.一、二叉树的理论知识1、二叉树的定义:二叉树（binarytree）是每个结点最多有两个孩子，且其子树有左右之分的有序树。二叉树的递归定义和基本形态二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：⑴有一个特定的结点称为根；⑵余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；二叉树二叉树和树的区别：⑴、树的每一个结点可以有任意多个孩子，而二叉树中每个结点的孩子数不能超过2；⑵、树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。2、下图列出二叉树的五种基本形态：空二叉树只有一个根只有左孩子只有右孩子有左右孩子3、二叉树的两个特殊形态⑴满二叉树：如果一棵深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。(a)⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）(a)(b)4、二叉树的三个主要性质性质1：在二叉树的第i（≥1）层上，最多有2i-1个结点性质2：在深度为k(k≥1)的二叉树中最多有2k-1个结点。性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。n0=n2+1(设n0为二叉树的叶结点数；n2为二叉树中度为2的结点数)设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0+n1+n2（1）由于二叉树中除了根结点外，其余每个结点都有且仅有一个分支进入。设b为二叉树的分支个数，n=b+1（2）所有这些分支同时又为度为1和度为2的结点发出的。因此又有b=n1+2n2(3)（3）代入（2）得出n=n0+n1+n2(1)n=b+1(2)b=n1+2n2(3)n=n1+2n2+1(4)比较（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1。例题：如果一棵m度的树中有N1个度为1的顶点，N2个度为2的顶点，N3个度为3的顶点，……，Nm个度为m的顶点，求该树中叶子顶点个数。分析：设叶子结点数为N0所有结点数为n，边数(分支）为b，则有：n=b+1(1)又：n=N0+N1+N2+…..+NM(2)b=N1+2N2+3N3+…..+M*NM(3)(2),(3)代入（1）得出：N0=N2+2N3+3N4+…..+(M-1)NM+11、(NOIP9)一个高度为h的二叉树最小元素数目（）。A）2h+1B）hC）2h-1D）2hE）2h-12、(NOIP8)按照二叉数的定义，具有3个结点的二叉树有（）种。A）3B）4C）5D）63、(NOIP7).一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点A)2h-1B)2h-1C)2h+1D)h+14、将一棵有100个结点的完全二叉树从根结点这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为[]A98B99C97D505、有n个结点并且其高度为n的二叉树的数目是[]A、nB、2nC、2n-1D、2(n-1)BCBAD6、(NOIP8)设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk，分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系（n0=数学表达式，数学表达式仅含nk、k和数字）。设结点总数为n，则：n=n0+nk除了根结点外，其余每个结点都有且仅有一个分支进入:n-1=k*nk所以：n0=(k-1)*nk+1二、二叉树的存储结构二叉树的存储结构有两种形式⑴、顺序存储结构⑵、链式存储结构1、顺序存储结构将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括⑴一个数据域（data）；⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。Constm=树中结点数上限；Typenode=record{结点类型}data：datatype；{数据值}prt，lch，rch：integer；{父结点、左儿子、右儿子编号}end；treetype=array[1‥m]ofnode；{二叉树的顺序表类型}VarTree：treetype；{二叉树}2、链式存储结构动态数据结构（指针）。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：⑴值域：data⑵左指针域：lch⑶右指针域：rch这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点例如用下图（b）所示的二叉链表存储二叉树（下图（a））Typebitrpetr=^bnode；{结点指针类型}benode=record{结点类型}data：datatype；{值域}lch，rch：bitreptr；{左指针域和右指针域}end；Varbt：bitreptr；{头指针}三、二叉树的遍历(访问)二叉树的遍历是指按照一定的顺序不重复地访问二叉树中的每一个结点。如果用L、D、R分别表示左子树、根结点、右子