数据结构之树

# 1 树

树的结构：除根节点外每个节点只有一个父节点，根节点没有父节点；除叶节点外每个节点只有一个或多个子节点，叶节点没有子节点。父节点和子节点用指针链接。

树的遍历：前序遍历、中序遍历、后序遍历，其递归和循环实现都要熟练掌握。此外还有广度优先遍历。

二叉树的特例：

• 二叉搜索树：平均 O(logn) 找到一个节点；
• 堆：最大堆、最小堆，用于解决快速找到最大最小值的问题；
• 红黑树：规则保证从根节点到叶节点最长路径的长度不超过最短路径的两倍。

# 1.1 二叉树遍历

前序遍历最先出现的是根节点，中序遍历可以通过根节点划分左右子树，后续遍历最后出现的是根节点。

因此根据中序序列和前序序列（后序序列），可以唯一重建一棵二叉树。但通过前序序列和后序序列无法确定一棵二叉树。

以前序 + 中序为例，方法如下：

• 确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。

• 求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。

• 递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位

中序遍历时，下一个节点的确定过程：

• 若该节点有右子树，则下一个节点为右子树的左叶子节点；

• 若无右子树，则（1）如果该节点是父节点的左子节点，那么下一个节点为父节点 （2）如果该节点是父节点的右子节点，那么回溯直到找到满足条件（1）的节点。

# 1.2 二叉树的深度（0622更新）

递归后序遍历，左右子树中较大深度 +1。

# 1.3 二叉树的路径（0622更新）

前序遍历，借助堆栈思想存储路径。

# 1.4 最大堆/最小堆（0624更新）

下面以最大堆为例，最小堆类似。

• 是完全二叉树，不一定是满二叉树；

• 父节点大于或等于子节点的值。

由于是完全二叉树，因此借助数组的形式来存储，若数组下标从 1 开始，最大堆中父节点下标与子节点下标是两倍关系。

heap[father * 2] == heap[leftChild]; 
heap[father * 2] == heap[rightChild];

最大堆的效率：O(1) 完成最大值查找，O(logn) 完成插入和删除。

# 1.5 红黑树（0625更新）

C++ 中的 set 和 multiset 都是基于红黑树实现的。

红黑树是一种特殊的二叉查找树，它的特征如下：

• 每个节点或者是黑色，或者是红色。

• 根节点是黑色。

• 每个叶子节点都是黑色。这里的叶子节点指为空（nullptr）的节点。

• 如果一个节点是红色的，那么他的子节点必须是黑色的。

• 从一个节点到所有子孙节点的路径上包含相同数目的黑节点。

注意，最后一个特性确保没有一个路径会比其他路径长出两倍，因而红黑树是接近平衡的二叉树。