算法与数据结构讲义四(数据结构-树)

1、第十四课 数据结构树12.0 树型结构12.2 二叉树及其应用12.3 霍夫曼二叉树12.4 线段树12.0 树型结构（一）树的定义树是一种数据结构，它是由n（n=1）个有限结点组成一个具有层次逻辑关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：(1)每个结点有零个或多个子结点； (2)每一个子结点只有一个父结点； (3)没有前驱的结点为根结点； (4)除了根结点外，每个子结点可以分为m个不相交的子树； （二）树的有关术语(1)节点的度：一个节点含有的子树的个数称为该节点的度； (2)叶节点或终端节点：度为零的节点称为叶节点； (3)非

2、终端节点或分支节点：度不为零的节点； (4)双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点； (5)孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； (6)兄弟节点：具有相同父节点的节点互称为兄弟节点； (7)树的度：一棵树中，最大的节点的度称为树的度； (8)节点的层次：从根开始定义起，根为第0层，根的子结点为第1层，以此类推； (9)树的高度或深度：树中节点的最大层次； (10)堂兄弟节点：双亲在同一层的节点互为堂兄弟； (11)节点的祖先：从根到该节点所经分支上的所有节点； (12)子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 (13)森

3、林：由m（m=0）棵互不相交的树的集合称为森林；（三）树的物理存储 一般使用数组来线性存储树中各节点的数据本身，但为了记录各节点之间的父子关系，需要附加存储父亲或孩子节点所在的位置。双亲表示法：可以存储为： ABCDEFGHIJK11124455571 2 3 4 5 6 7 8 9 10 11优点：节省空间。便于从下向上访问（记录了从孩子到父亲的逻辑关系）。便于随时插入新的子树。缺点：不利于从上向下的访问。（未记录父亲到孩子的逻辑关系）。例如：利用所给边集创建双亲表达树输入：第一行两个整数n，m，表示节点个数和边的条数 下面m行，每行2个整数，表示两个节点存在父子关系输出：如上的双亲表示法的

4、树program maketree;/时间复杂度O(nlogn)const maxn=12;var inf,outf:text; bian:array1.maxn,1.2of integer;/存储边集 tree,num:array1.maxnof integer;/存储树、各节点的度 t:array1.maxnof boolean;/哈希 n,m,i,j,k:integer;/procedure init;begin assign(inf,maketree.in); assign(outf,maketree.out);reset(inf); readln(inf,n,m); for i:=1

