数据结构之树

# 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];
1
2

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

# 1.5 红黑树(0625更新)

C++ 中的 setmultiset 都是基于红黑树实现的。

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

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

  • 根节点是黑色。

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

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

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

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