树 (Tree)

什么是树？

基础概念

  • 高度 (Height) 节点到叶子节点的最长路径（边数）

  • 深度 (Depth) 根节点到目标节点的路径（边数）

  • 层 (Level) 节点的深度 + 1

二叉树 (Binary Tree)

二叉树是一棵树，其中每个节点都不能有多于两个的孩子节点。

二叉树的一个性质是一棵平均二叉树的深度要比节点个数 N 小得多，这个性质有时很重要。

分析表明，其平均深度为 O(根号N)，而对于特殊类型的二叉树，即**二叉查找树 (Binary Search Tree)**，其深度的平均值是 O(logN)。不幸的是，这个深度是可以大到 N - 1 的。

  • 满二叉树 叶子节点都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。
  • 完全二叉树 叶子节点都在最底下两层，最底层的叶子节点都靠左排列，且除了最底层外，其他层的节点个数都要达到最大。

完全二叉树

满二叉树的特征非常明显，把它单独拎出来讲，可以理解。但完全二叉树的特征并不明显，单从长相上来看，完全二叉树并没有特别特殊的地方，更像是“芸芸众树”中的一种。

  • 为何还要特意地把它拎出来讲？
  • 为何偏偏把最底层的叶子节点靠左排列，而不是靠右排列？

存储结构

要完全理解二叉树定义的由来，需要先了解，如何表示（或者存储）一棵二叉树？

存储一棵二叉树一般有两种方法，一种是基于指针或者引用的二叉链式存储法；一种是基于数组的顺序存储法。

链式存储法

从下图中可以清晰地看出，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。

根据根节点，通过其左右子节点的指针，即可把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种结构来实现的。

顺序存储法

把根节点存储在下标 i = 1 的位置，其左子节点存储在下标 2 * i 的位置，其右子节点存储在 2 * i +1 的位置，以此类推。

反过来，下标为 i / 2 的位置存储它的父节点。

通过这种方式，只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），即可通过下标计算，把整棵树都串起来。

不过，上述的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，则会浪费较多的数组存储空间。

💡 所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。

因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。

这是为何完全二叉树会单独拎出来讲的原因，也是为何完全二叉树要求最底层的节点都靠左的原因。

二叉树的遍历

  • 前序遍历 对于树中的任意节点来说，先打印它本身，然后打印它的左子树，最后打印它的右子树。

  • 中序遍历 对于树中的任意节点来说，先打印它的左子树，然后打印它本身，最后打印它的右子树。

  • 后序遍历 对于树中的任意节点来说，先打印它的左子树，然后打印它的右子树，最后打印它本身。

实际上，二叉树的前、中、后序遍历就是一个递归的过程。

写递归代码的关键，是看能否找到递推公式，而写递推公式的关键就是，如果要解决问题 A，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。

因此，可以先把前、中、后序遍历的递推公式都写出来：

1
2
3
4
5
6
7
8
前序遍历的递推公式：
preOrder(r) = print r -> preOrder(r->left) -> preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = preOrder(r->left) -> print r -> preOrder(r->right)

后序遍历的递推公式：
postOrder(r) = preOrder(r->left) -> preOrder(r->right) -> print r

有了递推公式，代码写起来就简单多了：

时间复杂度分析

从上面前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，即二叉树遍历的时间复杂度是 O(n)。

扩展：表达式树

下图显示一个**表达式树 (expression tree)，其叶子节点为操作数 (operand)，其他节点为操作符 (operator)**。

在本例中，左子树的值是 a + (b * c)，右子树的值是 ((d * e) + f) * g，因此整棵树表示 (a + (b * c)) + ((d * e) + f) * g)。

通过二叉树的中序遍历，递归地产生左右括号，可以得到表达式树的表达式类型 (a + (b * c)) + ((d * e) + f) * g)。

通过二叉树的后序遍历，可以得到表达式 a b c * + d e * f + g * +。

构造表达式树

有了中、后序遍历得到的表达式，要想构造表达式树，就是通过一种算法，把后缀表达式转变成中缀表达式。

具体的做法是，一次一个字符地读入后缀表达式：

  • 若符号是操作数，建立一个单节点树并将它入栈
  • 若符号是操作符，从栈中弹出两棵树 T1 和 T2（T1 先弹出）并形成一棵新的树，然后将这棵新树入栈

看一个例子，设输入为：

1
a b + c d e + **

前两个字符是操作数，因此创建两棵单节点树并将它们依次入栈：

接着，+ 被读入，因此两棵树依次弹出，一棵新的树形成，并被压入栈中：

然后，c、d 和 e 被读入，在每个单节点树创建后，对应的树被压入栈中：

接下来读入 + 号，因此两棵树合并：

继续进行，读入 * 号，因此，弹出两棵树并形成一棵新的树，* 是它的根：

最后，读入最后一个符号，两棵树合并，而最后的树被留在栈中：