五分钟让你彻底理解二叉树的非递归遍历

什么是二叉树

在计算机科学中二叉树，binary tree，是一种数据结构，在该数据结构中每个节点最多有两个子节点，如图所示：

二叉树的定义就是这样简单，但这种看起来很简单的数据结构遍历起来一点都不简单。

如何遍历二叉树

所谓遍历简单的讲就好比在迷宫中寻宝，宝物就藏在某一个树节点当中，但我们并不知道具体在哪个节点上，因此要找到宝物就需要将全部的树节点系统性的搜索一遍。

那么该怎么系统性的搜索一遍二叉树呢？

给定一个单链表你几乎不需要思考就能知道该如何遍历，很简单，拿到头节点后处理当前节点，然后拿到头节点的下一个节点(next)重复上述过程直到节点为空。

你会看到遍历链表的规则很简单，原因就在于链表本身足够简单，就是一条线，但是二叉树不一样，二叉树不是一条简单的"线"，而是一张三角形的"网"。

那么给定一棵二叉树，你该如何遍历呢？以上图为例，你该如何系统性的搜索一遍所有的节点呢(1,2,3,4,5,6)？

有的同学可能已经看出来了，我们可以一层一层的搜索，依次从左到右遍历每一层节点，直到当前层没有节点为止，这是二叉树的一种遍历方法。树的这种层级遍历方法利用了树的深度这一信息(相对于根节点来说)，同一层的节点其深度相同，那么我们是不是可以利用树有左右子树这一特点来进行遍历呢？答案是肯定的。

如上图所示1的左子树是2，2的左子树是3，2的右子树是4。。。

假设我们首先遍历根节点1，然后呢，你可能会想然后遍历2的左子树吧，也就是2，当我们到了2这个节点之后再怎么办呢？要遍历2的右子树吗？显然我们不应该去遍历2的右子树，为什么？原因很简单，因为从节点1到节点2我们是沿着左子树的方向来遍历的，我们没有理由到节点2的时候改变这一规则，接下来我们继续沿用这一规则，也就是首先遍历左子树。

我们来到了节点3，节点3的左子树为空，因此无需遍历，然后呢？显然我们应该遍历节点3的右子树，但是3的右子树也为空，这时以3为根节点的树全部遍历完毕。

当遍历完节点3后该怎么办呢？如果你在迷宫中位于节点3，此时节点3已经是死胡同了，因此你需要做的就是沿着来时的路原路返回，回退到上一个节点也就是3的父节点2，这在计算机算法中被称为回溯，这是系统性搜索过程中常见的操作，回到2后我们发现2的左子树已经搜索完毕，因此接下来需要搜索的就是2的右子树也就是节点4，因为节点4还没有被搜索过，当来到节点4后我们可以继续使用上述规则直到这颗树种所有的节点搜索完毕为止，为什么到节点4的时候可以继续沿用之前的规则，原因很简单，因为以4为根节点的子树本身也是一棵树，因此上述规则同样适用。

因此总结一下该规则就是：

处理当前节点；
搜索当前节点的左子树；
左子树搜索完毕后搜索当前节点的右子树；

这种先处理当前节点，然后再处理当前节点的左子树和右子树的遍历方式被称为先序遍历(pre_order)；当然我们也可以先遍历左子树，然后处理当前节点再遍历右子树，这种遍历顺序被称为中序遍历(in_order)；也可以先遍历左子树再遍历右子树，最后处理当前节点，这种遍历顺序被称为后序遍历(post_order)。

递归实现遍历二叉树

在讲解递归遍历二叉树前我们首先用代码表示一下二叉树的结构：

struct tree {
struct tree* left;
struct tree* right;
int value;
};

从定义上我们可以看出树本身就是递归定义的，二叉树的左子树是二叉树(struct tree* left)，二叉树的右子树也是二叉树(struct tree* right)。假设给定一颗二叉树t，我们该如何遍历这颗二叉树呢？

struct tree* t;  // 给定一颗二叉树

有的同学可能会觉得二叉树的遍历是一个非常复杂的过程，真的是这样的吗？

我们再来看一下上一节中遍历二叉树的规则：

处理当前节点；
搜索当前节点的左子树；
左子树搜索完毕后搜索当前节点的右子树；

假设我们已经实现了树的遍历函数，这个函数是这样定义的：

void search_tree(struct tree* t);

只要调用search_tree函数我们就能把一棵树的所有节点打印出来：

struct tree* t;   // 给定一颗二叉树
search_tree(t);   // 打印二叉树所有节点

要是真的有这样一个函数实际上我们的任务就完成了，如果我问你用这个函数把树t的左子树节点都打印出来该怎么写代码你肯定会觉得侮辱智商，很简单啊，不就是把树t的左子树传给search_tree这个函数吗？

seartch_tree(t->left);   // 打印树t的左子树

那么打印树t的右子树呢？同样easy啊

search_tree(t->right); // 打印树t的右子树

是不是很简单，那么打印当前节点的值呢？你肯定已经懒得搭理我了