[数据结构基础]二叉树的重要性质

前言

本文将总结和二叉树有关的一些重要性质,以作参考。

正文

性质一

在二叉树的第 $i$ 层上【至多】有 $2^{i-1}$ 个结点,其中,$i \geqslant 1$.

Tips:
【至多】就是在该二叉树为【满二叉树】的情况下。

性质二

深度为 $k$ 的二叉树【至多】有 $2^{k} – 1$ 个结点,其中,$k \geqslant 1$.

Tips:
【至多】就是在该二叉树为【满二叉树】的情况下。

性质三

对任意一棵二叉树,若终端结点(叶子结点)的个数为 $n_{0}$ (叶子结点的度为 $0$, 估下标记为 $0$), 度为 $2$ 的结点个数为 $n_{2}$, 则:

$$
n_{0} = n_{2} + 1.
$$

性质四

具有 $n$ 个结点的【完全二叉树】的深度 $k$ 为 $\lfloor \log_{2}^{n} \rfloor + 1$.

性质五

对于具有 $n$ 个结点的【完全二叉树】,如果按照对【满二叉树】的结点进行连续编号的方式对【完全二叉树】的结点从 $1$ 开始按照从左到右,从上到下的顺序编号,则对于任意序号为 $i$ 的【完全二叉树】结点,有如下性质:

(1) 如果 $i = 1$, 则结点 $i$ 为根节点,根节点无双亲结点;如果 $i > 1$, 则结点 $i$ 的双亲结点序号为 $\lfloor \frac{i}{2} \rfloor$.

(2) 如果 $2i \leqslant n$, 则结点 $i$ 的左孩子结点序号为 $2i$. 否则,若 $2i > n$, 则结点 $i$ 没有左孩子。

(3) 如果 $2i + 1 \leqslant n$, 则结点 $i$ 的右孩子结点序号为 $2i + 1$. 否则,若 $2i + 1 > n$, 则结点 $i$ 没有右孩子。

图示

以上性质都可以通过以下特例辅助记忆:

图 1.