数据结构--第7章 树形结构1.ppt

第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次树。 2. 分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。在分支结点中,每个结点的分支数就是该结点的度。如对于度为1的结点,其分支数为1,被称为单分支结点；对于度为2的结点,其分支数为2,被称为双分支结点,其余类推。; 3. 路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。可见,路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。; 4. ???子结点、双亲结点和兄弟结点：在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。; 5. 结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度(或树的深度)。 6. 有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树。; 7. 森林：n(n＞0)个互不相交的树的集合称为森林。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给n棵独立的树加上一个结点,并把这n棵树作为该结点的子树,则森林就变成了树。;7.1.4 树的性质 性质1 树中的结点数等于所有结点的度数加1。 证明：根据树的定义,在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点。也就是说,每个结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数(度数),从而可得树中的结点数等于所有结点的度数加1。; 性质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个