二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点
前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。
即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。
从根节点开始，开始遍历，并输出（先序遍历首先输出根）
递归输出直至最左（先序根后面输出的是左孩子）
当到达最左节点的时候，访问右节点
因此其处理过程如下：
对于任一结点p：
访问结点p，并将结点p入栈;
判断结点p的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点p，循环至1);若不为空，则将p的左孩子置为当前的结点p;
直到p为null并且栈为空，则遍历结束。
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
另外还有一种方法，如果我们把一颗树当成一个图，前序，中序和后序遍历都是深度优先遍历的特例。
而其前前序遍历与深度优先遍历最像，打印顺序也一致，因此前序遍历也可以用深度优先搜索来实现
中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。
从根节点开始，开始遍历
递归输出直至最左，然后输出（中序先输出左孩子，而中序遍历第一个输出的是其最左叶子节点）
对于任一结点p，
若其左孩子不为空，则将p入栈并将p的左孩子置为当前的p，然后对当前结点p再进行相同的处理；
若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的p置为栈顶结点的右孩子；
直到p为null并且栈为空则遍历结束
40
41
42
后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。
43
44
45
46
47
48
49
50
51
52
第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。如果p不存在左孩子和右孩子，则可以直接访问它；或者p存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
其实后序遍历中当前节点要是想被输出, 要么
其左右孩子均为null
其左孩子刚被输出，而其右孩子为null
其右孩子刚被输出
但是这里有一个优化, 入栈时候, 先是根入栈， 然后是右孩子, 然后是左孩子,
因此当跟元素位于栈顶的时候, 其左右孩子必然已经弹出，即被访问并且输出,
也就是说, 判断当前节点是否需要输出时，只需要之前被输出的节点pre是当前栈定节点cur的孩子就行
即后序遍历中当前栈顶元素要是想被输出
其孩子（不论左右）刚被输出即可
而且如果刚被输出的节点是其左孩子，那么我们可以确定其有孩子必为null，否则它后于父节点入栈，应该在父节点之前被弹出并且输出
因此我们的输出判断可以改为
利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加
首先我们用递归的方式来打印某一层的信息
如果我们要打印第n层，那么就需要从根节点开始递归的遍历，当到达我们制定的层次时，就输出。
打印第n层的递归函数如下
如果我们想要打印第2层，就直接调用如下的即可
当然我们也可以采用层次递减的方式，level = n为希望递归的层次，而层次每深入一次，level递减，当level=0时，则说明递归至第n层
能够打印第n层的节点，那么我们实现层次遍历就简单了，循环调用递归每一层的节点即可
以上的方法可以很清楚的看出，存在重复访问的情况，就是第0层访问的次数最多，第1层次之。所以这个递归的方法不是很有效的方法，但是却不需要消耗额外的空间
第一个尝试，利用了两个队列，一个储存本层的节点，另一个储存下层的节点。遍历本层的节点，把其子代节点排入下层队列。本层遍历完毕后，就可换行，并交换两个队列。
我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。
本实现使用deque而不是queue，因为deque才支持swap()操作。注意，swap()是o(1)的操作，实际上只是交换指针。
这实现要用两个循环(书上的实现也是)，并且用了两个队列。能够只用一个循环、一个队列么?
其实我们只需要使用标识能够标识出每层的结束即可，因此可以归纳为如下的方法
* 双指针法，标识每层的开始结点和结束节点
size方法，同双指针法，标识每层的节点数目
end标识，在每层结束后，插入一个标识（如null或者特殊节点）来表示结束
第三种方法就是设置双指针，一个curr指向访问当层开始的节点，一个end指向访问当层结束节点的下一个位置
同样类似的方式，这种方式就是用了两个指针，分别表示每层的开始和结束。
相同的，我们也可以使用两个size来表示当前队列中父节点的个数和子节点的个数
转载：http://blog.csdn.net/gatieme/article/details/51163010
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)