5、 to m do begin readln(inf,biani,1,biani,2); inc(numbiani,1); inc(numbiani,2); /统计各节点的度 end;end;/procedure make;begin i:=1; k:=0; fillchar(t,sizeof(t),true); while km do begin while numi1 do i:=i mod n+1;/查找度为1的节点 j:=1; while not(tjand(bianj,1=i)or(bianj,2=i) do inc(j); /找到包含该 if jn then break; /节点的边

6、 tj:=false; if bianj,1=i then treei:=bianj,2; if bianj,2=i then treei:=bianj,1; dec(numbianj,1); dec(numbianj,2); inc(k); end;end;/procedure print;begin rewrite(outf); for i:=1 to n do write(outf,i:3); writeln(outf); for i:=1 to n do write(outf,treei:3); close(outf);end;/begin init; make; print;end.

7、 2、孩子表示法：（一般二叉树使用） 1 2 3 4 5 6 7 8 9 10 11ABCDEFGHIJK256811379410优点：便于从上向下的访问。便于随时删除子树。缺点：占用空间过大且不确定（使用链表时例外）。3、混合表示法：既记录双亲关系又记录孩子关系。12.1 树的应用（一）并查集并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 并查集的存储一般采用双亲表示法。一般为了提高使用效率，会附加储存一些信息，如：该节点下属节点个数、该节点到达根的距离等。1、基本操作：一开始时，所有元素都分属于各个独立的集合。（

8、1）查找某结点的根：function get_father(x:integer):integer;/传入待查找的结点序号begin while fatherx0 do x:=fatherx; get_father:=x;end; （2）合并两个不相交的集合：procedure join(x,y:integer);var xx,yy:integer;begin xx:=get_father(x); yy:=get_father(y); if xxyy then fatherxx:=yy;end; （3）判断两个结点是否属于一个集合：function same(x,y:integer):boole

9、an;begin if get_father(x)=get_father(y) then same:=true else same:=false;end; 2、并查集的优化：并查集在使用时，一旦结点多起来，就有可能退化成为一条链，这时，查找结点的祖先或判断两个结点是否是同一集合的复杂度就会称为O(n)。（1）合并时将元素所在深度低的集合合并到元素所在深度高的集合。 （附加存储集合中根的深度ranki）procedure join_rank(x,y:integer);var xx,yy:integer;begin xx:=get_father(x); yy:=get_father(y); if

10、rankxxrankyy then fatheryy:=xx else fatherxx:=yy; if rankxx=rankyy then inc(rankyy);end;（2）路径压缩我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。function get_father(x:integer):integer;var xx,y:integer;begin xx:=x; while fatherxx0 do xx:=fatherxx; while fatherxxx do begin y:=fatherx; fatherx:=xx; x:=y; end;end;3、例题：(1) 亲

11、戚(Relations)或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和B en是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关心的亲戚关系的提问，以最快的速度给出答案。输入格式 输入由两部分组成。第一部分以N，M开始。N为问题涉及的人的个数(1 N 20000)。这些

12、人的编号为1,2,3,N。下面有M行(1 M 1000000)，每行有两个数ai, bi，表示已知ai和bi是亲戚.第二部分以Q开始。以下Q行有Q个询问(1 Q 1 000 000)，每行为ci, di，表示询问ci和di是否为亲戚。对于每个询问ci, di，若ci和di为亲戚，则输出Yes，否则输出No。样例输入与输出输入rela10 72 45 71 38 91 25 62 333 47 108 9输出relaYesNoYes(2) 银河英雄传说【问题描述】 公元五八一年，地球居民迁移至金牛座第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九

13、年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, , 30000。之后，他把自己的战舰也依次编号为1, 2, , 30000，让第i号战舰处于第i列(i = 1, 2, , 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i

14、号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特

15、的询问。 最终的决战已经展开，银河的历史又翻过了一页【输入文件】输入文件galaxy.in的第一行有一个整数T（1=T=500,000），表示总共有T条指令。以下有T行，每行有一条指令。指令有两种格式：1.M i j ：i和j是两个整数（1=i , j=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。2.C i j ：i和j是两个整数（1=i , j=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。【输出文件】输出文件为g。你的程序应当依次对输入的每一条指令进行分析和处理：如果是杨威利发布的

16、舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。【样例输入】4M 2 3C 1 2M 2 4C 4 2【样例输出】-11【样例说明】战舰位置图：表格中阿拉伯数字表示战舰编号第一列第二列第三列第四列初始时1234M 2 31324C 1 21号战舰与2号战舰不在同一列，因此输出-1M 2 41432C 4 24号战舰与2号战舰之间仅布置了一艘战舰，编号为3，输出1算法分析：构建压缩

17、路径的并查集，同时用一个数组behind记录各结点到集合祖先结点的距离、一个数组num记录各集合祖先所拥有的子结点个数。1)当A集合合并到B集合中时，A集合各结点的behind不变，树根的num值等于原numA值加B集合根的numB值；B集合各结点的behind值等于各结点原来的behind值加上numA。 2)查询时，当战舰i与战舰j属于同一集合时，其间的战舰数量等于：|behindi-behindj|-1（二）trie索引树Trie树是搜索树的一种。既可以用于字典搜索，又可以用于索引查找。其核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。1、trie树示

