数据结构与算法 —— 树、堆

树的定义及基本术语

树（Tree）：n（n >= 0）个结点构成的有限集合。当 n = 0 时，称为空树；对于任意一颗非空树（n > 0），它具备以下性质：

树中有一个称为根（Root）的特殊结点，用 r 表示。

其余结点可以分为 m（m > 0）个互不相交的有限集 T1, T2, … , Tm，其中每个集合本身又是一棵树，称为原来树的子树（subtree）。

树的定义使用了递归的思想。注意：根据定义，子树之间不能相交，一颗树中不能出现环。

下面是一颗树及其子树：

根据树的定义，可以得出一些结论：

除了根结点外，每个结点有且仅有一个父结点。（根结点没有父结点）
一颗 N 个结点的树有 N - 1 条边。（因为除了根结点外，每个结点都有且仅有一条边与其父结点相连）

树的一些基本术语：

结点的度（Degree）：一个结点的子树个数。
树的度：树中所有结点的度的最大值。
叶结点（Leaf）：度为 0 的结点（即没有子树的结点）。
路径与路径长度：从一个结点出发，到另一个结点经过的所有边构成一条路径，路径所包含的边的个数为路径的长度。
父结点（Parent）、子结点（Child）、兄弟结点（Sibling）、祖先结点（Ancestor）、子孙结点（Descendant）。
结点的层次（Level）：规定根结点在 1 层，其他任一结点的层数是其父结点的层数加 1。
树的深度（Depth）：树中所有结点中的最大层次就是这棵树的深度。

树的表示

数组实现

由于树中每个结点的子结点数目无法确定（可能是 0 个，也可能是 n 个），树的结构很难判别，所以用数组实现是不切实际的。

后面要说到的二叉树可以用数组实现。

链表实现

看到树的结构，理所当然地会想到用链表来实现一棵树，如下图：

结点用结构体或对象来表示，看起来似乎实现了，但有个问题是：无法确定某个结点有几个子结点，即需要在结构体中定义多少个指针。

针对这个问题，有一个解决方法：将每个结点都设计成一样的结构，比如全都设置成 A 结点那样的结构，也就是有三个指针，用不到的指针就让它指向空，比如 B 除了有两个指针指向它的子结点外，还有一个指针指向空。

但这样有一个前提：必须事先知道这棵树的度。且由于很多指针都指向空，会造成大量空间被浪费。

儿子-兄弟表示法

这种方法可以将一颗一般的树表示成一个结构上比较一致的树。

每个结点统一只有两个指针，一个指向它的第一个子结点，另一个指向它的兄弟结点。

下图是将一棵树用儿子-兄弟表示法表示的结果：

将表示结果顺时针旋转 45°：

可以发现这也是一棵树，每个结点最多只有两个子结点，这种树叫做二叉树。

不管多么复杂的树，都可以用儿子-兄弟表示法将其转换为一颗二叉树。所以研究二叉树是很重要的。

二叉树的定义、性质及存储

二叉树的定义

二叉树：一个有穷的结点集合。

这个集合可以为空。

若不为空，则它是由根结点和称为其左子树和右子树的两个不相交的二叉树组成。

二叉树与“度为 2 的树”的区别是：二叉树的子树有左右之分。

二叉树有五种基本形态：

几种特殊的二叉树

斜二叉树：

这种二叉树的每个结点要么都只有左孩子，要么都只有右孩子，也就是往一边到。其实就相当于一个链表。
满二叉树（也叫完美二叉树）：

如果一棵二叉树的任何结点，要么是树叶，要么左右子树都非空，那么这棵二叉树就叫做满二叉树。
完全二叉树：

如果一棵二叉树最多只有最下面的两层结点度数可以小于 2，并且最下面一层的结点都集中在该层最左边的连续位置上，则此二叉树称作完全二叉树。

完全二叉树是一种很重要的二叉树，很多数据结构和算法都建立在这种二叉树的基础上。

二叉树的几个重要性质

二叉树第 $i$ 层（根结点的层数为 1）的最大结点数为：$2^{i-1}, i \ge 1$
深度为 $k$ 的二叉树的最大结点总数为：$2^k-1, k \ge 1$

推导：第 1 层的结点数为 $2^{1-1}=1$，第二层为 $2^{2-1}=2$，以此类推，最后将所有结点数加起来，$1+2^1+2^2+ \dots +2^{k-1}$，这是一个等比数列求和，它的结果就是 $2^k-1$。
对任何非空二叉树，若 $n_0$ 表示叶结点的个数，$n_2$ 表示度为 2 的结点的个数，那么两者满足关系 $n_0=n_2+1$。

如下图中，叶结点有 D、J、K、H 共四个，即 $n_0=4$，而度为 2 的结点有 A、B、E 共三个，即 $n_2=3$，满足前面所述的关系。

结论的推导：

设 $n_1$ 表示度为 1 的结点的个数，也就是说 $n_0+n_1+n_2$ 就是总结点数。

从下往上看，除了根结点外，其他每个结点都有一条向上的边，所以边的总数为 $n_0+n_1+n_2-1$

再从上往下看，每个结点都有 0 条或 1 条或 2 条边，这些边的总数为 $0 \times n_0 + 1 \times n_1 + 2 \times n_2$

列方程 $n_0+n_1+n_2-1 = 0 \times n_0 + 1 \times n_1 + 2 \times n_2$，即可推出上面的结论。

二叉树的存储

数组存储

完全二叉树可以很方便地用数组存储。将结点按从上到下，从左到右的顺序按顺序存入数组即可：

这样存储后，可以通过计算的方式算出某个结点的子结点、父结点：

假设某个非根结点的序号为 $i$，结点总数为 $n$，则：
- 其父结点的序号为 $\lfloor i \div 2 \rfloor$
- 其左子结点的序号为 $2i$。（如果 $2i \le n$，则没有左子结点）
- 其右子结点的序号为 $2i+1$。（如果 $2i + 1 \le n$，则没有右子结点）
如果是一般的二叉树，可以先将其补充成一棵完全二叉树，再用数组存储：

可以很明显地看出，这种存储方式会造成空间上的浪费。

链表存储

链表存储显然是可行的，因为二叉树的度为 2，每个结点只需要两个指针。

结点的定义：

typedef struct TreeNode* BinTree;
struct TreeNode {
    ElementType data;	// 数据域
    BinTree left;	// 指向左孩子
    BinTree right;	// 指向右孩子
}

二叉树的遍历

深度优先遍历（递归）

先序遍历：

void preOrderTraversal(BinTree bt) {
    if (bt) {
        visit(bt->data);
        preOrderTraversal(bt->left);
        preOrderTraversal(bt->right);
    }
}

中序遍历和后序遍历只是 visit() 放的位置不一样。

数据结构与算法 —— 树、堆

2020-03-16
数据结构与算法

数据结构与算法 —— 树、堆

树的定义及基本术语

树的表示

数组实现