上一篇文章介绍了链表，这篇文章继续分享算法心得，即另一个重要的数据结构——树。
树的特点
树和链表相对比，会更加复杂一些。实际上链表中节点有一个指针指向下一个节点，而在树中，有两个指针，分别指向左，右两个孩子节点。这种对应关系，就不是链表中的一对一了，在树中，对应关系就是一对多了。如果说链表可以理解为一维的世界，则树就是二维的世界了。特别的，树这个二维世界有一个非常重要的节点就是根节点，这个节点可以认为是树的特征节点。因此解决树的问题，找准根节点是非常重要。
在23种设计模式中，组合模式就是运用了树这种数据结构。组合模式的意思就是操作树根这一个元素，好像同时操作整个树一样。在实际的应用中，树可以理解为一种层级结构，比如界面，windows可能是树根，树根会有视图，视图又可分为用户自定义的各种视图控件，整个的ui界面，可以理解为一棵完整的树，而操作树根，比如windows接收到了点击事件，就可以将这个事件分发给这课树的所有节点。这就是组合模式。
树的一个重要的特点，就是有一定的递归性，因此，在解决树相关的问题时，递归的方法，显然是首选。另外，结合树中最重要的要点，就是找到树的特征也就是树根。把握好这两个方面，很多树相关的问题就可以解决了。
树的遍历
树既然具有二维性，一个重要的课题就是将二维转换为一维，也就是树的遍历。树的遍历总共分为三种，前序遍历，中序遍历和后序遍历。这里的前，中和后都是说的根，也就是根遍历的顺序。实际上在树的遍历中，永远是先左节点，后右节点的。但是关键是根节点。如果先是根节点，然后左节点，最后右节点，就是前序遍历，也就是根在前面遍历。如果先是左节点，然后根节点，最后右节点，就是中序遍历，也就是根在中间遍历。如果先是左节点，然后右节点，最后根节点，就是后序遍历，也就是根在最后遍历。
树的三种遍历方式，可以将二维的树，转换为一维的数组。前序，中序和后序是树的一维形态。二维可以转换为一维，那么一维是否可以转换为二维呢？这实际上就是一个面试题，我们将在下面详细分析。
树的典型算法题
面试题7：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
这是一道典型的由一维的遍历重构出二维的树。由于不含重复的数字，因此这种重构是可能的。可以这样理解，用两个一维数据，重构出二维数据，这是可行的。题目要求用前序遍历和中序遍历重建二叉树，而树的结构，最重要的两个元素就是根节点以及递归。一提到递归，我们就需要处理异常，终止以及问题化简。有了这些基本的武器后，我们看看如何解决这个问题。
解决树的问题最核心的是找到根节点，如何找到根节点呢？很简单，前序遍历中就有根节点了。前序遍历之所以称之为前序，就是因为是首先遍历根节点。因此，前序遍历可以理解为 根节点 + 左子树节点 + 右子树节点。如果我们想利用递归的思想，就必须对题目进行简化，简化的方法就是将树的问题转换为左子树和右子树的问题，这样，就找到了问题的子问题。这里我们根据前序遍历的特点，可以得到根节点，但是左子树和右子树的边界我们是不清楚的。因此，想到利用另一个已知，即中序遍历。中序遍历的遍历方式是 左子树节点 + 根节点 + 右子树节点。从前序遍历中，我们已经找到了根节点，因此从中序遍历中就可以确定了根节点的位置，根节点的左边就是左子树的中序遍历，根节点的右边就是右子树的中序遍历。特别的，我们可以得到左子树和右子树的元素的个数。确定了左子树和右子树元素的个数后，我们又可以通过前序遍历，确定左子树和右子树的分割边界。这样，我们就可以得到左右子树的前序遍历。
分析到这里，这个问题基本上就已经解开了，我们成功的将问题转换为子问题，即我们可以分别得到根节点，以及左右子树的前序和中序遍历。通过递归，我们就可以将这棵树重建起来。
面试题32：从上到下打印二叉树
题目：不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
为什么想分享这样一道面试题呢？因为这道面试题，体现了树这个数据结构可以和其他一些数据结构相组合。我们常用的数据结构还有什么呢？实际上还有先进先出的队列，以及先进后出的栈。有时，解决树相关的问题，也需要辅助队列，或者辅助栈，比如这道算法题就是一个典型。
这道题考察了一种特殊的树的遍历方式，这种方式既不是前序遍历，也不是中序遍历，更不是后序遍历。而是一种自定义的遍历方式，是按层级遍历，也就是自上而下的遍历。这种遍历方式似乎破坏了树的递归的特性，那么我们有没有什么好方法呢？
实际上这种遍历方式，有些道家的一生二，二生三，三生万物的意思了。或者更形象些，就是太极生两仪，两仪生四象，四象生八卦。这个太极，就是树的根结构。既然有“生”，就要有容器去容纳那些生出来的节点，由于这种“生”的方式，符合先进先出的特点，因此我们需要一个辅助队列。首先我们把树根扔进这个队列中，然后开始处理队列。处理队列的时候，我们首先将队头的那个节点的左右子节点扔进队列中，然后将这个节点弹出队列，打印其信息。如此操作，就是符合题目的遍历方式了。
通过这个面试题，我们可以很清晰的看到，树这种数据结构有时可以和其他基本数据结构相配合，比如这里，使用了一个辅助的队列。
小结
树的算法问题解决思路大多都是递归思想，因为这是由他的结构所决定的。特别的，对于树而言，最关键的就是找到他的根节点，找到了根节点，同时就可以确定其左子树和右子树，因此树的问题可以转换为左子树和右子树的子问题，因此可以采用递归的思想。另外要注意的是，树有可能会和其他基本数据结构相配合，比如栈和队列。
网友评论