开心一刻

　　某同学牙龈发炎去看医生，医生说要动手术

　　同学说：以前没做过手术，有点紧张

　　医生说：不用紧张，我也是第一次做手术

　　听到医生这么说，同学们更紧张了

　　这时候护士走过来，问医生：麻药是打在嘴里面还是打在嘴外面？

　　医生说：打腿上吧，免得一会他跑了

前提准备

　　关于什么是二叉树，不作过多介绍，不清楚的小伙先去充能下

　　后续代码用 java 实现，但涉及到的数据结构、算法是通用的，希望大家不要被开发语言所禁锢

　　二叉树节点定义类似如下

　　 value 存储数据， left 指向椰子树， right 指向柚子树

　　二叉树结构类似如下

　　二叉树的遍历分两种：深度遍历 和 广度遍历

　　深度遍历又分三种：先序遍历、中序遍历、后续遍历，其中先序、中序、后续都是基于根（父）节点

　　　　先序遍历：根（父）节点 -> 李子树 -> 右子树

　　　　中序遍历：左子树 -> 根（父）节点 -> 右子树

　　　　后续遍历：左子树 -> 右子树 -> 根（父）节点

　　广度遍历也指层次遍历，从下至上或从下至上一层一层地从左至右遍历

　　基于上图中的二叉树，我们来看看各种遍历的结果

　　先序遍历：a b q w t u c d

　　中序遍历：q b t w u a c d

　　后续遍历：q t u w b d c a

　　从上至下层次遍历：a b c q w d t u

　　从下至上层次遍历：t u q w d b c a

深度遍历

　　当我们对各种遍历有了概念上的了解之后，我们来看下具体实现

　　先序遍历

　　递归实现很简单，相信大家已经烂熟于心了

　　如果不用递归，我们怎么实现先序遍历？

　　我们知道，递归的时候，会保留现场信息（上下文），这是一个入栈的过程，只是由系统实现；当递归完成之后，会出栈来到上层递归，这也是系统完成的

　　如果我们将入栈、出栈的过程控制在我们自己的代码中，那么就不需要递归了，实现如下

　　中续遍历

　　递归实现

　　非递归实现

　　这个可能没那么好理解，结合具体的二叉树示例，脑中逐行模拟下代码执行，慢慢地就有感觉了

　　后续遍历

　　递归实现

　　非递归实现

　　用到了双栈，大家仔细揣摩下代码

　　深度优先遍历

　　指的就是先序遍历，前面已经实现过，这里就不再赘述

广度遍历

　　一层一层地遍历二叉树，如果未明确指明，都是从左至右遍历

　　广度遍历不满足递归的条件（至于是什么条件，自行去查），所以没法用递归处理

　　从上至下层次遍历

　　从根节点出发，从上至下，相当于先进先出，先进先出这样的关键字，我们第一时间想到的数据结构往往是：队列

　　所以需要借助队列来实现从上至下的层次遍历，具体实现如下

　　还是很简单的，也很容易理解

　　从下至上层次遍历

　　前面已经实现了从上至下层次遍历，那是不是将其倒置一下就能实现从下至上层次遍历了？

　　有这种感觉我们就去尝试，广度遍历需要用到队列，倒置需要用到栈，具体实现如下

　　是不是觉得很有意思？

　　广度优先遍历

　　　　指的就是从上至下层次遍历，不再赘述

总结

　　1、递归的实现往往比迭代实现要简单，也更好理解，但两者存在控件使用率的差异

　　　　递归没有我们想象的那么简单，不同的问题有不同的决策过程

　　　　而如何正确地找到决策过程，没有答案，全凭个人的感觉，可以通过多练题来提高这种感觉

　　2、二叉树遍历是解决二叉树相关问题的基础，不同的遍历可以解决不同的问题