【精品课件】树型结构.ppt

《【精品课件】树型结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章　树型结构树的基本概念树的遍历树的线性表示树类的定义树的存储结构6.1树的基本概念树是由n(n≥0)个结点构成的有限集合，n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：(1)有且仅有一个特定的结点称之为根；(2)其余结点分成m(m≥0)个互不相交的有限集合T1,T2,……Tm，其中每一个集合又都是一棵树，称T1,T2,……Tm为根结点的子树。BDEFGAHIJKC图6.1在树中采用线段连接两个相关联的结点，如A和B，D和H等。其中A和D是上端结点，B和H是下端结点。称A、D分别是B、H的双亲（或父母或前件），B和H分别为A和D的

2、子女（或孩子或后件）。显然，双亲和子女的关系是相对而言的。图6.1中，B是A的子女，但又是E和F的双亲。由于E和F的双亲为同一结点，称E和F互为兄弟。在任何一棵树中，除根结点外，其它任何一个结点有且仅有一个双亲，有0个或多个子女，且它的子女恰巧为其子树的根结点。我们将一结点拥有的子女数称为该结点的度，树中所有结点度的最大值称为树的度。图6.1中，A的度为3，B的度为2，而C的度为0，整棵树的度为3。称度为0的结点为终端结点或叶子结点，称度不为0的结点为非终端结点或分支结点。显然，A、B、D、H均为分支结点，而E、F、C、G、J、K、I均为叶子结点。称树中连接

3、两个结点的线段为树枝。在树中，若从结点Ki开始沿着树枝自上而下能到达结点Kj，则称从Ki到Kj存在一条路径，路径的长度等于所经过的树枝的条数。在图6.1中，从结点A到结点J存在一条路径，路径的长度为3；从D到K也存在一条路径，路径的长度为2。仔细观察不难发现，从树根到树中任何一个结点均存在一条路径。将从树根到某一结点Ki的路径中Ki前所经过的所有结点称为Ki的祖先；反之，以某结点Ki为根的子树中的任何一个结点都称为Ki的子孙。图6.1中，A、D、H均为J和K的祖先，而G、H、I、J和K均为D的子孙。树中结点的层次：从树根开始定义，根结点为第一层，根的子女结点

4、构成第二层，依次类推，若某结点Kj位于第i层，则其子女就位于第i+1层。称树中结点的最大层次数为树的深度或高度。图6.1中，A结点位于第一层，B、C、D位于第2层，E、F、G、H和I位于第三层等等，整棵树的高度为4。若树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是有序树；否则称之为无序树。下图6.3中的两棵树，若看成是有序树，它们是不等价的；若看成是无序树，两者相等。DCEFABDEFAB由m(m≥0)棵互不相交的树构成的集合称为森林。森林和树的概念十分相近，一棵树中每个结点，其子树的集合即为一个森林；而在森林中的每棵树之上加一个共同的

5、根，森林就成为了一棵树。C图6.3有序树和无序树的比较树型结构的其他表示方法：A(B(E,F),C,D(G,H(J,K),I))(a)图6.1的括号表示法BHJKGIEFDCA(b)图6.1的嵌套集合表示法ABEFCDGHJKI(C)图6.1的凹入表示法6.2树类的定义ADTtree{数据对象D：具有相同性质的数据元素构成的有限集合。数据关系R：如果D为空或D仅含一个元素，则R为空；否则D中存在一个特殊的结点root，称之为根结点，其无前驱；其它结点被分成互不相交的m(m0)个集合，分别构成root的m棵子树；若这些子树非空，则它们的根结点root

6、i均称为整棵树根结点root的后继结点；而每棵子树也是一棵树，因而它们中数据元素间的关系也同样满足R的定义。树的基本操作如下：（1）Inittree(T)（2）Cleartree(T)（3）Emptytree(T)（4）Root(T)（5）Child(T,a,i)（6）Parent(T,a)（7）Degree(T,a)（8）Depth(T)（9）Choose(T,C)（10）Addchild（T,a,i,t1）（11）Delchild(T,a,i)（12）Createtree(a,F)（13）Equaltree(T1,T2)（14）Numofnode(

7、T)（15）preorder(T)（16）postorder(T)（17）levelorder(T)（18）Destroytree(T)}ADTTree6.3树的存储结构根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。6.3.1双亲表示法在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，可以包含两个信息：结点的值data和体现结点之间相互关系的属性__该结点的双亲parent。借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为双亲表示

8、法。#defineMAXSIZE100typedef