二叉树的遍历采用递归实现是比较简单的一种方式，在实际使用中也常会采用递归实现。但了解如何采用非递归实现，更能加深对二叉树遍历的原理。
非递归的遍历实现，实际会使用到栈的结构。通过对树节点的入栈和出栈，实现二叉树的遍历。
以下为实现代码（Java）：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
| package com.algorithms;
import java.util.Stack;
public class BinaryTree {
/**
* 二叉树前序打印-递归实现
*
* @param node 根节点
*/
public static void preSearch(Node node) {
if (node == null) {
return;
}
System.out.print(node.val + " ");
preSearch(node.left);
preSearch(node.right);
}
/**
* 二叉树前序打印-遍历实现
*
* @param node 根节点
*/
public static void preSearchV2(Node node) {
Stack<Node> stack = new Stack<>();
stack.add(node);
while (!stack.empty()) {
Node n = stack.pop();
System.out.print(n.val + " ");
if (n.right != null) {
stack.add(n.right);
}
if (n.left != null) {
stack.add(n.left);
}
}
}
/**
* 二叉树中序打印-递归实现
*
* @param node 根节点
*/
public static void midSearch(Node node) {
if (node == null) {
return;
}
midSearch(node.left);
System.out.print(node.val + " ");
midSearch(node.right);
}
/**
* 二叉树中序打印-遍历实现
*
* @param node 根节点
*/
public static void midSearchV2(Node node) {
Stack<Node> stack = new Stack<>();
while (!stack.empty() || node != null) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
System.out.print(node.val + " ");
node = node.right;
}
}
}
/**
* 二叉树后序打印-递归实现
*
* @param node 根节点
*/
public static void postSearch(Node node) {
if (node == null) {
return;
}
postSearch(node.left);
postSearch(node.right);
System.out.print(node.val + " ");
}
/**
* 二叉树后序打印-遍历实现
*
* @param node 根节点
*/
public static void postSearchV2(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
Node c;
stack.push(node);
while (!stack.empty()) {
c = stack.peek();
if (c.left != node && c.left != null && node != c.right) {
stack.push(c.left);
} else if (c.right != node && c.right != null) {
stack.push(c.right);
} else {
c = stack.pop();
System.out.print(c.val + " ");
node = c;
}
}
}
public static void main(String[] args) {
Node root = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
root.left = n2;
root.right = n3;
Node n4 = new Node(4);
Node n5 = new Node(5);
n2.left = n4;
n2.right = n5;
Node n6 = new Node(6);
Node n7 = new Node(7);
n3.left = n6;
n3.right = n7;
Node n8 = new Node(8);
Node n9 = new Node(9);
n5.left = n8;
n5.right = n9;
preSearch(root);
System.out.println();
preSearchV2(root);
System.out.println();
System.out.println();
midSearch(root);
System.out.println();
midSearchV2(root);
System.out.println();
System.out.println();
postSearch(root);
System.out.println();
postSearchV2(root);
}
}
|