树与二叉树的基本概念 ¶

树结构总结 | Qida's Blog

树 ¶

树的定义 ¶

树（tree）是一种非线性数据结构，由 $n$ 个节点组成的有限集合。每个节点有零个或多个子节点；没有父节点的节点称为根节点；每个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。

任意一棵非空树应满足以下条件:

有且仅有一个特定的称为根的节点
其余节点可分为 $m (m > 0)$ 个不相交的子集 $T_1, T_2, \ldots, T_m$，其中每一个集合本身又是一棵树，称为根的子树

显然，树的定义是递归的，树的递归定义刻画了树的自相似性，即树的结构与子树的结构相同。

树作为一种分层结构，具有以下两个特点:

根节点没有前驱，除根节点外的所有节点有且只有一个前驱
树中所有节点都可以有零个或多个后继

树的常用术语 ¶

森林 ¶

由若干棵互不相交的树组成的集合称为森林。

事实上，由于树的自相似性，森林与树也可以相互转换：把树的根节点删去就成了森林，反之，把各个树的根节点连接起来，森林就变成了一棵树。

树的性质 ¶

树的节点数 $n$ 等于所有节点的度数之和加 $1$
度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}\ (i \geqslant 1)$ 个节点
高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^h - 1}{m - 1}$ 个节点
具有 $n$ 个节点、度为 $m$ 的树的最小高度为 $\lceil \log_m (n(m-1) + 1) \rceil$
度为 $m$、具有 $n$ 个节点的树的最大高度 $h$ 为 $n - m + 1$

树结点与度之间的关系

总结点数 $= n_0 + n_1 + n_2 + \cdots + n_m$
总分支数 $= n_1 + 2n_2 + 3n_3 + \cdots + mn_m$（度为 $m$ 的结点引出 $m$ 条分支）
总结点数 $= $ 总分支数 $+ 1$
设一棵 $m$ 叉树中有 $n_1$ 个度为 $1$ 的结点，$n_2$ 个度为 $2$ 的结点，$\cdots$，$n_m$ 个度为 $m$ 的结点，则该树的叶节点数为:

\[ n_0 = n_2 + 2n_3 + \cdots + (m - 1)n_m + 1 = \sum_{i = 2}^{m} (i - 1)n_i + 1 \]

可通过关系 $n = n_0 + n_1 + n_2 + \cdots + n_m = n_1 + 2n_2 + 3n_3 + \cdots + mn_m + 1$ 推导。

二叉树 ¶

顾名思义，二叉树是一种每个节点最多有两个子节点的树。

二叉树与度与 $2$ 的树

度为 $2$ 的树至少有 $3$ 个节点，而二叉树可以为空树
度为 $2$ 的有序树子节点次序是相对另一个子节点而言的（即在只有一个节点时不分左右），而二叉树无论其是否具有两个子节点，均需要确定左右次序

几种特殊的二叉树 ¶

满二叉树 ¶

一棵高度为 $h$ 且有 $2^h - 1$ 个节点的二叉树称为满二叉树。

满二叉树的每层都含有最多的节点数；所有的叶节点都集中在二叉树的最下一层，并且所有的非叶节点都有两个子节点。

完全二叉树 ¶

二叉排序树 ¶

深入理解之排序二叉树 | Anran758's blog

二叉排序树

平衡二叉树 ¶

平衡二叉树

树中任意结点的左、右子树高度差的绝对值不超过 $1$。

正则二叉树 ¶

树中每个分支节点都有 $2$ 个子节点，即树中只有度为 $0$ 或 $2$ 的节点。

二叉树的性质 ¶

非空二叉树的叶结点数等于度为 $2$ 的结点数加 $1$，即 $n_0 = n_2 + 1$
非空二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点（$i \geqslant 1$）
高度为 $h$ 的二叉树至多有 $2^h - 1$ 个结点（$h \geqslant 1$）
具有 $n$ 个（$n > 0$）结点的完全二叉树的高度 $h$ 为 $\lceil \log_2 (n + 1) \rceil$ 或 $\lfloor \log_2 n \rfloor + 1$
对于完全二叉树，如果从上至下、从左至右编号 $1, 2, \cdots, n$，则有以下关系:
1. 最后分支结点的编号为 $\lfloor n/2 \rfloor$，若 $i \leqslant \lfloor n/2 \rfloor$，则结点 $i$ 为分支结点，否则为叶结点
2. 叶结点只可能在最后两层上出现（相当于在相同高度的满二叉树的最底层、最右边减少一些连续叶结点，当减少 $2$ 个或以上叶结点时，次底层将出现叶结点）
3. 若有度为 $1$ 的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子（度为 $1$ 的分支结点只可能是最后一个分支结点，其结点编号为 $\lfloor n/2 \rfloor$）
4. 按层序编号后，一旦出现某结点（编号为 $i$）为叶结点或只有左孩子，则编号大于 $i$ 的结点均为叶结点（结论 1 和结论 3 是相通的）
5. 若 $n$ 为奇数，则每个分支结点都有左孩子和右孩子；若 $n$ 为偶数，则编号最大的分支结点（编号为 $n/2$）只有左孩子，没有右孩子，其余分支结点都有左孩子和右孩子
6. 当 $i > 1$ 时，结点 $i$ 的双亲的编号为 $\lfloor i/2 \rfloor$。即当 $i$ 为偶数时，其双亲的编号为 $i/2$，即 $i$ 的双亲为 $i/2$；当 $i$ 为奇数时，其双亲的编号为 $(i - 1)/2$，即 $i$ 的双亲为 $(i - 1)/2$
7. 若结点 $i$ 有左孩子，则左孩子的编号为 $2i$；若结点 $i$ 有右孩子，则右孩子的编号为 $2i + 1$
8. 结点 $i$ 所在的层次（深度）为 $\lfloor \log_2 i \rfloor + 1$

二叉树的存储结构 ¶

顺序存储结构 ¶

顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。

对于完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素。即将完全二叉树上编号为 i 的结点元素存储在一维数组中下标为 i-1 的分量中。

对于一般的二叉树，可以按完全二叉树的形式进行编号，不过在最下一层要加“虚”结点，将其补齐，如图所示:

不难看出，顺序存储结构仅适用于完全二叉树，在一般二叉树上采用顺序存储结构，会造成存储空间的浪费。

链式存储结构 ¶

树结构总结-链式存储结构 | Qida's Blog