树

树（Tree）

许多逻辑关系并不是简单的线性关系，在实际场景中，常常存在着一对多，甚至多对多的情况。树和图就是典型的非线性数据结构。

这些结构都像自然界中的树一样，从同一个根衍生出许多枝干，再从每一个枝干衍生出许多更小的枝干，最后衍生出更多的叶子。

树是由$n\ (n \ge 0)$个有限节点组成的一个具有层次关系的集合，当$n = 0$时称为空树。

在任意一个非空树中，有以下特点：

• 有且仅有一个特定的结点称为根（root）。

• 当$n > 1$时，其余结点可分为$m\ (m > 0)$个互不相交的有限集$T_1, T_2, \dots, T_m$，其中每一个集合本身又是一棵树，并且称为根的子树（subtree）。

• 根：没有父结点（parent）的结点。

• 内部结点（internal node）：至少有一个子结点（child）的结点。

• 外部结点（external node） / 叶子结点（leaf node）：没有子结点的结点。

• 度（degree）：结点分支的个数。

• 路径（path）：从根结点到树中某结点经过的分支构成了路径。

• 祖先结点（ancestors）：包含父结点、父结点的父结点等。

• 子孙结点（descendants）：包含子结点、子结点的子结点等。

• 深度（depth）：从根结点到该结点经过的边数，根结点深度为0。树的高度（height）：最大层级数，本章按结点层数计，空树高度为0。

二叉树（Binary Tree）

二叉树是树的一种特殊形式。二叉树的每个结点最多有两个孩子结点，即最多有2个，也可能只有1个，或者没有孩子结点。

二叉树结点的两个孩子结点，分别被称为左孩子（left child）和右孩子（right child）。这两个孩子结点的顺序是固定的，不能颠倒或混淆。

二叉树还有几种特殊的形式：

左斜树（left skew tree） / 右斜树（right skew tree）

只有左子树或只有右子树的二叉树。

满二叉树（perfect binary tree）

所有非叶子结点都存在左右孩子，并且所有叶子结点都在同一层。

完全二叉树

对于一个有n个结点的二叉树，按层级顺序编号，则所有结点的编号从1到n，完全二叉树所有结点和同样深度的满二叉树的编号从1到n的结点位置相同。简单来说，就是除最后一层外，其它各层的结点数都达到最大，并且最后一层从右向左连续缺少若干个结点。

二叉树的存储结构

二叉树既可以通过链式存储，也可以使用数组存储：

链式存储结构

一个结点最多可以指向左右两个孩子结点，所以二叉树的每一个结点包含三个部分：

• 存储数据的数据域data

• 指向左孩子的指针left

• 指向右孩子的指针right

数组存储

按照层级顺序把二叉树的结点放到数组中对应的位置上。如果某一结点的左孩子或右孩子空缺，则数组的相应位置也空出来。

采用数组存储可以更方便地定位二叉树的孩子结点和父结点。假设一个父结点的下标是parent，那么它的左孩子结点的下标就是2 * parent + 1，右孩子结点的下标就是2 * parent + 2。反过来，假设一个左孩子结点的下标是leftChild，那么它的父结点的下标就是floor((leftChild - 1) / 2)。

但是，对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。对于一种特殊的完全二叉树——二叉堆而言，就是使用数组进行存储的。