ds课件葆第7章树形结构.pptx

第7章 树形结构;7.1 树的基本概念 ;7.1.1 树的定义 树的形式化定义：T＝{K,R}。 K是包含n个结点的有穷集合(n0),关系R满足以下条件: （1）有且仅有一个结点k0∈K,它对于关系R来说没有前驱结点,结点k0称作树的根。 （2）除结点k0外,K中的每个结点对于关系R来说都有且仅有一个前驱结点。 （3）K中每个结点对于关系R来说可以有多个后继结点。;递归定义： 树是由n（n≥0）个结点组成的有限集合（记为T）。其中， 如果n=0，它是一棵空树，这是树的特例； 如果n0，这n个结点中存在（且仅存在）一个结点作为树的根结点，简称为根（root），其余结点可分为m （m0）个互不相交的有限集T1，T2，…，Tm，其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。;7.1.2 树的表示;（2）文氏图表示法。 使用集合以及集合的包含关系描述树结构。;（3）凹入表示法。 使用线段的伸缩描述树结构。; （4）括号表示法。;7.1.3 树的基本术语 1. 结点的度与树的度： 树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树或m叉树。 2. 分支结点与叶结点： 度不为零的结点称为非终端结点，又叫分支结点。 度为零的结点称为终端结点或叶结点。在分支结点中，每个结点的分支数就是该结点的度。; 3. 路径与路径长度： 对于任意两个结点ki和kj，若树中存在一个结点序列ki，ki1，ki2，…，kin，kj，使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继，则称该结点序列为由ki到kj的一条路径，用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。 路径的长度等于路径所通过的结点数目减1（即路径上分支数目）。; 4. 孩子结点、双亲结点和兄弟结点： 在一棵树中，每个结点的后继，被称作该结点的孩子结点（或子女结点）。相应地，该结点被称作孩子结点的双亲结点（或父母结点）。 具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系，可以把每个结点的所有子树中的结点称为该结点的子孙结点，从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。; 5. 结点的层次和树的高度： 结点的层次从树根开始定义，根结点为第一层，它的孩子结点为第二层，以此类推，一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度（或树的深度）。 6. 有序树和无序树： 若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。; 7. 森林： n（n＞0）个互不相交的树的集合称为森林。把树的根结点删去就成了森林。;7.1.4 树的性质 性质1 树中的结点数等于所有结点的度数加1。 证明：根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点。也就是说，每个结点与指向它的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数（度数），从而可得树中的结点数等于所有结点的度数加1。; 性质2 度为m的树中第i层上至多有mi-1个结点，这里应有i≥1。 证明（采用数学归纳法） 对于第一层，因为树中的第一层上只有一个结点，即整个树的根结点，而由i=1代入mi-1，得mi-1=m1-1=1，也同样得到只有一个结点，显然结论成立。 假设对于第(i-1)层（i＞1）命题成立，即度为m的树中第(i-1)层上至多有mi-2个结点，则根据树的度的定义，度为m的树中每个结点至多有m个孩子结点，所以第i层上的结点数至多为第(i-1)层上结点数的m倍，即至多为mi-2×m=mi-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)?。 证明