6.14树的性质 性质1树中的结点数等于所有结点 的度数加1。 ③◎ 证明:根据树的定义,在一棵树中 除树根结点外,每个结点有且仅有 个前驱结点。也就是说,每个结点与 度之和=分支数 指向它的一个分支一一对应,所以除 分支数=n-1 树根之外的结点数等于所有结点的分 所以,n=度之和+1 支数(度数),从而可得树中的结点 数等于所有结点的度数加1
6.1.4 树的性质 性质1 树中的结点数等于所有结点 的度数加1。 证明：根据树的定义，在一棵树中， 除树根结点外，每个结点有且仅有一 个前驱结点。也就是说，每个结点与 指向它的一个分支一一对应，所以除 树根之外的结点数等于所有结点的分 支数（度数），从而可得树中的结点 数等于所有结点的度数加1。 度之和＝分支数 分支数=n-1 所以，n=度之和+1 A B C D E F G J H I K L M
性质2度为m的树中第上至多有m1个结点,这里应有 1 证明(采用数学归纳法) 对于第一层,因为树中的第一层上只有一个结点,即整个树 的根结点而由i1代入m1,得ntl=m1l=1,也同样得到只有 个结点,显然结论成立。 假设对于第(i1)层(i>1)命题成立,即度为m的树中第( 1)层上至多有m2个结点。 则根据树的度的定义,度为m的树中每个结点至多有m个孩 子结点,所以第层上的结点数至多为第(i1)层上结点数的m倍 即至多为m2xm=mt1个,这与命题相同,故命题成立
性质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个，这与命题相同，故命题成立
推广:当一棵m次树的第很有m个结点(论1)时,称 该层是满的,若一棵m次树的所有叶子结点在同一层,除该 层外其余每一层都是满的,称为满m次树。显然,满m次树 是所有相同高度的m次树中结点总数最多的树。 也可以说,对于n个结点,构造的m次树为满m次树或 者接近满m次树,此时树的高度最小
推广：当一棵m次树的第i层有mi-1个结点（i≥1）时，称 该层是满的，若一棵m次树的所有叶子结点在同一层，除该 层外其余每一层都是满的，称为满m次树。显然，满m次树 是所有相同高度的m次树中结点总数最多的树。 也可以说，对于n个结点，构造的m次树为满m次树或 者接近满m次树，此时树的高度最小
性质3高度为的m次树至多有m-个结点 m-1 证明:由树的性质2可知第i层上最多结点数为mr1 i=1,2,,h),显然当高度为h的m次树(即度为m的树)上 每一层都达到最多结点数时,整个m次树具有最多结点数,因 些有: 整个树的最多结点数=每一层最多结点数之和 n+ml1+m2+,,+mh-1=W3
性质3 高度为h的m次树至多有 个结点。 证明：由 树的 性质 2可 知, 第i 层上 最多 结点 数为 mi-1 （i=1,2,…,h），显然当高度为h的m次树（即度为m的树）上 每一层都达到最多结点数时，整个m次树具有最多结点数，因 此有： 整个树的最多结点数 = 每一层最多结点数之和 =m0+m1+m2+…+mh-1 = 。 1 1 − − m m h 1 1 − − m m h
性质4具有n个结点的m次树的最小高度为ogn(m(m )+1) 证明:设具有n个结点的m次树的高度为h,若在该树中前 h-层都是满的,即每一层的结点数都等于m个(1ih-1) 第h层(即最后一层)的结点数可能满,也可能不满,则该树 具有最小的高度。其高度h可计算如下: m=3,h=3,最多结点情况 m-3,h=3,最少结点情况
性质4 具有n个结点的m次树的最小高度为logm (n(m- 1)+1)。 证明：设具有n个结点的m次树的高度为h，若在该树中前 h-1层都是满的，即每一层的结点数都等于mi-1个（1≤i≤h-1）， 第h层（即最后一层）的结点数可能满，也可能不满，则该树 具有最小的高度。其高度h可计算如下： m=3，h=3，最多结点情况 m=3，h=3，最少结点情况