第十四讲：树及其应用.ppt

第14讲:数据结构之 树,线形结构:数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。不管其存储方式（顺序和链式）如何.栈、队列非线形结构:至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。树、图,数据结构:,一、树的概念1、树的定义 树是一种常见的非线性的数据结构：树型结构。空树（不含结点）；非空树（至少一个结点）,第一部分 树,树的递归定义如下：树是n(n=0)个结点的有限集，这个集合满足以下条件：有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；除根外，其余的每个结点都有且仅有一个前驱；除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；由上述定义可知，树结构没有封闭的回路。,思考：树中结点和边的关系,2、结点的分类 结点一般分成三类根结点：没有父亲的结点。在树中有且仅有一个根结点。分支结点：除根结点外，有孩子的结点称为分支结点。叶结点：没有孩子的结点称为树叶。根结点到每一个分支结点或叶结点的路径是唯一的。从根A到结点M的唯一路径为ADHM。,3、树的度结点的度：一个结点的子树数目称为该结点的度。树的度：所有结点中最大的度称为该树的度(宽度）。,4、树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有4层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图中树的深度为4。,1,2,3,4,5、森林 所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点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 为树的度)的数组，分别存储该结点的每一个儿子的下标Const n=树的度；max=结点数的上限；Type node=record 结点类型 data：datatype；数据域 child：array1n of integer；指向各儿子的下标 end；treetype=array1.maxof node；Var tree：treetype；树数组,三、存储结构,I data ch1.m,2、动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下：Const n=树的度；Type treetype=node；结点类型 node=record data：datatype；数据域 next：array1n of treetype；指向各儿子的指针域 end；Var root：treetype；根结点指针,1、家族的统计一 已知某个村子中人员关系，统计该村子中含有几个家族，并求出每个家族中的老祖的编号。输入：第一行：n：该村子人的数量；（n=10000）以下若干行：每行两个结点编号：i，j：i是j的父结点(I,j=1000)。输出：第一行：该村中家族的数量。第二行：依次输出每个家族中老祖的编号（从小到大）。样例输入：91 22 34 64 57 89 1 9 4,四、简单的应用举例:,输出：27 9,分析：father:array1.10000 of integer;fatheri:记录i的父亲结点。初始时：fatheri=0;读入：I，j 执行：fatherj:=I最后统计 fatheri=0的结点，即时老祖宗结点。时间复杂度：O(n),已知一个家族中各成员之间的关系，并知道其中有唯一的老祖。完成下列要求。,输入：第一行：n（人数），m（关系数）。以下m行；每行两个人x和y，表示y是x的儿子。输出：第一行：老祖（树根）：root。第二行：儿子最多的成员max。第三行：max的儿子。,样例输入：8 74 14 21 31 52 62 72 8,样例输出：42 6 7 8,2、家族的统计二（treea.pas）,const maxn=100;type treetype=record father:integer;num:integer;child:array1.maxn of integer;end;var tree:array1.maxn of treetype;n,m:integer;procedure init;var e,i,j,k,x,y:integer;begin assign(input,a.in);reset(input);fillchar(tree,sizeof(tree),0);readln(n,m);for i:=1 to m do begin readln(x,y);treey.father:=x;inc(treex.num);treex.childtreex.num:=y;end;end;,function root:integer;var i:integer;begin for i:=1 to n do if treei.father=0 then begin root:=I;exit;end;end;procedure find;var k,i,max:integer;begin k:=1;max:=0;for i:=1 to n do if treei.nummax then begin k:=i;max:=treei.num;end;writeln(k);for i:=1 to max-1 do write(treek.childi,);writeln(treek.childmax);end;BEGIN init;writeln(root);find;END.,一、二叉树的理论知识1、二叉树的定义:二叉树（binary tree）是每个结点最多有两个孩子，且其子树有左右之分的有序树。二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；,第二部分 二叉树(BT),二叉树和树的区别：、树的每一个结点可以有任意多个孩子，而二叉树中每个结点的孩子数不能超过2；、树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。,2、下图列出二叉树的五种基本形态：,空二叉树,只有一个根,只有左孩子,只有右孩子,有左右孩子,3、二叉树的两个特殊形态满二叉树：如果一棵深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。(a)完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）,(a),(b),4、二叉树的三个主要性质性质1：在二叉树的第i（1）层上，最多有2i-1个结点性质2：在深度为k(k1)的二叉树中最多有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+1,1、(NOIP9)一个高度为h 的二叉树最小元素数目（）。A）2h+1B）h C）2h-1D）2hE）2h-12、(NOIP8)按照二叉数的定义，具有3个结点的二叉树有（）种。A）3 B）4 C）5 D）63、(NOIP7).一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点A)2h-1 B)2h-1 C)2h+1 D)h+14、将一棵有100个结点的完全二叉树从根结点这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为 A 98 B 99 C 97 D 505、有n个结点并且其高度为n的二叉树的数目是 A、n B、2n C、2n-1 D、2(n-1),6、(NOIP8)设有一棵k叉树，其中只有度为0和k两种结点，设n 0，n k，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0=数学表达式，数学表达式仅含n k、k和数字）。,二、二叉树的存储结构二叉树的存储结构有两种形式、顺序存储结构、链式存储结构,1、顺序存储结构 将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括一个数据域（data）；三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。,Const m=树中结点数上限；Type node=record 结点类型 data：datatype；数据值 prt，lch，rch：integer；父结点、左儿子、右儿子编号 end；treetype=array1m of node；二叉树的顺序表类型 Var Tree：treetype；二叉树,2、链式存储结构 动态数据结构（指针）。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：值域：data左指针域：lch右指针域：rch这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点,例如用下图（b）所示的二叉链表存储二叉树（下图（a）,Type bitrpetr=bnode；结点指针类型 benode=record 结点类型 data：datatype；值域 lch，rch：bitreptr；左指针域和右指针域 end；Var bt：bitreptr；头指针,三、二叉树的遍历(访问)所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、LRD、DLR、DRL、RDL、RLD若再限定先左后右的次序，则只剩下三种组合 DLR、LDR、LRD这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。,1、前（根）序遍历：DLR前序遍历的规则如下：若二叉树为空，则退出。否则 访问处理根结点；前序遍历左子树；前序遍历右子树；a b d e h i c f g,2、中序遍历：LDR中序遍历的规则如下：若二叉树为空，则退出；否则 中序遍历左子树；访问处理根结点；中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列：d b h e i a f c g,3、后序遍历：LRD后序遍历的规则如下：若二叉树为空，则退出；否则 后序遍历左子树；后序遍历右子树；访问处理根结点；若后序遍历上图中的二叉树，可以得到如下的后序序列 d h i e b f g c a,2）、写出二叉树后序遍历序列,1）、对二叉树从1进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的 编号，则可以采取 次序的遍历方法。A 先序 B中序 C后序 D从根开始的层次,1、编程实现：二叉树的遍历（tree1.pas）建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。输入：第一行：结点个数n。以下行：每行3个数，第一个是父亲，后两个依次为左右孩子。输出：根、先中后序遍历结果。,样例输入：81 2 42 0 04 8 03 1 55 6 06 0 78 0 07 0 0,样例输出：33 1 2 4 8 5 6 72 1 8 4 3 6 7 52 8 4 1 7 6 5 3,const maxn=100;type treetype=record father:integer;lch,rch:integer;end;var tree:array1.maxn of treetype;n,m,t:integer;procedure init;var f,l,r,i:integer;begin assign(input,tree.in);reset(input);fillchar(tree,sizeof(tree),0);readln(n);for i:=1 to n do begin readln(f,l,r);treef.lch:=l；treef.rch:=r;if l0 then treel.father:=f;if r0 then treer.father:=f;end;end;,function root:integer;var i:integer;begin for i:=1 to n do if treei.father=0 then begin root:=i;exit;end;end;,方法：数组顺序存储结构,procedure preorder(t:integer);begin if t0 then begin write(t,);preorder(treet.lch);preorder(treet.rch);end;end;procedure inorder(t:integer);begin if t0 then begin inorder(treet.lch);write(t,);inorder(treet.rch);end;end;,procedure sucorder(t:integer);begin if t0 then begin sucorder(treet.lch);sucorder(treet.rch);write(t,);end;end;BEGIN init;t:=root;writeln(t);preorder(t);writeln;inorder(root);writeln;sucorder(t);END.,2、二叉链表先序建立二叉树。(程序实现tree2.pas),用#表示空输入序列：abd#eh#I#cf#g#,程序实现：写出二叉树的建立(先序)及遍历的递归算法。program tree(input,output);type btlink=btnode;btnode=record data:char;lchild,rchild:btlink;end;var bt:btlink;,procedure precrt(var bt:btlink);var ch:char;begin read(ch);if ch=#then bt:=nil else begin new(bt);bt.data:=ch;precrt(bt.lchild);precrt(bt.rchild);end;end;,procedure preorder(bt:btlink);begin if btnil then begin write(bt.data);preorder(bt.lchild);preorder(bt.rchild);end;end;,procedure inorder(bt:btlink);begin if btnil then begin inorder(bt.lchild);write(bt.data);inorder(bt.rchild);end;end;,procedure sucorder(bt:btlink);begin if btnil then begin sucorder(bt.lchild);sucorder(bt.rchild);write(bt.data);end;end;,begin precrt(bt);preorder(bt);writeln;inorder(bt);writeln;sucorder(bt);end.,遍历算法的简单变化：1)设计算法按照从左向右的顺序输出二叉树的叶子结点。,procedure ye(bt:btlink);begin if btnil then begin if(bt.lchild=nil)and(bt.rchild=nil)then write(bt.data);ye(bt.lchild);ye(bt.rchild);end;end;,2)设计算法求二叉树中的结点数。,procedure sum(bt:btlink);begin if btnil then begin n:=n+1;sum(bt.lchild);sum(bt.rchild);end;end;,3）设计算法求二叉树中度为2的结点数。,procedure sum2(bt:btlink);begin if btnil then begin if(bt.lchildnil)and(bt.rchildnil)then m:=m+1;sum2(bt.lchild);sum2(bt.rchild);end;end;,4）设计算法求二叉树的深度。,function high(bt:btlink):integer;var a,b:integer;begin if bt=nil then high:=0 else begin a:=high(bt.lchild);b:=high(bt.rchild);if ab then high:=a+1 else high:=b+1;end;end;,四、由二叉树的两种遍历顺序确定树结构遍历二叉树（如下图）有三种规则：前序遍历：根左子树右子树；中序遍历：左子树根右子树；后序遍历：左子树右子树根；,结论：1、已知先序和中序可以确定二叉树2、已知后序和中序可以确定二叉树例：先序:abdecf中序:dbeafc画出二叉树，写出后序遍历的结果。,2、(NOIP7)已知一棵二叉树的结点名为大写英文字母。中序遍历：CBGEAFHDIJ后序遍历：CGEBHFJIDA则该二叉树的先序遍历的顺序为：,3、中序遍历：DBGEACHFI 后序遍历：DGEBHIFCA 求先序遍历结果,4、(NOIP6)已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。,1、给出一棵二叉树的先序遍历：ABCDEFGH中序遍历：CBEDAGHF画出此二叉树并写出后序遍历结果。,【例题1】根据两种遍历顺序确定树结构输入：二叉树的前序遍历顺序与中序遍历顺序输出：二叉树的后序遍历顺序样例：输入：ABCDEFGHCBEDAGHF输出：CEDBHGFA,var sx,sz:string;procedure work(sx,sz:string);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);end.,石子合并问题 有n堆石子,每堆有一个重量,每次把2堆石子合并成1堆,付出的代价为这两堆石子的重量之和,如果把这n堆石子最后合并成1堆石子,怎样合并才能使付出的代价最小,求出最小的代价.,五、最优二叉树(哈夫曼树),显然图(D)所示的合并方法付出的代价最小:54,例如n=5,重量 分别为7、5、2、4、6。,(D)L=6+11+13+24=54,1、最优二叉树的定义在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使（wk第k个叶结点的权值；pk第k个叶结点的带权路径长度）达到最小。,2、最优二叉树的构造方法 假定给出n个结点ki(i=1n)，其权值分别为wi(i=1n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：首先，将给定的n个结点构成n棵二叉树的集合F=T1，T2，Tn。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步 在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；在F中删除这两棵二叉树，同时将新得到的二叉树加入F中；重复、，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。以上构造最优二叉树的方法称为哈夫曼（huffmann）算法。,例如：给定五个结点k1，k2，k3，k4，k5，其权值分别为16、2、18、16、23。构造最优二叉树的过程如下：构造初始集合F，F中各二叉树根结点的权值分别为16，2，18，16，23（如下图）：,以具有权值16及2的根结点的两棵二叉树为左、右子树，构造一棵根权值为18的新二叉树，并从F中删去这两棵二叉树（如下图）：,以同样的方法，得到一个新二叉树的集合F，其根结点的权值分别为23，18，34（如下图）：,又得到一个新二叉树的集合F，其根结点的权值分别为34，41（如下图）：,最后得到最优二叉树（如下图），其根结点的权值为75，结点数为2*5-1=9。,在最优二叉树中非叶结点的度均为2，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。由此得出最优二叉树的数据类型定义Const n=叶结点数的上限；m=2*n-1；最优二叉树的结点数 Type node=record 结点类型 data：integer；权值 prt，lch，rch,lth：0m；父指针、左、右指针和路径长度 end；wtype=array1n of integer；n个叶结点权值的类型 treetype=array1m of node；最优二叉树的数组类型 Var tree：treetype；其中tree 1n为叶结点，tree n+12n-1为中间结点，根为tree 2n-1,在最优二叉树的顺序存储结构中前n个结点为叶结点。构造最优二叉树的算法如下：procedure hufm(w：wtype；var tree：treetype；var bt：integer)；function min(h：integer)：integer；在前h个结点中选择父指针为0且权值最小的结点min begin ml；for p1 to h do if(treepprt=0)and(m1treepdata)then begin ip；m1treepdata；end；then mini；end；min,begin fillchar(tree，sizeof(tree)，0)；构造初始集合F for i1 to n do read(treeiData)；for kn+1 to m do 构造最优二叉树 begin 计算k为根的左儿子和右儿子 imin(k-1)；treeiprtk；treeklchi；jmin(k-1)；treejprtk；treekrchj；treekdatatreeidata+treejdata；end；for btm；end；hufm,3、哈夫曼编码使用频率高的采用短的的编码,则总的编码长度便可减少.,例如:在某通讯中只使用abcd四种字符,其出现频率分别为:0.4,0.3,0.2,0.1。请进行哈夫曼编码。使通讯码尽可能的短 并写出信息：bbdaac的编码。,1）.给定一个整数集合3，5，6，9，12，下列二叉树哪个是该整数集合对应的霍夫曼（Huffman）树。（）,2）、已知如图所示的哈夫曼树，那么电文CDAA的编码是 A 110100 B 11011100 C 010110111 D 11111100,3）、若以4，5，6，7,8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 A、69 B、70 C、73 D、68,4）(NOIP6)在有N个叶子节点的哈夫曼树中，其节点总数为（）A.不确定B.2N-1C.2N+1D.2N,1、树的公共祖先：给定一棵二叉树和两个不同的节点，求出他们最近的公共祖先父节点。已知该二叉树有n个节点，标号1.n。(n100)输入：第一行两个整数x，y，表示需要计算的节点；以下若干行，每行两个整数a和b，表示a的父节点是b。输出：X与y的最近公共祖先root。,输入样例：9 72 13 24 25 38 59 56 47 4,输出样例：2,const maxn=100;var father,a:array1.maxn of integer;x,y:integer;procedure init;var a,b:integer;begin assign(input,treeaaa5.in);reset(input);readln(x,y);while not eof do begin readln(a,b);fathera:=b;end;close(input);end;,procedure find1;var i,j:integer;begin i:=x;while i0 do begin ai:=1;i:=fatheri;end;j:=y;while aj1 do j:=fatherj;writeln(j);end;BEGIN init;find1;END.,2、树的路径 给定一棵二叉树和两个不同的节点，求出他们最近的公共祖先父节点。已知该二叉树有n个节点，标号1.n。(n100)输入：第一行两个整数x，y，表示需要求的节点；以下若干行，每行两个整数a和b，表示a的父节点是b。输出：X到y的路径。,输入样例：9 72 13 24 25 38 59 56 47 4,输出样例：9 5 3 2 4 7,onst maxn=100;var father,a,b,c:array1.maxn of integer;x,y,root:integer;procedure init;var a,b:integer;begin assign(input,treeaaa4.in);reset(input);readln(x,y);while not eof do begin readln(a,b);fathera:=b;end;close(input);end;,procedure find1;var i,j:integer;begin i:=x;while i0 do begin ai:=1;i:=fatheri;end;j:=y;while aj1 do j:=fatherj;root:=j;writeln(root);end;,procedure find2;var i,j,k:integer;begin i:=0;while xroot do begin inc(i);bi:=x;x:=fatherx;end;inc(i);bi:=root;j:=0;while yroot do begin inc(j);cj:=y;y:=fathery;end;for k:=1 to i do write(bk,);for k:=j downto 1 do write(ck,);end;,BEGIN init;find1;find2;END.,