二叉树的遍历(递归及非递归方式)
二叉树的先序、中序、后序遍历，递归以及非递归方式。
1,递归方式的先序、中序、后序
如下代码所示，是递归的方式，区别就是打印输出的时机，分别对应着先序、中序、后序。
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
| public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
public static void inOrderRecur(Node head) {
if (head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}
public static void posOrderRecur(Node head) {
if (head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.value + " ");
}
|
2，非递归方式
先序遍历：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public static void preOrderUnRecur(Node head) {
System.out.print("pre-order: ");
if (head != null) {
//new一个栈
Stack<Node> stack = new Stack<Node>();
//把头结点压栈
stack.add(head);
//循环，当栈不为空的时
while (!stack.isEmpty()) {
//弹出头结点并打印
head = stack.pop();
System.out.print(head.value + " ");
//这是主要的处理逻辑，当右孩子不为空时，右孩子压栈，即"有右先压右"
if (head.right != null) {
stack.push(head.right);
}
//当左孩子不为空时左孩子压栈，这一步在右孩子压栈之后，即"有左后压左"
if (head.left != null) {
stack.push(head.left);
}
}
}
System.out.println();
}
|
中序遍历：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static void inOrderUnRecur(Node head) {
System.out.print("in-order: ");
if (head != null) {
//new一个栈
Stack<Node> stack = new Stack<Node>();
//当栈不为空或者二叉树不为空
while (!stack.isEmpty() || head != null) {
//左孩子存在，那就一溜把左孩子压栈
if (head != null) {
stack.push(head);
head = head.left;
}
else {
//从栈中弹出一个结点并打印
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
|
后序遍历：
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
| public static void posOrderUnRecur1(Node head) {
System.out.print("pos-order: ");
if (head != null) {
//new两个栈，一个作为辅助使用
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
//s1栈压入头结点
s1.push(head);
//s1不为空
while (!s1.isEmpty()) {
//弹出s1的结点
head = s1.pop();
//压入s2中
s2.push(head);
//左孩子不为空，就把它压入s1栈中
if (head.left != null) {
s1.push(head.left);
}
//右孩子不为空，也把它压入s1栈中
if (head.right != null) {
s1.push(head.right);
}
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
|