树的性质

四个性质

性质一:非空树的结点数等于树中所有结点的度之和加1

性质二:度为k的非空树的第i层最多有$k^{i-1}$个结点(i>=1)

数学归纳法 大法好
当i = 1时,第一层只有一个结点,即树的根结点。$k^0 = 1$。
当i > 1时,假设命题成立,则第i-1层最多有$k^{i-2}$个结点。因为度为k的树,每个结点最多有k个孩子结点。则i层的最多的结点数是第i-1层的k倍,则第i层最多有$k*k^{i-2}$=$k^{i-1}$个结点。

性质三:深度为h的k叉树最多有$\frac{k^h -1}{k-1}$

只有当深度为h的k叉树的每一层都达到该层最大结点总数时,该树的结点总数才达到最大,因此
$$\sum_{i=1}^k k^{i-1}=k^0 + k^1 + k^2 + … + k^{h-1}=\frac{k^h-1}{k-1}$$

其实是一个等比数列,从1开始,等比为k的数列,则总和为$S_n = a_1 + a_2 + a_3 + … + a_n$

$$S_n=\frac{1 - k^{h-1}*k}{1-k} = \frac{k^h-1}{k-1}$$

一颗k叉树的结点总数为$\frac{k^h-1}{k-1}$时,称为该树为满k叉树

性质四:具有n个结点的k叉树的最小深度为$log_k(n(k-1)+1)$

详细证明如下
设具有n个结点的k叉树的深度为h,若该树的前h-1层都是满的,
即每一层的结点数都为$k^{i-1}$个$(1≤i≤h-1)$
第h层(最后一层)的结点数可能满,也可能不满,
n总结点数小于等于深度为h的满k叉树,则可得如下式子:
$$n ≤ \frac{k^h-1}{k-1}$$

又因为n肯定大于h-1层的满k叉树,即
$$\frac{k^{h-1}-1}{k-1} < n$$

合并得
$$\frac{k^{h-1}-1}{k-1} < n ≤ \frac{k^h-1}{k-1}$$
$${k^{h-1}-1} < n(k-1) ≤ {k^h-1}$$
$$k^{h-1} < n(k-1) + 1 ≤ k^h$$
取以k为底的对数
$$① h-1 < log_k(n(k-1) + 1) ≤ h$$
$$② h < log_k(n(k-1) + 1) + 1 ≤ h + 1$$
根据①,②得
$$log_k(n(k-1)+1) ≤ h < log_k(n(k-1) + 1) + 1$$
又因h是树的深度,只能是整数,所以
$$h = log_k(n(k-1)+1) $$

例题

例题1:一个深度为5的满2叉树的结点总数为多少?

例题2:一个深度为3的满6叉树的结点总数为多少?

例题3:对于二叉树,最小深度为$log_2(n(2-1) + 1),n=20$,最小深度为?

例题4:对于三叉树,最小深度为$log_3(n(3-1) + 1),n=20$,最小深度为?

xpisme wechat
微信号