第三讲：树及其应用.ppt

《第三讲：树及其应用.ppt》由会员分享，可在线阅读，更多相关《第三讲：树及其应用.ppt（66页珍藏版）》请在三一办公上搜索。

1、第三讲:树及其应用,一、.树的概念1、树的定义 树是一种非线性的数据结构。,树的递归定义如下：树是n(n0)个结点的有限集，这个集合满足以下条件：有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；除根外，其余的每个结点都有且仅有一个前驱；除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；由上述定义可知，树结构没有封闭的回路。,2、结点的分类 结点一般分成三类根结点：没有父亲的结点。在树中有且仅有一个根结点。分支结点：除根结点外，有孩子的结点称为分支结点。叶结点：没有孩子的结点称为树

2、叶。根结点到每一个分支结点或叶结点的路径是唯一的。从根A到结点M的唯一路径为ADHM。,3、树的度结点的度：一个结点的子树数目称为该结点的度。树的度：所有结点中最大的度称为该树的度(宽度）。下列树的宽度为3,4、树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图中树的深度为4。,5、森林 所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点A，其原来的三棵子树Tb，Tc，Td的集合Tb，Tc，Td就为森林，这三棵子树的具体形态如图

3、（c）。,6、有序树和无序树 按照树中同层结点是否保持有序性，可将树分为有序树和无序树。(1)如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；(2)如果同层结点的次序任意，这样的树称为无序树。,二、树的表示方法和存储结构1、树的表示方法树的表示方法一般有两种：自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。,优点:直观,形象;缺点:保存困难.,括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括

4、号括起来。例如图可写成如下形式(A(B(E(K,L),F),C(G),D(H(M),I,J)优点:易于保存;缺点:不直观.,2、树的存储结构树的存储结构一般有两种静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n 为树的度)的数组，分别存储该结点的每一个儿子的下标Const n=树的度；max=结点数的上限；Type node=record 结点类型 data：datatype；数据域 ch：array1n of integer；指向各儿子的下标 end；treetype=array1.maxof node；Var tree：treetype；树数组,I d

5、ata ch1.m,动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下：Const n=树的度；Type treetype=node；结点类型 node=record data：datatype；数据域 next：array1n of treetype；指向各儿子的指针域 end；Var root：treetype；根结点指针,1、树的统计输入森林中的结点关系，统计森林中树的数量，输出树的根。输入：第一行：n：结点数量；k：边数；（n,k=100）以下k行：每行两个结点编号

6、：i，j：i是j的父结点(I,j=100)。输出：第一行：树的数量。第二行：依次输出森林中树的根结点编号（从小到大）。样例输入：9 71 22 34 64 57 89 1 9 4输出：27 9,应用:,var f:array1.100of integer;fi：记录结点i的父亲 i,j,k,m,n,t,x,y,p,q:integer;begin readln(n,k);for i:=1 to n do fi:=0;默认根标志是本身，各自是独立的一棵树 for i:=1 to k do begin readln(x,y);fy:=x;end;t:=0;for i:=1 to n do if fi

7、=0 then inc(t);统计根的个数 writeln(t);for i:=1 to n do if fi=0 then write(fi,);end.,2、找树根和孩子（treea.pas）给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。,输入：第一行：n（结点个数），m（边数）。以下m行；每行两个结点x和y，表示y是x的孩子。输出：第一行：树根：root。第二行：孩子最多的结点max。第三行：max的孩子。,样例输入：8 74 14 21 31 52 62 72 8,样例输出：42 6 7 8,const maxn=100;type treetype=record 结

8、点类型 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 readln(n,m);for i:=1 to m do begin readln(x,y);treey.father:=x;inc(treex.num);孩子数量加1 treex.childtreex.num:=y;end;end;,function r

9、oot:integer;找树根：父亲结点为0的结点 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;k：孩子最多的结点 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.chi

10、ldi,);writeln(treek.childmax);end;BEGIN init;writeln(root);find;END.,三、二叉树的概念 二叉树的特点:是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。1、二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；,二叉树和树区别：树的每一个结点可以有任意多个孩子，而二叉树中每个结点的孩子数不能超过2；树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分

11、。左儿子和右儿子。下图列出二叉树的五种基本形态：,2、二叉树的两个特殊形态满二叉树：如果一棵深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。(a)完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）,(a),(b),3、二叉树的三个主要性质性质1：在二叉树的第i（1）层上，最多有2i-1个结点性质2：在深度为k(k1)的二叉树中最多有2k-1个结点。性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。n0=n2+1(设n0为二叉树的叶结点数；n2为二叉树中

12、度为2的结点数),设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然 n=n0+n1+n2（1）由于二叉树中除了根结点外，其余每个结点都有且仅有一个边指向父亲。设 b为二叉树的边的个数，n=b+1（2）所有这些分支同时又为度为1和度为2的结点发出的。因此又有 b=n1+2n2(3),由1，2，3得到：n0=n2+1,【试题分析】：如果一棵m度的树中有N1个度为1的顶点，N2个度为2的顶点，N3个度为3的顶点，Nm个度为m的顶点，求该树中叶子顶点个数。,分析：设叶子结点数为N0 所有结点数为n，边数(分支）为b，则有：n=b+1(1)又：n=N0+N1+N

13、2+.+NM(2)b=N1+2N2+3N3+.+M*NM(3)(2),(3)代入（1）得出：N0=N2+2N3+3N4+.+(M-1)NM+1,(NOIP9)一个高度为h 的二叉树最小元素数目（）。A）2h+1B）h C）2h-1D）2hE）2h-1(NOIP8)按照二叉数的定义，具有3个结点的二叉树有（）种。A）3 B）4 C）5 D）6(NOIP8)设有一棵k叉树，其中只有度为0和k两种结点，设n 0，n k，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0=数学表达式，数学表达式仅含n k、k和数字）。,(NOIP7).一棵二叉树的高度为h，所有结点的度为0，或

14、为2，则此树最少有()个结点A)2h-1 B)2h-1 C)2h+1 D)h+1,四、树或森林转换成二叉树1、树转化为二叉树一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。例如将下图（a）所示的普通有序树转换成二叉树(下图（b）)。,2、森林转换成二叉树 将森林中的每棵树转换成相应的二叉树；将各棵树的根相连；以第一棵树为轴心，顺时针粗略地旋转900；,五、二叉树的存储结构二叉树的存储结构有两种形式顺序存储结构链式存储结构,1、顺序存储结构将每个结点依次存放在一维数组中，用数组下标指示结点编号

