数据结构与算法笔记（三）

树

数据结构中的树（Tree）与生活中常见的树?有些类似，可以类比为生活中的树?倒过来。示意图：

相关概念

每个元素称为「节点」，用来连线相邻节点之间的关系叫作「父子关系」。示意图：

其中，A 节点是 B 节点的「父节点」，B 节点是 A 节点的「子节点」。B、C、D 节点有同一个父节点 A，它们互称为「兄弟节点」。没有父节点的节点（E）称为「根节点」，没有子节点的节点（G、H、I、J）称为「叶子节点」或「叶节点」。

高度、深度和层

1. 节点的高度（Height）：节点到叶子节点的最长路径；

2. 节点的深度（Depth）：根节点到这个节点所经历的边的个数；

3. 节点的层数（Level）：节点的深度 + 1；

4. 树的高度：根节点的高度。

示意图：

二叉树

树的结构有多种，其中最常用的是二叉树（Binary Tree）。

二叉树的每个节点最多有两个“叉”，也就是两个节点，分别为「左子节点」和「右子节点」。如图所示：

1. 左边的二叉树：一棵普通的二叉树；

2. 中间的二叉树：叶子节点全都在最底层，而且除了叶子节点外，每个节点都有左右两个子节点，称为「满二叉树」；

3. 右边的二叉树：叶子节点都在最底下两层，且最后一层的叶子节点都靠左排列，除了最后一层，其他层的节点个数都达到最大，称为「完全二叉树」。

二叉树的存储

两种方式：基于指针（或引用）的链式存储法，基于数组的顺序存储法。

链式存储法：每个节点有三个字段，其中一个存数据，另外两个分别为指向左右子节点的指针。如图所示：

顺序存储法：根节点存储在下标为 i = 1 的位置，左子节点下标为 2 * i = 2， 右子节点下标为 2 * i + 1 = 3，以此类推。如图所示：

值得注意的是，这里存储的是一颗完全二叉树，因此它在数组中只有第一个位置为空。若不是完全二叉树，则其存储结构如下：

数组中为空的位置就很多，这样会浪费很多存储空间。

二叉树的遍历

二叉的遍历就是循环打印出二叉树中的所有节点。经典的方法有三种，分别为：前序遍历、中序遍历和后序遍历。其中的前、中、后指的是节点与它的左右子节点遍历打印的先后顺序，即：

1. 前序遍历：本节点 --> 左子节点 --> 右子节点；

2. 中序遍历：左子节点 --> 本节点 --> 右子节点；

3. 后序遍历：左子节点 --> 右子节点 --> 本节点。

可以看到，前、中、后就是本节点在遍历中的顺序。示意图：

二叉查找树

二叉查找树（Binary Search Tree）是二叉树中最常用的一种类型，又称「二叉搜索树」，它支持快速查找、插入、删除一个数据。

结构特点

二叉树中的任一节点，其左子树中每个节点的值，都小于该节点的值；右子树中每个节点的值都大于该节点的值。示意图：

查找

查找步骤：

1. 先将要查找元素的值与根节点的值比较，若相等则返回；

2. 若小于根节点的值，则在左子树中递归查找；

3. 若大于根节点的值，则在右子树中递归查找。

查找过程示意图：

插入

插入过程与查找的比较过程有些类似，操作示意图如下：

删除

相比查找和插入，删除过程略微复杂一些。主要分为三种情况：

1. 待删除的节点无子节点：直接删除（下图的节点 55）；

2. 待删除的节点有一个子节点：将待删除节点的父节点指向待删除节点的子节点（下图的节点 13）；

3. 待删除的结点有两个子节点：需要先找到待删除节点的右子树中的最小节点，用它替换要删除的节点，然后再删除该最小节点（下图的节点 18）。

这三种情况的删除操作示意图如下：

二叉树&散列表

1. 散列表中的数据是无序的；二叉查找树中序遍历可在 O(n) 时间复杂度内输出有序的数据序列；

2. 散列表的扩容比较耗时，散列冲突时性能不稳定；平衡二叉查找树的性能稳定在 O(logn)；

3. 散列表构造比二叉树复杂不少（散列函数设计、冲突解决、扩容等）；二叉树只需考虑平衡性问题，且解决方案比较成熟、固定。

堆

堆（Heap）是一种特殊的树，它满足以下结构特征：

1. 堆是一个完全二叉树；

2. 堆中每个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

其中，每个节点值都大于等于子树中每个节点值的堆称为「大顶堆」，小于等于树中每个节点值的堆称为「小顶堆」。示意图：

其中 1、2 为大顶堆，3 为小顶堆，4 不是堆（不是完全二叉树）。

存储

前面分析了二叉树的存储方法有两种：链式存储和顺序存储，而顺序存储比较适合完全二叉树。堆的顺序存储示例如下：

堆化

当向堆中插入元素、或从堆中删除元素时，可能会导致堆不满足其结构特点。因此需要对其进行调整使其重新满足堆的特性，该过程称为堆化（heapify）。

堆化有两种方式：从下往上和从上往下。

从下往上堆化示意图（插入节点 22）：

从上往下堆化示意图（删除节点 33）：

注意：这样操作会使堆不满足完全二叉树的特性。

如果转换思路，把最后一个节点放到堆顶，然后再进行从上到下堆化，如图所示：

这样就不会出现“数组空洞”，又能满足完全二叉树的特性。

应用场景

堆的几个非常重要的应用场景：优先级队列、Top K 问题、求中位数。

小结

1. 数据结构中的树可以类比生活中常见的树?倒过来。其中二叉树最常用，二叉树有两种特殊的情况：满二叉树和完全二叉树；

2. 二叉树的遍历方式有三种：前序、中序和后序遍历；在二叉树中，二叉查找树最常用，可以快速查找、插入、删除一个元素；

3. 堆是一种特殊的树：它是完全二叉树；且每个节点的值都大于等于（或小于等于）子树中每个节点的值（分别为大顶堆和小顶堆）。

相关阅读：

数据结构与算法笔记（二）

Stay hungry, stay foolish.