【数据结构】二叉树

二叉树

二叉树是一种树形结构，一个节点最多有两个子节点，没有子节点的节点为叶节点，我们设二叉树的节点数为n。

基本概念

边

节点和子节点的连线为边，这个概念是所有树形结构的概念。除了根节点，每个节点和其父节点都有一条连线，所以树的边的个数为n-1。

高度

节点到其叶节点的最长简单路径中边的个数是节点的高度，树的高度为根节点的高度。

简单路径：除了起点和终点的节点外，路径中所有的节点都不重复。起点和终点重复的节点称为回路(或环)。

深度

深度和高度相反，是节点到根节点的简单路径中边的个数。

二叉树第一层的深度为0，第二层为1，依次递增。二叉树每层的层数和深度相同。

索引

这里我们将根节点的索引定为1，从上往下，从左往右，依次递增，最后一个节点的索引为n。在大多数编程语言中，数组索引的开始为0，这里要注意下。

特性

设二叉树中有0个子节点的节点的个数为n₀，有1个子节点的节点的个数为n₁，有两个子节点的节点的个数为n₂，则：
$$n_0=n_2+1$$
证明：
$$\begin{gathered} n=n_0+n_1+n_2 \\ 二叉树的边数为n-1,同时n_2的节点有2条边，n_1的节点有1条边，所以 \\ n-1=2\ast n_2+n_1 \\ 2\ast n_2+n_1+1=n_0+n_1+n_2 \\ {n}_2+1=n_0 \end{gathered}$$
还有其他特性放在下面的满二叉树和完全二叉树。

满二叉树

除了最后一层外，其他每层的所有节点都有两个子节点。

设满二叉树的高度为h，层数为$i(i=0,1,2,...,h)$，则

1. 节点的总数为 $2^{h+1}-1$；

2. 第i层的节点数为 $2^i$​；

3. 第i层第一个节点的索引为 $2^i$​​；

由1，2可知：
$$\begin{gathered} 2^{h+1}-1=2^0+2^1+2^2+...+2^h \\ {2}^{h+1}=2^0+2^1+2^2+...+2^h+1 \end{gathered}$$

完全二叉树

除了最后一层外，每层都是满的，即每层的节点数为$2^i$，且最后一层的节点都集中在左侧。若高度为h的完全二叉树的节点数为n，则它和同样高度为h的满二叉树的前n个节点可以一一对应。满二叉树是一种特殊的完全二叉树。

节点数和层数

若完全二叉树的高度为h，当最后一层有1个节点或 $2^h$​ 个节点时，是完全二叉树的最小和最大值。

根据i层的第一个节点的索引为 $2^i$ 可知：
$$\begin{gathered} 2^h\le n\le 2^{h+1}-1 \\ {2}^h\le n<2^{h+1} \\ h\le \lg n<h+1 \\ h=\lfloor \lg n\rfloor \\ 或者2^h+1\le n+1\le 2^{h+1} \\ {2}^h<n+1\le 2^{h+1} \\ h<\lg (n+1)\le h+1 \\ h=\lceil lg(n+1)\rceil -1 \end{gathered}$$
节点数和层数的关系为$h=\lfloor \lg n\rfloor$或$h=\lceil lg(n+1)\rceil -1$

叶节点的开始索引

可以容易看出，在完全二叉树中，只有一个子节点的节点只有0个或1个，即$0\le n_1\le 1$。将所有节点从上到下，从左到右的排序，顺序为两个子节点的节点，1个子节点的节点，0个子节点的节点，所以叶节点的开始索引为$i=n_2+n_1+1=n-n_0+1$。
$$\begin{gathered} n=n_0+n_1+n_2 \\ {n}_0=n_2+1 \\ 0\le n_1\le 1 \\ 可得n_0=\lceil \frac{n}{2}\rceil \\ i=n-n_0+1=n-\lceil \frac{n}{2}\rceil +1 \\ i=\lfloor \frac{n}{2}\rfloor +1 \end{gathered}$$
所以叶节点开始的索引为$\lfloor \frac{n}{2}\rfloor +1$或者$\lceil \frac{n+1}{2}\rceil$