15、，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括Const m=树中结点数上限；Type node=record 结点类型 data：datatype；数据值 prt，lch，rch：0m父结点、左儿子、右儿子编号 end；treetype=array1m of node；二叉树的顺序表类型Var Tree：treetype；二叉树,例如，采用数组tree存储二叉树（如下图）,2、链式存储结构 对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。由于二叉树中每个结点通常包括数

16、据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：值域：data左指针域：lch右指针域：rch这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点,Type bitrpetr=bnode；结点指针类型 benode=record 结点类型 data：datatype；值域 lch，rch：bitreptr；左指针域和右指针域 end；Var bt：bitreptr；头指针,例如用下图（b）所示的二叉链表存储二叉树（下图（a）,六、二叉树的遍历(访问)所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。如果用L、D、R分别表示遍历左子树、访问根结点、遍历右

17、子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、LRD、DLR、DRL、RDL、RLD若再限定先左后右的次序，则只剩下三种组合 DLR、LDR、LRD这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。,、前（根）序遍历前序遍历的规则如下：若二叉树为空，则退出。否则 访问处理根结点；前序遍历左子树；前序遍历右子树；a b d e h i c f g,中序遍历中序遍历的规则如下：若二叉树为空，则退出；否则 中序遍历左子树；访问处理根结点；中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列：d b h e i a f c g,后序遍历后序遍历的规则如

