# 完全二叉树的题型
## 已知深度，求一些属性
- 最后一层节点数上限为：$2^{k-1}$（即满二叉树）
- 总节点数上限为：$2^k-1$（即满二叉树）
## 已知结点数，求深度(高度)
- 将结点数用二进制表示出来，位数就是高度。
- 也可以数学计算：$\lfloor\log_2n\rfloor+1$
## 已知结点数，求叶子结点数
1. 求出深度，以及最后一层的节点数$n$和空位数$m$
1. 叶子结点数 = $n+\lfloor m/2 \rfloor$
## 已知结点数，求空指针数
1. 求出深度，以及最后一层的节点数$n$和空位数$m$
2. 空指针数 = $
\begin{cases}
2\times 叶子结点数+1&,n和m为奇数\\
2\times 叶子结点数&, n和m为偶数
\end{cases}
$
## \*已知叶子节点数，求可能深度
> 懒人直接看结论
### 推导
其实就是构造方程和不等式。
已知叶子节点数为$n$，设深度为$k$，最后一层的空位数为$x$，有如下等式：
$$
n=2^{k-1}-x+\lfloor \dfrac{x}2\rfloor \\
$$
分类讨论，整理得
$$
\begin{align}
&当x为奇数时：x=2^k-2n-1 \\
&当x为偶数时：x=2^k-2n
\end{align}
$$
又有不等式 $0\le x\lt 2^{k-1}$，当且仅当 $x$ 为偶数时有可能取$0$（树为满二叉树），得
$$
\begin{align}
&&当x为奇数时：&2^k\gt 2n+1 \gt 2^{k-1} \\
&&当x为偶数时：&2^k\ge 2n \gt 2^{k-1} \\
\end{align}
$$
不等式各边都大于0，所以可同时取以2为底的对数，得
$$
\begin{align}
&&当x为奇数时：&k\gt \log_2{(2n+1)} \gt k-1 \\
&&当x为偶数时：&k\ge \log_2{2n} \gt k-1 \\
\end{align}
$$
由此可得$k$的取值范围（这里还不是最简形式，不用记）：
$$
\begin{align}
&&当x为奇数时：&k=\lceil\log_2{(2n+1)}\rceil \\
&&当x为偶数时：&k=\lceil\log_2{2n}\rceil \\
\end{align}
$$
由于本题并未给出$x$的奇偶性，我们把两种情况都试一下就行了。如有1个叶子节点的完全二叉树可能为1层或2层，有2个叶子节点的可能为2层或3层（因x的奇偶而不同），有3个叶子节点的一定为3层（不论x奇偶，结果一致），有4个叶子节点的可能为3层或4层……以此类推。
特别地，我们可以归纳整理，并且把向上取整变成我们熟悉的向下取整，得到结论（这是最简形式！）
### 结论
**当叶子节点数$n$恰好为2的次方时，树深有两种可能情况 $\log_2{n}+1$ 和 $\log_2{n}+2$，分别是满二叉树和下面有一个；如果不为2的次方，则必然只有一种树深，即$\lfloor\log_2{n}\rfloor+2$。NICE！**
$$
\begin{cases}
k\in \{ \log_2{n}\ + 1,\ \log_2{n}\ +2 \} &, \log_2n \in \mathbb{Z} \\
k= \lfloor \log_2{n} \rfloor +2 &, \log_2n \notin \mathbb{Z}
\end{cases}
$$
---
另附一种快速推算方式：
比如求273个叶子节点的完全二叉树有几层，那我首先想一个满二叉树有256个叶子节点，然后再往下一层走叶子节点会慢慢变多，但是没有多到512个。也就是说这棵树的深度是比256个叶子节点的满二叉树的深度还高1，256个叶子节点的满二叉树根据$2^{k-1}$算出来$k$是9，那这个273个的树就是10了！当然根据上述公式 $\lfloor \log_2{273}\rfloor +2=10$ 结果是一样的。
![]()