树中结点，高度及度的计算

树中结点，高度及度的计算

计算(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)，是结点

度的计算

树中结点数等于所有结点的度数之和加上(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*} ]