算法Java实现对二叉树前序/中序/后序的递归与非递归算法
代长亚二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
首先创建节点类，并在里面添加了一个创建树的方法，调用后就可以返回一个包含7个节点的二叉树。
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
| public class Node {
// 节点值
public int value;
// 左子节点
public Node left;
// 右子节点
public Node right;
Node(int va) {
value = va;
}
Node(int va, Node le, Node ri) {
value = va;
left = le;
ri = right;
}
/**
* 创建一颗二叉树
*
* @return 根节点
*/
public static Node createTree() {
Node root = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
node3.left = node7;
return root;
}
}
|
创建遍历类，在该类里实现各种遍历方法。
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
| import java.util.ArrayList;
public class Traverse {
/**
* 递归前序遍历
*
* @param root
*/
public void recursiveProOrder(Node root) {
// 遍历根节点
if (root != null) {
System.out.print(root.value);
}
// 遍历左子树
if (root.left != null) {
recursiveProOrder(root.left);
}
// 遍历右子树
if (root.right != null) {
recursiveProOrder(root.right);
}
}
/**
* 前序遍历
*
* @param root
*/
public void proOrder(Node root) {
// 使用ArrayList作为堆栈
ArrayList<Node> stack = new ArrayList<Node>();
// 栈指针
int top = -1;
Node current = root;
while (true) {
if (current != null) {
System.out.print(current.value);
}
// 右子节点进栈
if (current.right != null) {
stack.add(current.right);
top++;
}
// 左子节点进栈
if (current.left != null) {
stack.add(current.left);
top++;
}
// 如果栈内还有节点，栈顶节点出栈
if (top > -1) {
current = stack.get(top);
stack.remove(top--);
} else {
break;
}
}
}
/**
* 递归中序遍历
*
* @param root
*/
public void recursiveInOrder(Node root) {
if (root != null) {
if (root.left != null) {
recursiveInOrder(root.left);
}
System.out.print(root.value);
if (root.right != null) {
recursiveInOrder(root.right);
}
}
}
/**
* 中序遍历
*
* @param root
*/
public void inOrder(Node root) {
if (root != null) {
ArrayList<Node> stack = new ArrayList<Node>();
int top = -1;
Node current = root;
while (current != null || top > -1) {
if (current != null) {
// 一直深入地寻找左子节点，并将路上的节点都进栈
stack.add(current);
top++;
current = current.left;
} else {
// 取出栈顶节点，并继续遍历右子树
current = stack.get(top);
stack.remove(top--);
System.out.print(current.value);
current = current.right;
}
}
}
}
/**
* 递归后续遍历
*
* @param root
*/
public void recursivePostOrder(Node root) {
if (root != null) {
if (root.left != null) {
recursivePostOrder(root.left);
}
if (root.right != null) {
recursivePostOrder(root.right);
}
System.out.print(root.value);
}
}
/**
* 后序遍历：可以被遍历的节点都要进栈出栈两次，所以添加第二个栈用来标示进栈次数
*
* @param root
*/
public void postOrder(Node root) {
if (root != null) {
// 用来保存节点的栈
ArrayList<Node> stack = new ArrayList<Node>();
// 用来保存标志位的栈
ArrayList<Integer> stack2 = new ArrayList<Integer>();
// 两个栈共用的栈指针
int top = -1;
int tag;
Node current = root;
do {
//将所有左子节点进栈
while (current != null) {
stack.add(current);
stack2.add(0);
top++;
current = current.left;
}
//取出栈顶节点，并判断其标志位
current = stack.get(top);
tag = stack2.get(top);
stack2.remove(top);
if (tag == 0) {
// tag为0,表明该节点第一次进栈，还需要进栈一次，同时修改标志位
current = current.right;
stack2.add(1);
} else {
// tag不位0,表明非首次进栈，可以遍历了。
stack.remove(top);
top--;
System.out.print(current.value);
current = null;
}
} while (current != null || top != -1);
}
}
}
|
实例化遍历类并调用各个遍历方法。
点击(此处)折叠或打开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Algorithm {
public static void main(String[] args) {
Node root=Node.createTree();
System.out.print("前序遍历： ");
new Traverse().proOrder(root);
System.out.println();
System.out.print("前序递归遍历： ");
new Traverse().recursiveProOrder(root);
System.out.println();
System.out.print("中序遍历： ");
new Traverse().inOrder(root);
System.out.println();
System.out.print("中序递归遍历： ");
new Traverse().recursiveInOrder(root);
System.out.println();
System.out.print("后序遍历： ");
new Traverse().postOrder(root);
System.out.println();
System.out.print("后序递归遍历： ");
new Traverse().recursivePostOrder(root);
}
|
输出结果：
前序遍历： 01374256
前序递归遍历： 01374256
中序遍历： 73140526
中序递归遍历： 73140526
后序遍历： 73415620
后序递归遍历： 73415620
