第7章树形结构资料.ppt

第7章 树和二叉树;7.1.1 树的定义 形式化定义： 树：T={D,R}。D是包含n个节点的有穷集合（n≥0）。当n=0时为空树，否则关系R满足以下条件: ;递归定义： 树是由n（n≥0）个节点组成的有限集合（记为T）。其中： ;7.1.2 树的表示; （2）文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。; （3）凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。;　（4）括号表示法。将树的根节点写在括号的左边，除根节点之外的其余节点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。;思考题： 　　树的逻辑结构定义？适合表示什么类型的数据？;7.1.3 树的基本术语 1. 节点的度与树的度：树中某个节点的子树的个数称为该节点的度。树中各节点的度的最大值称为树的度，通常将度为m的树称为m次树?? ; 3. 路径与路径长度：对于任意两个节点di和dj，若树中存在一个节点序列di,di1,di2,…,din,dj，使得序列中除di外的任一节点都是其在序列中的前一个节点的后继，则称该节点序列为由di到dj的一条路径，用路径所通过的节点序列(di,di1,di2,…,dj)表示这条路径。 路径长度等于路径所通过的节点数目减1（即路径上分支数目）。; 4. 孩子节点、双亲节点和兄弟节点：在一棵树中，每个节点的后继，被称作该节点的孩子节点（或子女节点）。相应地，该节点被称作孩子节点的双亲节点（或父母节点）。 具有同一双亲的孩子节点互为兄弟节点。进一步推广这些关系，可以把每个节点的所有子树中的节点称为该节点的子孙节点。 　从树根节点到达该节点的路径上经过的所有节点被称作该节点的祖先节点。; 5. 节点的层次和树的高度：树中的每个节点都处在一定的层次上。节点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2层,以此类推,一个节点所在的层次为其双亲节点所在的层次加1。树中节点的最大层次称为树的高度（或树的深度）。 6. 有序树和无序树：若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。; 7. 森林：n（n＞0）个互不相交的树的集合称为森林。森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林。反之，只要给n棵独立的树加上一个节点，并把这n棵树作为该节点的子树，则森林就变成了树。;7.1.4 树的性质 　性质1 树中的节点数等于所有节点的度数加1。 证明：根据树的定义，在一棵树中，除树根节点外，每个节点有且仅有一个前驱节点。也就是说，每个节点与指向它的一个分支一一对应，所以除树根之外的节点数等于所有节点的分支数（度数），从而可得树中的节点数等于所有节点的度数加1。;　　求解树的节点个数问题：对于度为m的树，在n、n0、n1、n2、…、nm中只有两个参数未知时，一般可求出这两个值。例如求n和n0的求解过程如下： n=n0+n1+…+nm 度之和=n－1 度之和=n1+2n2+…+mnm 所以有：n＝n1+2n2+…+mnm+1=n0+n1+…+nm 这样：n0=n2+…+(m－1)nm+1; 例：一棵度为4的树T中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶子节点个数是 。 A.41 B.82 C.113 D.122; 性质2 度为m的树中第i层上至多有mi-1个节点，这里应有i≥1。; 性质3 高度为h的m次树至多有 个节点。 证明：由树的性质2可知,第i层上最多节点数为mi-1（i=1,2,…,h），显然当高度为h的m次树（即度为m的树）上每一层都达到最多节点数时，整个m次树具有最多节点数，因此有： 　整个树的最多节点数=每一层最多节点数之和=m0+m1+m2+…+mh-1 = 。; 性质4 具有n个节点的m次树的最小高度为?logm(n(m-1)+1)?。 证明：设具有n个节点的m次树的高度为h，若在该树中前h-1层都是满的，即每一层的节点数都等于mi-1个（1≤i≤h-1），第h层（即最后一层）的节点数可能满，也可能不满，则该树具有最小的高度。其高度h可计算如下：;根据树的性质3可得： ＜n≤ 乘(m-1)后得： mh-1＜n(m-1)+1≤mh 以m为底取对数后得：h-1＜logm(n(m-1)+1)≤h