记得有次被别人问起二叉树的先序遍历，竟然不清楚？当然读书的时候是知道的，工作后有点忘了，只知道它是利用栈递归遍历的，至于这里的先序的“先”，到底指的是先遍历左子树还是先遍历根节点给忘了。

为加深印象，今天打算做个小小的总结，先不管工作上有没用到（其实是有用到的，比如楼主曾经做二值图像连通算法的时候，需要对图进行遍历，可使用深度或广度，与二叉树的遍历思想类似），毕竟面试的时候，这个知识点还是会经常问起的，如果不知道，未免略显尴尬。

尽量简单点，也不说那么多概念了，二叉树的遍历分为两种：深度优先遍历和广度优先遍历；深度优先遍历又分为三种，先序、中序和后序。

这里，我们就不细写具体的实现代码了，理解其思想就好，所有例子都是基于以下树进行遍历的。

深度优先遍历（辅助结构：栈）

先序遍历：根节点，左子树，右子树

结果：124563

中序遍历：左子树，根节点，右子树

结果：425613

后序遍历：左子树，右子树，根节点

结果：465231

关于先序、中序、后序遍历，我只说一点：就是这里的先、中、后指的是根节点，根节点，根节点。。。。

广度优先遍历（辅助结构：队列）

很简单，结果为：123456

补充一下：广度优先遍历又叫层次遍历，感觉这个名字更加形象点，另外，每次遍历完一个节点会将它的子节点做入队操作。

本文转自风一样的码农博客园博客，原文链接：http://www.cnblogs.com/chenpi/p/5555608.html，如需转载请自行联系原作者