18、意图：2、trie树的性质：1）字符串中字符种数决定结点的单元数，结点中单元的下标为字符。2）用孩子表示法保存树的逻辑结构，某字符对应的单元存储的值为0表示该字符非后续字符，等于其它值时表示该字符是后续字符，且下一个后续字符位于其值指向的结点。3）可以采用标记法确定到该结点时，是否是一个完整的字符串。4）插入、查找的复杂度均为O(length(s)。3、trie树的操作：1）根据所给字符串创建trie树：trie定义为：array0.maxn,a.zof longint;procedure make_trie(s:string); /s为需要建立索引的字符串var i,l:integer;be

19、gin l:=length(s); p:=0; for i:=1 to l do begin if triep,si=0 then begin inc(d);/d为全局变量，记录trie数组当前 triep,si:=d;/已使用的单元数。 end; p:=triep,si; end; tp:=true; /当索引到p时，可以是一个单词的结束end; 2）查找function seach(s:string):boolean;var i,p,l:integer;begin l:=length; seach:=true; p:=0; for i:=1 to l do begin p:=triep,s

20、i;/当前字母找到，转下一个结点继续查找 if p=0 then/如果没有下一个字母，则返回找不到信息 begin seach:=false; break; end; end; if not(tp) then seach:=false;/即使该单词字母已全部找到，但仅仅是前缀end; 4、例题：1）有200000个长度不超过10个字母的单词组成的字典，现给一个长度为100000的字符串，问：该字符串包含多少个单词。2）最长前缀（文件名：Prefix.pas） 【问题描述】一些生物体的复杂结构可以用其基元的序列表示，而一个基元用一个大写英文字符串表示。生物学家的一个问题就是一个这样的长序列分解为

21、基元（字符串）的序列。对于给定的基元集合P，如果可以从中选出N个基元P1，P2，P3，.,Pn，将它们各自对应的字符串依次连接后得到一个字符串S，称S可以由基元集合P构成。在从P中挑选基元时，一个基元可以使用多次，也可不用。例如，序列 ABABACABAAB 可以由基元集合A，AB，BA，CA，BBC 构成。 字符串的前K个字符为该字符串的前缀，其长度为K。请写一个程序，对于输入的基元集合P和字符串T，求出一个可以由基元集合P构成的字符串T的前缀，要求该前缀的长度尽可能长，输出其长度。 【输入数据】 第一行是基元集合P中的基元数目N（1=N=100）,随后有2N行，每两行描述一个基元，第一行为

22、该基元的长度L（1=L=20）。随后一行是一个长度为L的大写英文字符串，表示该基元。每个基元互不相同。 最后一行描述要处理的字符串T，T由大写字母组成，最后一行是一个字符.,表示字符串结束。T的长度最小为1，最大不超过500000。 【输出数据】 只有一行，一个数字，表示可以由P构成的T的最长前缀的长度。 【样例】 prefix.in 51A2 AB 3BBC 2CA 2BA ABABACABAABCB. prefix.out 1112.3 二叉树及其应用一、概念：二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”和“右子树”。二叉树的子树有左右之分，次序不能颠倒。二叉树也是

23、递归定义的。二叉树常用于二叉查找树和二叉堆。二、二叉树与树的区别：1、二叉树结点的最大度数为2，而树的结点的最大度数没有限制。2、二叉树的结点有左、右之分，而树的结点是无序的。三、二叉树的相关术语：（1）结点的度。结点所拥有的子树的个数称为该结点的度。（2）叶结点。度为0的结点称为叶结点，或者称为终端结点。（3）分支结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。它又是子树的根。（4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（5）路径、路径长度。如果一

24、棵树的一串结点n1,n2,nk有如下关系：结点ni是ni+1的父结点（1i1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i1，则序号为i的结点是根结点，无双亲结点。 （2）如果2in，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。 （3）如果2i1n，则序号为i的结点的右孩子结点的序号为2i1；如果2i1n，则序号为i的结点无右孩子。五、二叉树的物理存储：1、对于满二叉树或完全二叉树，一般采用一维数组，只存储结点数据即可，其逻辑关系可根据二叉树的性质直接确定。对于下标为i的结点，其双亲结点位置的下标为i/2，其左孩子结点位置的下标为2*i

25、、右孩子结点位置的下标为2*i+1。如：堆、线段树的存储。2、对于非满二叉树，如果使用第一种方法存储，则空间过于浪费，一般采用地址标记法存储，且由于二叉树的度是不超过2的，因此，主要采用孩子表示法。如：可记录为：结点数据ABCDEFGHI双亲地址011223355左子树地址2468右子树地址3579实际使用时，可根据需要省去双亲地址的记录。六、二叉树的基本操作：var tree:array1.maxn,1.3of integer;1、初始化一棵空二叉树：Fillchar(tree,sizeof(tree),0) ;2、将新数据作为结点插入到树中，根据数据属性，大于根则插入到右子树、小于根插入到

26、左子树中。基本框架：procedure make_tree(待插入数据; 结点地址); /递归子程序，主程序调用时地址为1。begin if 待插入数据的属性当前根结点数据的属性 then begin if 左结点为空 then 插入为左结点 else make_tree(待插入数据,左结点地址); end else begin if 右结点为空 then 插入为右结点 else make_tree(待插入数据,右结点地址)； end;end;3、在二叉树中查找数据元素，如果存在返回数据的地址，若不存在则返回0： 基本框架：function find(需查找数据; 结点地址):integer;

27、 /主程序调用时结点地址为1。begin if 当前根结点数据需查找数据 then begin if 需查找数据的属性当前根结点数据的属性 then begin if 左子树不为空 then find:=find(需查找数据; 左子树地址) else find:=0; end else begin if 右子树不为空 then find:=find(需查找数据; 右子树地址) else find:=0； end; end else find:=当前根的地址;end;4、二叉树的遍历：二叉树的遍历有三种基本的方式：（1）先序遍历：先访问树的根，再访问左子树，最后访问右子树。如：右图先序遍历结果ABDCEGHFI（2）中序遍历：先访问左子树，再访问根，最后访问右子树。 DBAGEHCIF（3）后序遍历：先访问左子树，再访问右子树，最后访问根。DBGHEIFCA算法框架：(1)前序遍历procedure pre_tra(结点地址);begin 输出当前结点; pre_tra(左结点地址); pre_tra(右结点地址)；end; (2)中序遍历procedure mid_tra(结点地址);begin pre_tra(左结点地址); 输出当前结点; pre_tra(右结点地址)；en