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

前言

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

正文

性质一

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

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

性质二

深度为 $k$ 的二叉树【至多】有 $2^k–1$ 个结点，其中，$k⩾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⩽n$, 则结点 $i$ 的左孩子结点序号为 $2i$. 否则，若 $2i>n$, 则结点 $i$ 没有左孩子。

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

图示

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

EOF