计算\(m\)叉树的最小高度
层数
结点数
第一层
\(1\)
第二层
\(m^1\)
第三层
\(m^2\)
\(\vdots\)
\(\vdots\)
第\(h\)层
\(m^{h-1}\)
故要求得最小高度每层都应为满结点的\(m\)叉树。设结点数为\(n\)，则\(n\le 1+m^1+m^2+\cdots+m^{h-1}\)。利用数列前\(n\)项和公式：
\[\begin{equation*}
\begin{aligned}
&等差数列前n项和:S_n=\frac{n(a_1+a_n)}{2}=na_1+\frac{n(n+1)}{2}d\\
\\
&等比数列前n项和:S_n=\frac{a_1(1-q)^n}{1-q}
\end{aligned}
\end{equation*}
\]
\(n\le\frac{1·(1-m^{h-1})}{1-m}\Longrightarrow nm-n+1\le m^{h-1}\)两边取对数得：
\[h=\lceil\log_m(n(m-1)+1)\rceil
\]
树易混淆概念
注意区分以下概念：
树的高度：是从下往上数
树的深度：从上往下数
树的度：各结点的度的最大值
如上面树的度\(=3\)，是结点D
度的计算
树中结点数等于所有结点的度数之和加上\(1\)(根节点)
度为\(m\)的树中第\(i\)层至多有\(m^{i-1}\)个结点，即满\(m\)叉树的情况。
\(\Large 例1:\)已知一棵树度为\(4\)的树中，度为\(0,1,2,3\)的结点数分别为\(14,4,3,2\)，求该树的结点总数\(n\)和度为\(4\)的结点个数，并给出推导过程。
\[\begin{equation*}
\begin{aligned}
\\\Large{解:}\\
&设n_i表示度为i的结点,则总结点数n:\\
\\
&①n=n_0+n_1+n_2+n_3+n_4=23+n_4\\
\\
&且树种结点数等于所有结点度数之和+1\\
\\
&②n=n_0·0+n_1·1+n_2·2+n_3·3+n_4·4\\
\\
&=0·14+1·4+2·3+3·2+4·n_4+1\\
\\
&=17+4n_4\\
\\
&故17+4n_4=23+n_4,得n_4=2,n=25\\
\\
&\therefore 该树总结点数为25,n_4为2
\end{aligned}
\end{equation*}
\]
\(\Large 例2:\)已知一棵度为\(m\)的树中，有\(n_1\)个度为\(1\)的结点，有\(n_2\)个度为\(2\)的结点\(\cdots\)有\(n_m\)个度为\(m\)的结点，问该树有多少个叶结点。
\[\begin{equation*}
\begin{aligned}
\\\Large{解:}\\
&树中结点数等于所有结点的度数之和加上1:\\
\\
&即n=n_1+2n_2+\cdots+mn_m+1=\sum_{i=1}^{m}in_i+1\\
\\
&且总结点数n=n_0+n_1+\cdots+n_m,即\\
\\
&n_0=\sum_{i=1}^{m}in_i-(n_1+n_2+\cdots+n_m)+1\\
\\
&=\sum_{i=1}^{m}in_i-\sum_{i=1}^{m}n_i+1=1+\sum_{i=1}^{m}n_i(i-1)
\end{aligned}
\end{equation*}
\]