Question

树是一种在实际编程中经常遇到的数据结构。它的逻辑很简单：除了根结点之外每个结点只有一个父结点，根结点没有父结点；除了叶结点之外所有结点都有一个或多个子结点，叶结点没有子结点。父结点和子结点之间用指针链接。由于树的操作会涉及大量的指针，因此与树有关的面试题都不太容易。当面试官想考查应聘者在有复杂指针操作的情况下写代码的能力，他往往会想到用与树有关的面试题。

面试的时候提到的树，大部分都是二叉树。所谓二叉树是树的一种特殊结构，在二叉树中每个结点最多只能有两个子结点。在二叉树中最重要的操作莫过于遍历，即按照某一顺序访问树中的所有结点。通常树有如下几种遍历方式：

- 前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。图2.5中的二叉树的前序遍历的顺序是10、6、4、8、14、12、16。

- 中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。图2.5中的二叉树的中序遍历的顺序是4、6、8、10、12、14、16。

- 后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。图2.5中的二叉树的后序遍历的顺序是4、8、6、12、16、14、10。

图2.5　一个二叉树的例子

这3种遍历都有递归和循环两种不同的实现方法，每一种遍历的递归实现都比循环实现要简捷很多。很多面试官喜欢直接或间接考查遍历（面试题39二叉树的深度、面试题18树的子结构、面试题25二叉树中和为某一值的路径）的具体代码实现，面试题6重建二叉树、面试题24二叉树的后序遍历序列也是考查对遍历特点的理解，因此应聘者应该对这3种遍历的6种实现方法都了如指掌。

- 宽度优先遍历：先访问树的第一层结点，再访问树的第二层结点……一直到访问到最下面一层结点。在同一层结点中，以从左到右的顺序依次访问。我们可以对包括二叉树在内的所有树进行宽度优先遍历。图2.5中的二叉树的宽度优先遍历的顺序是10、6、14、4、8、12、16。

面试题23从上到下遍历二叉树就是考查宽度优先遍历算法的题目。

二叉树有很多特例，二叉搜索树就是其中之一。在二叉搜索树中，左子结点总是小于或等于根结点，而右子结点总是大于或等于根结点。图2.5中的二叉树就是一棵二叉搜索树。我们可以平均在O（logn）的时间内根据数值在二叉搜索树中找到一个结点。二叉搜索树的面试题有很多，比如面试题50树中两个结点的最低公共祖先、面试题27二叉搜索树与双向链表。

二叉树的另外两个特例是堆和红黑树。堆分为最大堆和最小堆。在最大堆中根结点的值最大，在最小堆中根结点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。红黑树是把树中的结点定义为红、黑两种颜色，并通过规则确保从根结点到叶结点的最长路径的长度不超过最短路径的两倍。在C++的STL中，set、multiset、map、multimap等数据结构都是基于红黑树实现的。与堆和红黑树相关的面试题，请参考面试题30求最小的k个数字。