《算法与数据结构讲义四数据结构树》由会员分享，可在线阅读，更多相关《算法与数据结构讲义四数据结构树（15页珍藏版）》请在金锄头文库上搜索。
1、第十四课 数据结构树12.0 树型结构12.1树的应用12.2 二叉树及其应用12.3 霍夫曼二叉树12.4 线段树12.0 树型结构（一）树的定义树是一种数据结构，它是由n（n=1）个有限结点组成一个具有层次逻辑关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：(1)每个结点有零个或多个子结点； (2)每一个子结点只有一个父结点； (3)没有前驱的结点为根结点； (4)除了根结点外，每个子结点可以分为m个不相交的子树； （二）树的有关术语(1)节点的度：一个节点含有的子树的个数称为该节点的度； (2)叶节点或终端节点：度为零的节点称为叶
2、节点； (3)非终端节点或分支节点：度不为零的节点； (4)双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点； (5)孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； (6)兄弟节点：具有相同父节点的节点互称为兄弟节点； (7)树的度：一棵树中，最大的节点的度称为树的度； (8)节点的层次：从根开始定义起，根为第0层，根的子结点为第1层，以此类推； (9)树的高度或深度：树中节点的最大层次； (10)堂兄弟节点：双亲在同一层的节点互为堂兄弟； (11)节点的祖先：从根到该节点所经分支上的所有节点； (12)子孙：以某节点为根的子树中任一节点都称为该节点的子
3、孙。 (13)森林：由m（m=0）棵互不相交的树的集合称为森林；（三）树的物理存储 一般使用数组来线性存储树中各节点的数据本身，但为了记录各节点之间的父子关系，需要附加存储父亲或孩子节点所在的位置。1、 双亲表示法：可以存储为： ABCDEFGHIJK11124455571 2 3 4 5 6 7 8 9 10 11优点：（1） 节省空间。（2） 便于从下向上访问（记录了从孩子到父亲的逻辑关系）。（3） 便于随时插入新的子树。缺点：不利于从上向下的访问。（未记录父亲到孩子的逻辑关系）。例如：利用所给边集创建双亲表达树输入：第一行两个整数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); re
5、adln(inf,n,m); for i:=1 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); /找到包含该
6、if jn then break; /节点的边 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
7、 init; make; print;end. 2、孩子表示法：（一般二叉树使用） 1 2 3 4 5 6 7 8 9 10 11ABCDEFGHIJK256811379410优点：（1） 便于从上向下的访问。（2） 便于随时删除子树。缺点：占用空间过大且不确定（使用链表时例外）。3、混合表示法：既记录双亲关系又记录孩子关系。12.1 树的应用（一）并查集并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 并查集的存储一般采用双亲表示法。一般为了提高使用效率，会附加储存一些信息，如：该节点下属节点个数、该节点到达根的距离
8、等。1、基本操作：一开始时，所有元素都分属于各个独立的集合。（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）判断两个结点是否属于一个集合：f
9、unction same(x,y:integer):boolean;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_fa
10、ther(x); yy:=get_father(y); if 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; father
11、x:=xx; x:=y; end;end;3、例题：(1) 亲戚(Relations)或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及.在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和B en是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关心的亲戚关系的提问，以最快的速度给出答案。输入格式 输入由两部分组成。第一部分以N，M开始。N为问题涉及的人的个数(1 N 20000)。这些人的编号为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。样例输入与输出输入relation.in10 72 45 71 38 91 25 62 333 47 108 9输出relation.outYes
