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

《算法与数据结构讲义四(数据结构——树)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第十四课数据结构——树12.0树型结构12.1树的应用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)森林：由m（m>

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

4、ammaketree;//时间复杂度O(nlogn)constmaxn=12;varinf,outf:text;bian:array[1..maxn,1..2]ofinteger;//存储边集tree,num:array[1..maxn]ofinteger;//存储树、各节点的度t:array[1..maxn]ofboolean;//哈希n,m,i,j,k:integer;///////////////////////////////////////////////procedureinit;beginassign(inf,'maketree.in');assign(outf,'maket

5、ree.out');reset(inf);readln(inf,n,m);fori:=1tomdobeginreadln(inf,bian[i,1],bian[i,2]);inc(num[bian[i,1]]);inc(num[bian[i,2]]);//统计各节点的度end;end;///////////////////////////////////////////////proceduremake;begini:=1;k:=0;fillchar(t,sizeof(t),true);whilek1doi:=imodn+1;//查找度为1的节点

6、j:=1;whilenot(t[j]and((bian[j,1]=i)or(bian[j,2]=i)))doinc(j);//找到包含该ifj>nthenbreak;//节点的边t[j]:=false;ifbian[j,1]=ithentree[i]:=bian[j,2];ifbian[j,2]=ithentree[i]:=bian[j,1];dec(num[bian[j,1]]);dec(num[bian[j,2]]);inc(k);end;end;///////////////////////////////////////////////procedureprint;beginrew

7、rite(outf);fori:=1tondowrite(outf,i:3);writeln(outf);fori:=1tondowrite(outf,tree[i]:3);close(outf);end;///////////////////////////////////////////////begininit;make;print;end.2、孩子表示法：（一般二叉树使用）1234567891011ABCDEFG