树及其应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线形结构,:,数据元素的逻辑位置之间呈,线性关系,，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。不管其存储方式（顺序和链式）如何,.,栈、队列,非线形结构,:,至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。,树、图,数据结构,:,一、树的概念,1,、树的定义,树是一种常见的非线性的数据结构：树型结构。,空树（不含结点）；非空树（至少一个结点）,树,树的递归定义如下：,树是,n(,n,=0,),个结点的有限集，这个集合满足以下条件：,有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；,除根外，其余的每个结点都有且仅有一个前驱；,除根外，每一个结点都通过,唯一,的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；,由上述定义可知，树结构没有封闭的回路。,思考：树中结点和边的关系,2,、结点的分类,结点一般分成三类,根结点：,没有父亲的结点。在树中有且仅有一个根结点。,分支结点：,除根结点外，有孩子的结点称为分支结点。,叶结点：,没有孩子的结点称为树叶。,根结点到每一个分支结点或叶结点的路径是,唯一,的。,从根,A,到结点,M,的唯一路径为,ADHM,。,3,、树的度,结点的度：,一个结点的,子树数目,称为该结点的度。,树的度：,所有结点中最大的度称为该树的度,(,宽度）。,4,、树的深度（,高度,）,树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有,4,层。在树中，父结点在同一层的所有结点构成兄弟关系。,树中最大的层次称为树的深度，亦称高度,。图中树的深度为,4,。,1,2,3,4,5,、森林,所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点,A,，,其原来的三棵子树,T,b,，,T,c,，,T,d,的集合,T,b,，,T,c,，,T,d,就为森林，这三棵子树的具体形态如图（,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,；,树数组,三、存储结构,1,2,3,4,5,6,7,8,9,10,11,12,13,下标,信息,儿子,1,A,2,3,4,2,B,5,6,0,3,C,7,0,0,4,D,8,9,10,5,E,11,12,0,6,F,0,0,0,7,G,0,0,0,8,H,13,0,0,9,I,0,0,0,10,J,0,0,0,11,K,0,0,0,12,L,0,0,0,13,M,0,0,0,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,jmax 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,又是二叉树；,二叉,树,二叉树和树的区别：,、树的每一个结点可以有任意多个孩子，而二叉树中每个结点的孩子数不能超过,2,；,、树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。,2,、下图列出二叉树的五种基本形态：,空二叉树,只有一个根,只有左孩子,只有右孩子,有左右孩子,3,、二叉树的两个特殊形态,满二叉树：如果一棵深度为,K,的二叉树，共有,2,K,-1,个结点，即第,I,层有,2,I-1,的结点，称为满二叉树。,(a),完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于,2,，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图,(b),）,(a),(b),4,、二叉树的三个主要性质,性质,1,：在二叉树的第,i,（,1,）,层上，最多有,2,i-1,个结点,性质,2,：在深度为,k(k1),的二叉树中最多有,2,k,-1,个结点。,性质,3,：在任何二叉树中，叶子结点数总比度为,2,的结点多,1,。,n,0,=n,2,+1,(,设,n,0,为二叉树的叶结点数；,n,2,为二叉树中度为,2,的结点数,),设,n,0,为二叉树的叶结点数；,n,1,为二叉树中度为,1,的结点数；,n,2,为二叉树中度为,2,的结点数，显然,n=n,0,+n,1,+n,2,（,1,）,由于二叉树中除了根结点外，其余每个结点都有且仅有一个分支进入。设,b,为二叉树的分支个数，,n=b+1,（,2,）,所有这些分支同时又为度为,1,和度为,2,的结点发出的。因此又有,b=n,1,+2n,2,(3),（,3,）代入（,2,）得出,n=n,0,+n,1,+n,2,(1),n=b+1 (2),b=n,1,+2n,2,(3),n=n,1,+2n,2,+1 (4),比较（,1,）和（,4,），得出,n,0,=n,2,+1,即叶子数比度为,2,的结点数多,1,。,例题：如果一棵,m,度的树中有,N,1,个度为,1,的顶点，,N,2,个度为,2,的顶点，,N,3,个度为,3,的顶点，,，,N,m,个度为,m,的顶点，求该树中叶子顶点个数。,分析：设叶子结点数为,N,0,所有结点数为,n,，,边数,(,分支）为,b,，,则有：,n=b+1,(1),又：,n=N,0,+N,1,+N,2,+.+N,M,(2),b=,N,1,+2N,2,+3N,3,+.+M*N,M,(3),(2),(3),代入（,1,）得出：,N,0,=N,2,+2N,3,+3N,4,+.+(M-1)N,M,+1,1,、,(NOIP9),一个高度为,h,的二叉树最小元素数目（,）。,A,）,2h+1B,）,h C,）,2h-1D,）,2hE,）,2h-1,2,、,(NOIP8),按照二叉数的定义，具有,3,个结点的二叉树有（）种。,A,）,3 B,）,4 C,）,5 D,）,6,3,、,(NOIP7).,一棵二叉树的高度为,h,，所有结点的度为,0,，或为,2,，则此树最少有,(),个结点,A)2h-1,B)2h-1,C)2h+1,D)h+1,4,、将一棵有,100,个结点的完全二叉树从根结点这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为,1,，则编号为,49,的结点的左孩子的编号为,A 98 B 99 C 97 D 50,5,、有,n,个结点并且其高度为,n,的二叉树的数目是,A,、,n B,、,2n C,、,2n-1 D,、,2,(n-1),B,C,B,A,D,6,、,(NOIP8),设有一棵,k,叉树，其中只有度为,0,和,k,两种结点，设,n,0,，,n,k,，分别表示度为,0,和度为,k,的结点个数，试求出,n,0,和,n,k,之间的关系（,n,0,=,数学表达式，数学表达式仅含,n,k,、,k,和数字）。,设结点总数为,n,，则：,n=n,0,+n,k,除了根结点外，其余每个结点都有且仅有一个分支进入,:,n-1=k*,n,k,所以：,n,0,=(k-1)*n,k,+1,二、二叉树的存储结构,二叉树的存储结构有两种形式,、顺序存储结构,、链式存储结构,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,种遍历方法：,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,从根开始的层次,A,1,、编程实现：二叉树的遍历（,tree1.pas,）,建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。,输入：第一行：结点个数,n,。,以下行：每行,3,个数，第一个是父亲，后两个依次为左右孩子。,输出：根及先、中、后序遍历结果。,样例输入：,8,1 2 4,2 0 0,4 8 0,3 1 5,5 6 0,6 0 7,8 0 0,7 0 0,样例输出：,3,3 1 2 4 8 5 6 7,2 1 8 4 3 6 7 5,2 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(t);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,bt,nil then,begin,write(bt.data,);,preorder(bt.lchild,);,preorder(bt.rchild,);,end;,end;,procedure,inorder(bt:btlink,);,begin,if,bt,nil then,begin,inorder(bt.lchild,);,write(bt.data,);,inorder(bt.rchild,);,end;,end;,procedure,sucorder(bt:btlink,);,begin,if,bt,nil 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,bt,nil 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,bt,nil then,begin,n:=n+1;,sum(bt.lchild,);,sum(bt.rchild,);,end;,end;,3,）设计算法求二叉树中度为,2,的结点数。,procedure sum2(bt:btlink);,begin,if,bt,nil then,begin,if(,bt.lchild,nil)and(bt.rchild,nil)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;,3,、树的公共祖先：,给定一棵二叉树和两个不同的节点，求出他们最近的公共祖先父节点。已知该二叉树有,n,个节点，标号,1.n,。,(n100),输入：,第一行两个整数,x,，,y,，,表示需要计算的节点；,以下若干行，每行两个整数,a,和,b,，,表示,a,的父节点是,b,。,输出：,X,与,y,的最近公共祖先,root,。,输入样例：,9 7,2 1,3 2,4 2,5 3,8 5,9 5,6 4,7 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.,4,、树的路径,给定一棵二叉树和两个不同的节点，求出他们最近的公共祖先父节点。已知该二叉树有,n,个节点，标号,1.n,。,(n100),输入：,第一行两个整数,x,，,y,，,表示需要求的节点；,以下若干行，每行两个整数,a,和,b,，,表示,a,的父节点是,b,。,输出：,X,到,y,的路径,。,输入样例：,9 7,2 1,3 2,4 2,5 3,8 5,9 5,6 4,7 4,输出样例：,9 5 3 2 4 7,const,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.,四、由二叉树的两种遍历顺序确定树结构,遍历二叉树（如下图）有三种规则：,前序遍历：根,左子树,右子树；,中序遍历：左子树,根,右子树；,后序遍历：左子树,右子树,根；,结论：,1,、已知先序和中序可以确定二叉树,2,、已知后序和中序可以确定二叉树,例：,先序,:,abdecf,中序,:,dbeafc,画出二叉树，写出后序遍历的结果。,2,、,(NOIP7),已知一棵二叉树的结点名为大写英文字母。中序遍历：,CBGEAFHDIJ,后序遍历：,CGEBHFJIDA,则该二叉树的先序遍历的顺序为：,3,、中序遍历：,DBGEACHFI,后序遍历：,DGEBHIFCA,求先序遍历结果,4,、,(NOIP6),已知，按中序遍历二叉树的结果为：,abc,问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。,1,、给出一棵二叉树的先序遍历：,ABCDEFGH,中序遍历：,CBEDAGHF,画出此二叉树并写出后序遍历结果。,【,例题,1】,根据两种遍历顺序确定树结构,输入：,二叉树的前序,遍历,顺序与中序,遍历,顺序,输出：,二叉树的后序,遍历,顺序,样例：,输入：,ABCDEFGHCBEDAGHF,输出：,CEDBHGFA,/,算法,1,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.,/,算法,2,function,work(sx,sz:string):string,;,var,l,k:integer,;,left,right:string,;,begin,if,sx,=then exit()else,begin,l:=,length(sx,);,k:=pos(sx1,sz);,left:=work(copy(sx,2,k-1),copy(sz,1,k-1);,right:=work(copy(sx,k+1,l-k),copy(sz,k+1,l-k);,work:=left+right+sx1;,end;,end;,Writeln(work(sx,sz,);,石子合并问题,有,n,堆石子,每堆有一个重量,每次,任选,2,堆石子合并成,1,堆,付出的代价为这两堆石子的重量之和,如果把这,n,堆石子最后合并成,1,堆石子,怎样合并才能使付出的代价最小,求出最小的代价,.,五、最优二叉树,(,哈夫曼树,),显然图,(D),所示的合并方法付出的代价最小,:54,例如,n=5,重量 分别为,7,、,5,、,2,、,4,、,6,。,2,4,6,5,11,6,7,13,24,(D)L=6+11+13+24=54,=5*2+2*3+4*3+6*2+7*2=54,1,、最优二叉树的定义,在具有,n,个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使,达到,最小,。,w,k,第,k,个叶结点的权值；,p,k,第,k,个叶结点的带权路径长度：第,k,个结点被合并的次数）,2,、最优二叉树的构造方法,假定给出,n,个结点,k,i,(i,=1n),，,其权值分别为,w,i,(i,=1n),。,要构造以此,n,个结点为叶结点的最优二叉树，其构造方法如下：,首先，将给定的,n,个结点构成,n,棵二叉树的集合,F=T,1,，,T,2,，,，,T,n,。,其中每棵二叉树,T,i,中只有一个权值为,w,i,的根结点,k,i,，,其左、右子树均为空。然后做以下两步,在,F,中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；,在,F,中删除这两棵二叉树，同时将新得到的二叉树加入,F,中；,重复、，直到在,F,中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。,以上构造最优二叉树的方法称为哈夫曼（,huffmann,）,算法。,例如：给定五个结点，其权值分别为,23,、,16,、,2,、,18,、,16,。,构造最优二叉树的过程如下：,构造初始集合,F,，,F,中各二叉树根结点的权值分别为,23,、,16,，,2,，,18,，,16,（如下图）：,16,18,2,16,23,16,18,2,16,23,18,34,41,75,23*2+16*3+2*3+18*2+16*2=168,构造费用,(,生成,n-1,个结点的和,)=18+34+41+75=168,哈夫曼树带权路径的长度,=,构造费用,合并石子,小,Ray,在河边玩耍，无意中发现一些很漂亮的石子堆，于是他决定把这些石子搬回家。河滩上共有,n,堆石子，小,Ray,在把石子搬回家之前首先要把这,n,堆石子合并为一堆石子。已知小,Ray,每次可以选择其中的两堆石子合并为一堆，合并一次石子他要消耗的体力是两堆石子的数量和。,请计算小,Ray,把,n,堆石子合并成一堆最少消耗的体力值是多少。,【,输入：,】,第一行：,n,（,=30000,）,.,第二行：那个用空格隔开的数，分别表示,n,堆石子的数量。,【,输出：,】,n,堆石子合并成一堆所消耗的最小体力值。,说明,:,分别用队列和堆两种算法实现。,【,样例输入：,】,3,1 2 4,【,样例输出：,】,10,在最优二叉树中非叶结点的度均为,2,，因此采用顺序存储结构为宜。如果带权叶结点数为,n,个，则最优二叉树的结点数为,2n-1,个。,由此得出最优二叉树的数据类型定义,Maxn,=30000;,n=,叶结点数的上限；,m=2*n-1,；,最优二叉树的结点数,Type,node=record ,结点类型,data,：,integer,；,权值,prt,，,lch,，,rch,：,longint,;,父指针、左、右指针和路径长度,end,；,Var,a,：,array1.maxn of,longint,；,其中,a 1n,为叶结点，,a n+12n-1,为中间结点，根为,a 2n-1,算法一,(,hafuman.pas,),procedure,creat,;/,创建哈夫曼树,var,i,j,k:longint,;,begin,sum:=0;/,费用,m:=2*n-1;,for k:=n+1 to m do,begin,i:=findmin(k-1);,ak.lch,:=i;,ai.prt,:=k;,j:=findmin(k-1);,ak.rch,:=j;,aj.prt,:=k;,ak.data,:=,ai.data+aj.data,;,sum:=,sum+ak.data,;,end;,end;,function,findmin(k:longint):longint,;,/,在前,k,个街道中找最小的结点，父结点为,0,var,min,i:longint,;,begin,min:=,maxlongint,;,for i:=1 to k do,if(,ai.data,min)and(ai.prt,=0)then,begin min:=,ai.data,;,findmin,:=i;end;,end;,Sum,是所求的费用,时间复杂度：,O(n,2,),，无法完成,n=3000,算法二（,stone.pas,）,设置两个队列：,a,，,b,队列,a,：保存初始的,n,个叶结点，从小到大排序。,队列,b:,依次放生成的新结点，递增的。,生成结点过程：,Mindata,=minaopena+aopena+1;,bopenb+bopenb+1;,aopen+bopen,Inc(closedb,);,Bclosedb,=,mindata,;,采用快速排序；时间复杂度：,O,（,n*,long(n,),）,合并的时间复杂度：,O,（,n,）,总的时间复杂度：,O,（,n*,long(n,),）,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,C,B,A,4,）,(NOIP6),在有,N,个叶子节点的哈夫曼树中，其节点总数为（）,A.,不确定,B.2N-1,C.2N+1,D.2N,B,六、树、森林转换成二叉树,1,、普通有序树转换成二叉树,普通树为有序树,T,，,将其转化成二叉树,T,的规则如下：,将有序树,T,中每个结点,X,的第一个孩子结点转化为二叉树,T,中对应,X,的左孩子,L,，原树,T,中结点,X,的第二个孩子转化为二叉树,T,中,L,的右孩子,R1,，原树,T,中结点,X,的第三个孩子转化为二叉树,T,中,R1,的右孩子,R2,，依次类推。,4,1,2,3,5,6,8,7,转化后的二叉树根结点无右孩子,2,、森林转换成二叉树,森林转换成二叉树的方法为,将森林中的每棵树转换成相应的二叉树；,将各棵树的根相连；,以第一棵树为轴心，顺时针粗略地旋转,90,0,；,