18、下：若二叉树为空，则退出；否则 后序遍历左子树；后序遍历右子树；访问处理根结点；若后序遍历上图中的二叉树，可以得到如下的后序序列 d h i e b f g c a,1、将一棵有100个结点的完全二叉树从根结点这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为 A 98 B 99 C 97 D 502、对二叉树从1进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的 编号，则可以采取 次序的遍历方法。A 先序 B中序 C后序 D从根开始的层次遍历3、有n个结点并且其高度为n的二叉树的数目是 A、

19、n B、2n C、2n-1 D、2(n-1),4.写出二叉树三种序遍历结果,1、编程实现：二叉树的遍历（tree1.pas）建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。输入：第一行：结点个数n。以下行：每行3个数，第一个是父亲，后两个依次为左右孩子，0表示空。输出：根、先中后序遍历结果。,样例输入：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:i

20、nteger;父亲 lch,rch:integer;lch：左孩子；rch：右孩子 end;var tree:array1.maxn of treetype;n,m,t:integer;procedure init;var f,l,r,i:integer;begin 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:in

21、teger;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(tr

22、eet.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.,遍历算法的简单变化：1)设计算法按照从左向右的顺序输出二叉树的叶子结点。,procedure preorder(t:integer);先序 begin if

23、t0 then begin if(treet.lch=0)and(treet.rch=0)then write(t,);左右孩子都空 preorder(treet.lch);preorder(treet.rch);end;end;,2）设计算法求二叉树中度为2的结点数。,procedure preorder(t:integer);先序 begin if t0 then begin if(treet.lch0)and(treet.rch0)then write(t,);左右孩子都不空 preorder(treet.lch);preorder(treet.rch);end;end;,3）设计算法求

24、二叉树的深度。,function high(t:integer):integer;求以t为根的树的深度 var a,b:integer;begin if t=0 then high:=0 else begin a:=high(treet.lch);左子树的高度 b:=high(treet.rch);右子树的高度 if ab then high:=a+1 else high:=b+1;end;end;,七、由二叉树的两种遍历顺序确定树结构遍历二叉树（如下图）有三种规则：前序遍历：根左子树右子树；中序遍历：左子树根右子树；后序遍历：左子树右子树根；,2、(NOIP7)已知一棵二叉树的结点名为大写英

25、文字母，中序：CBGEAFHDIJ后序：CGEBHFJIDA该二叉树的先序遍历的顺序为：,1、已知先序遍历结果：ABCDEFGH中序遍历结果：CBEDAGHF求后序遍历结果。,【例题1】根据两种遍历顺序确定树结构输入：二叉树的前序遍历顺序与中序遍历顺序输出：二叉树的后序遍历顺序样例：输入：ABCDEFGHCBEDAGHF输出：CEDBHGFA,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);根在中序

26、的位置 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)所示的合并方法付出

27、的代价最小:54,例如n=5,重量 分别为7、5、2、4、6。,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的根

28、结点ki，其左、右子树均为空。然后做以下两步 在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；在F中删除这两棵二叉树，同时将新得到的二叉树加入F中；重复、，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。以上构造最优二叉树的方法称为哈夫曼（huffmann）算法。,例如：给定五个结点k1，k2，k3，k4，k5，其权值分别为16、2、18、16、23。构造最优二叉树的过程如下：构造初始集合F，F中各二叉树根结点的权值分别为16，2，18，16，23（如下图）：,最后得到最优二叉树（如下图），其根结点的

29、权值为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

30、 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 fi

31、llchar(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

32、。请进行哈夫曼编码。使通讯码尽可能的短 并写出信息：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、树的公共祖先：给定一棵二叉树和两个不同的节点，求出

33、他们最近的公共祖先父节点。已知该二叉树有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 readln(x,y);while not eof do begin readln(a,b);fathera

34、:=b;end;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 2

35、5 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 readln(x,y);while not eof do begin readln(a,b);fathera:=b;end;end;,procedure findroot;找树根 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;end;,procedure finda(i:integer);begin if iroot then begin write(i,);finda(fatheri);end;end;procedure findb(i:integer);begin if iroot then begin findb(fatheri);write(i,);end;end;,BEGIN init;findroot;finda(x);找x到根的路径 write(root,);findb(y);找根到y的路径END.,