二叉树遍历：数据结构与算法的通俗易懂讲解

很多小伙伴都老是会碰到疑问，其实还是基础没打扎实，这些题如果你不看答案你能知道多少呢？如果还有很多不知道就证明基础没打扎实，如果你还在入门纠结，如果你还在苦恼怎么入门！小编有个建议，可以加小编弄的一个C语言交流基地，大家可以进入交流基地：379249575，里面新手入门资料，可以说从零到项目实战，都是可以免费获取的，还有程序员大牛为各位免费解答问题，热心肠的小伙伴也是蛮多的。不失为是一个交流的的好地方，小编在这里邀请大家加入我的大家庭。欢迎你的到来。一起交流学习！共同进步！小编等你！

在通俗易懂讲解 二叉搜索树一文中主要介绍了二叉搜索树的性质,本文将继续介绍二叉树的遍历。

二叉搜索树的遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同主要分为前序遍历，中序遍历，后序遍历。注意，二叉搜索树和普通的二叉树其遍历是一模一样的，因此下文中，不区分是二叉搜索树还是二叉树。

前序遍历

对一颗二叉树的前序遍历操作如下：

• 访问根节点

• 前序遍历左子树

• 前序遍历右子树

例如下图中二叉树前序遍历节点访问顺序为3 1 2 5 4 6：

根据前面所分析的前序遍历的操作步骤，不难看出很容易用递归的方法实现二叉树的前序访问：

其实，还能以非递归的方式实现二叉树的前序遍历：由于在遍历完根节点后还要将其找回来以便遍历该根节点对应的右子树，因此可以考虑使用栈来存储访问过的根节点，代码实现如下：

中序遍历

对一颗二叉树的中序遍历操作如下：

• 中序遍历左子树

• 访问根节点

• 中序遍历右子树

例如下图中二叉树中序遍历节点访问顺序为1 2 3 4 5 6：

如同前序遍历一样，也可以用递归或者非递归的方式实现，而且其思想也类似，只是访问的顺序不一样了，其两种实现方式如下：

后续遍历

对一颗二叉树的后序遍历操作如下：

• 后序遍历左子树

• 后序遍历右子树

• 访问根节点

例如下图中二叉树后序遍历节点访问顺序为2 1 4 6 5 3：

二叉树后序遍历递归版本与前序中序类似，如下：

后序遍历的非递归算法较复杂，使用一个栈可以实现，但是过程很繁琐，我们可以考虑用两个栈来实现后序遍历的非递归算法。注意到后序遍历可以看作是下面遍历的逆过程：即先遍历某个结点，然后遍历其右孩子，然后遍历其左孩子。这个过程逆过来就是后序遍历。算法步骤如下：

(1) push根结点到第一个栈s中。

(2) 从栈s中pop一个结点，将其push到栈output中。

(3) 然后push结点的左孩子和右孩子到第一个栈s中。

(4) 重复过程2和3直到栈s为空。

(5) 现在所有结点已经push到栈output中，且按照后序遍历的顺序存放，直接全部 pop出来即是二叉树后序遍历结果。

代码实现如下：

为您提供通俗易懂的技术文章，让技术变的更简单！喜欢这篇文章的话记得关注哦！正在学习的小伙伴也可以加群一起来学习或探讨C/C++。最后，谢谢大家的支持！！！