二叉树的遍历有层次遍历，前序遍历，中序遍历以及后续遍历。本文分别通过递归和非递归的方法来实现这些遍历。
二叉树的数据结构
1
2
3
4
5
6
7
8
9
| public class Node{
public int value ;
public Node left ;
public Node right ;
public Node(int val){
value = val ;
}
}
|
递归的写法其实很简单，主要是得有一个终止条件，有了这个终止条件后，一切都好说。
1
2
3
4
5
6
7
| public void preOrderRecur(Node root){
if(head == null)
return ;
System.out.println(root.value) ;
preOrderRecur(root.left) ;
preOrderRecur(root.right) ;
}
|
1
2
3
4
5
6
7
| public void inOrderRecur(Node root){
if(head == null)
return ;
inOrderRecur(root.left) ;
System.out.println(root.value) ;
inOrderRecur(root.right) ;
}
|
1
2
3
4
5
6
7
| public void postOrderRecur(Node root){
if(head == null)
return ;
postOrderRecur(root.left) ;
postOrderRecur(root.rigth) ;
System.out.println(root.value) ;
}
|
从上面的代码可以看到，只要写好了终止条件，其他的都很好说。下面主要介绍非递归的写法。
前序遍历的顺序是跟左右，然后，对于一棵二叉树，其实也就只有三个节点：跟左右，当你这么想的时候，问题就变简单了：
用一个栈，首先根节点入栈，好，此时栈中有元素了；
这时候我们出栈一个元素，访问它，然后以此将它的右孩子、左孩子入栈，然后出栈、访问，然后右孩子、左孩子入栈，如此重复。
为什么入栈时要先右孩子后左孩子呢？因为是栈啊，先进后出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public void preOrderIte(Node root){
Stack<Node> stack = new Stack() ;
Node cur = root ;
if(cur != null) {
stack.push(cur) ;
}
while (!stack.empty()){
cur = stack.pop();
System.out.println(cur.value);
if(cur.right!=null){
stack.push(cur.right) ;
}
if(cur.left!=null){
stack.push(cur.left) ;
}
}
}
|
再来考虑一下中序遍历，左、根、右。
就是说，首先我需要找到最左下方那个元素，然后依次左根右地遍历。那么我在向下寻找地过程中用一个栈把它地路径都存起来岂不是美滋滋。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public void inOrderIte(Node root){
Stack<Node> stack = new Stack<>() ;
Node cur = root ;
if(cur!=null) {
stack.push(cur);
cur = cur.left;
}
while (!stack.empty() || cur !=null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
System.out.println(cur.value);
cur = cur.right;
}
}
|
再来看下后序遍历，左右根。
同样地，我们认为这个二叉树只有三个节点，根，左，右，我们期望的遍历顺序是：左右根，左右根反过来的顺序是什么：根右左，是不是有点像先序遍历。所以我们可以先尝试搞一个它的逆序遍历根右左，然后把这个遍历顺序放到一个栈里面重新输出一下就可以了。
先重新审视一下先序遍历的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public void preOrderIte(Node root){
Stack<Node> stack = new Stack() ;
Node cur = root ;
if(cur != null) {
stack.push(cur) ;
}
while (!stack.empty()){
cur = stack.pop();
System.out.println(cur.value);
if(cur.right!=null){
stack.push(cur.right) ;
}
if(cur.left!=null){
stack.push(cur.left) ;
}
}
}
|
大概就是先根节点入栈，然后根节点出栈，右孩子入栈，左孩子入栈。
我们只需要稍微改动一下，就可以变成后序遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public void postOrderIte(Node root){
Stack<Node> stack = new Stack() ;
Stack<Node> stack2 = new Stack<>();
Node cur = root ;
if(cur != null) {
stack.push(cur) ;
}
while (!stack.empty()){
cur = stack.pop();
stack2.push(cur);
if(cur.left!=null){
stack.push(cur.left) ;
}
if(cur.right!=null){
stack.push(cur.right) ;
}
}
while (!stack2.empty()){
System.out.println(stack2.pop().value);
}
}
|
在先序里，每次s1的pop都对应着一次print, 在后序里，每次s1的pop都对应着s2的push.
还有就是，在先序里，先入栈右孩子，再入栈左孩子，在后序里，翻了过来，应为我们有两个栈。
