github中有详尽代码可作参考

返回目录

树的性质

• 树中的结点数等于所有节点的度数之和加 $1$;
• 在 $n$个结点的树中有 $n-1$条边(度);
• 树的度(指各结点的度的最大值);
• $m$叉树(指每个结点最多只能有 $m$个孩子的树);

度为 $m$的树和 $m$叉树比较

• 度为 $m$的树(或 $m$叉树)第 $i$层至多有 $m^{i-1}$个结点( $i \geq 1$),此时整棵树是一个完全 $m$叉树;
• 高度为 $h$的 $m$叉树(或度为 $m$的树)至多有 $\frac{m^h-1}{m-1}$个结点;
• 高度为 $h$的 $m$叉树至少有 $h$个结点,高度为 $h$的 度为 $m$的树至少有 $h+m-1$个结点;

证明: 在完全 $m$叉树中,第一层有 $m^0=1$,第二层 $m^1$,第三层 $m^2$, $\cdots$,第 $h$层 $m^{h-1}$,总共 $1+m^1+m^2+\cdots+m^{h-1}=\frac{1(1-m^h)}{1-m}=\frac{m^h-1}{m-1}$.

由于 $m$叉树中,每一个高度至少为 $1$,故 至少有 $h$个结点;

而在度为 $m$的树中,至少有一个结点有 $m$个分支,且满足每层的结点尽可能少,即 $h-1 + m$,如下图所示.

• 具有 $n$个结点的 $m$叉树(或度为 $m$的树)的最小高度为 $\left \lceil \log _ m (n\times (m-1)+1)\right \rceil$;

证明: 所有结点都有 $m$个孩子,可由上一个性质知:

其中前 $h-1$层最多有多少个结点表示为 $\frac{m^{h-1}-1}{m-1}$,前 $h$层最多有多少和结点表示为 $\frac{m^h-1}{m-1}$.

故 $\frac{m^{h-1}-1}{m-1} < n \leq \frac{m^h-1}{m-1}$.

两边同时乘以 $m-1$,并 $+1$,得: $m^{h-1} < n\times (m-1)+1 \leq m^h$

两边同取 $\log _m$,得: $h-1 < \log _m (n\times (m-1)+1) \leq h$

故 $h_{min}=\left \lceil \log _m (n\times (m-1)+1) \right \rceil$

• 设树中度为 $i$( $i=0,1,2,\cdots,m$)的结点数为 $a_i$,总结点个数 $n$为 $\color{Red}{\displaystyle \sum_{i=0}^{m} a_i}$（表示结点个数之和),亦可表示为 $\color{Red}{\displaystyle (\sum_{i=0}^{m} i\times a_i)+1}$(表示所有结点的度数之和 $+1$)

对于一棵具有 $n$个结点、度为 $4$的树来说，( $\color{Red}{A}$)

A.树的高度至多是 $n-3$

B.树的高度至多是 $n-4$

C.第i层上至多有 $4(i-1)$个结点

D.至少在某一层上正好有 $4$个结点

树的度为 $4$说明至少有一个结点的度为 $4$,故 $D$错误,要想树的高度最高，需使树的每一层的结点尽可能少。将每一层只放一个结点的树高度为 $n$，而此时将最后三个结点放到了倒数第四个结点那一层，所以高度减少了 $3$，故树的高度至多为 $n-3$,故 $A$正确, $B$错误,度为 $4$的第 $i$层至多有 $4^{i-1}$个结点, $C$错误.

度为 $4$、高度为 $h$的树，( $\color{Red}{A}$),

A.至少有 $h+3$个结点

B.至多有 $4h-1$个结点

C.至多有 $4h$个结点

D.至少有 $h+4$个结点

套结论

• 高度为 $h$的 $m$叉树(或度为 $m$的树)至多有 $\frac{m^h-1}{m-1}$个结点;
• 高度为 $h$的 $m$叉树至少有 $h$个结点,高度为 $h$的 度为 $m$的树至少有 $h+m-1$个结点;

故度为 $4$,高度为 $h$的树中,至少有 $h+4-1=h+3$个结点,至多有 $\frac{4^h-1}{3}$.

假定一棵度为 $3$的树中，结点数为 $50$，则其最小高度为（).

A. $3$

B. $4$

C. $\color{Red}{5}$

D. $6$

方法一:套结论

• 具有 $n$个结点的 $m$叉树(或度为 $m$的树)的最小高度为 $\left \lceil \log _ m (n\times (m-1)+1)\right \rceil$;

由上知, $\left \lceil \log _3 (50\times 2+1) \right \rceil=\left \lceil \log _3 101 \right \rceil=5$

方法二:计算每层的个数,求和与结点数比较

2010统考真题：在一棵度为 $4$的树 $T$中，若有 $20$个度为 $4$的结点， $10$个度为 $3$的结点， $1$个度为 $2$的结点， $10$个度为 $1$的结点，则树 $T$的叶结点个数是()。

A. $41$

B. $\color{Red}{82}$

C. $113$

D. $122$

套结论

• 树中的结点数等于所有节点的度数之和加 $1$;

设度为 $0$的结点(叶子结点)有 $x$个,由题知:总结点数可表示为: $x\times 0+10\times 1+ 1\times 2+10\times 3+20\times 4+1$(度数之和加 $1$);总结点数亦可表示为 $x+10+1+10+20$(结点个数和)

两式联立解得: $x=82$

5.1.1

含有 $n$个结点的三叉树的最小高度是多少?

套结论

• 具有 $n$个结点的 $m$叉树(或度为 $m$的树)的最小高度为 $\left \lceil \log _ m (n\times (m-1)+1)\right \rceil$;

由上知, $\left \lceil \log _3 (n\times 2+1) \right \rceil$

5.1.2

已知一棵度为 $4$的树中，度为 $0,1,2,3$的结点数分别为 $14,4,3,2$,求该树的结点总数 $n$和度为 $4$的结点个数，并给出推导过程。

设树中度为 $i$( $i=0,1,2,\cdots,m$)的结点数为 $a_i$,总结点个数 $n$为 $\color{Red}{\displaystyle \sum_{i=0}^{m} a_i}$（表示结点个数之和),亦可表示为 $\color{Red}{\displaystyle (\sum_{i=0}^{m} i\times a_i)+1}$(表示所有结点的度数之和 $+1$)

设度为 $4$的结点个数是 $a_4$,由题知, $n=14+4+3+2+a_4=1\times 4+2\times 3 + 3\times 2+4\times a_4+1$

解得: $a_4=2$, $n=25$

5.1.3

已知一棵度为 $m$的树中，有 $n_1$个度为 $1$的结点，有 $n_2$个度为 $2$的结点 $\cdots\cdots$有 $n_m$个度为 $m$的结点，问该树有多少个叶子结点?

设度为 $0$的结点(叶子结点)有 $n_0$个,设总结点个数为 $n$,

$n=\displaystyle \sum_{i=0}^{m} n_i=n_0+n_1+n_2+\cdots +n_m$

$n=\displaystyle (\sum_{i=0}^{m} i\times n_i )+1=n_0\times 0+n_1\times 1+n_2\times 2+\cdots +n_m\times m +1$

故 $n_0=n_1+2n_2+\cdots+mn_m +1-(n_1+n_2+\cdots+n_m)$

$=n_2+2n_3+3n_4+\cdots+(m-1)n_m+1$

$\displaystyle =[\sum_{i=2}^{m} n_i\times (i-1)] +1$