性质2度为m的树中第层上至多有mi-1个节点，这里应有1。证明（采用数学归纳法）对于第一层，因为树中的第一层上只有一个节点，即整个树的根节点，而由=1代入mi-1，得mi-1=ml-1=1，也同样得到只有一个节点，显然结论成立假设对于第(i-1)层（i>1）命题成立，即度为m的树中第(i-1)层上至多有mi-2个节点则根据树的度的定义，度为m的树中每个节点至多有m个孩子节点，所以第层上的节点数至多为第（i-1)层上节点数的m倍，即至多为mi-2×mFmi-1个，这与命题相同，故命题成立。16
16 性质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个，这与命题相同，故命题成立
性质3m21个节点。高度为h的m次树至多有m证明：由树的性质2可知，第i层上最多节点数为mi-1（=1,2,..,h），显然当高度为h的m次树（即度为m的树）上每一层都达到最多节点数时，整个m次树具有最多节点数，因此有:整个树的最多节点数=每一层最多节点数之和=ml+ml+m2+...+ml-1 = mm-117
17 性质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次树的最小高度为[logm（nm-1)+1)l证明：设具有n个节点的m次树的高度为h，若在该树中前h-1层都是满的，即每一层的节点数都等于mi-1个（1≤h-1），第h层（即最后一层）的节点数可能满，也可能不满，则该树具有最小的高度。其高度h可计算如下：m=3，h=3，最多节点情况m-3，h=3，最少节点情况18
18 性质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，最少节点情况
m.m根据树的性质3可得<m-1m-1mlt-1 < n(m-1)+1<mh乘(m-1)后得：以m为底取对数后得：h-1<logm(n(m-1)+1)≤h即logm(n(m-1)+1)≤h < logm(n(m-1)+1)+1因h只能取整数，所以h= 1ogm(n(m-1)+1) 结论得证。19
19 根据树的性质3可得： ＜n≤ 乘(m-1)后得： mh-1＜n(m-1)+1≤mh 以m为底取对数后得：h-1＜logm (n(m-1)+1)≤h 即 logm (n(m-1)+1)≤h＜logm (n(m-1)+1)+1 因h只能取整数，所以 h=logm (n(m-1)+1) 结论得证。 1 1 1 − − − m m h 1 1 − − m m h
例7.1含n个节点的三次树的最小高度是多少？最大高度是多少？解：设含n个节点的（为完全三次树时高度最小）的三次树的最小高度为h，则有：1+3+9+...+3h-2 < n≤1+3+9+...+3h-1(3h-1-1)/2 < n≤ (3h-1)/23h-1 < 2n+1≤3h即 : h=[ log3(2n+1)最大高度为n-2。20
20 例7.1 含n个节点的三次树的最小高度是多少？最大高 度是多少？ 解：设含n个节点的（为完全三次树时高度最小）的 三次树的最小高度为h，则有： 1+3+9+.+3 h-2＜n≤1+3+9+.+3 h-1 (3 h-1 -1)/2 ＜n≤ (3 h -1)/2 3 h-1＜2n+1≤3 h 即：h= log3 (2n+1) 最大高度为n-2。