0%

二叉树前中后序遍历(非递归)

伪代码:

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
先序遍历(先根)
将根节点入栈;
当栈不空的时候:
弹出栈顶节点;
访问该节点;
如果其右子节点不可则入栈其右子节点;
如果其左子节点不空则入栈其左子节点;

中序遍历(先左)
将指针p指向根节点;
当p指向不为null时:
将p指向的节点入栈;
p向左子节点移动;
当p指向null时:
如果栈不空:
弹出栈顶节点并访问;
p指向该节点的右子节点;
如果栈为空
跳出内层循环(由于p指向null,间接地会跳出外层循环,终止遍历)

后续遍历(最后考虑根节点)
将根节点入栈;
指针lastAccess记录上次访问的节点,初始为null
当栈不空时:
瞥一眼栈顶节点;
若该节点是叶子节点或该节点是上次访问节点的父节点(注意上次访问节点为空的情况):
访问该节点;
lastAccess指向该节点;
否则:
将非空的该节点的右子节点入栈;
将非空的该节点的左子节点入栈;

代码实现:

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
class Node<E> {
E element;
Node<E> left;
Node<E> right;

Node(E element) {
this.element = element;
}

@Override
public String toString() {
return "Node{" +
"element=" + element +
'}';
}
}

private static void emptyTreeCheck(Node root) {
if (root == null) {
throw new IllegalArgumentException("empty tree");
}
}

public static void preOrderUnRecur(Node root) {
emptyTreeCheck(root);
Stack<Node> stack = new Stack<>();
StringBuilder stringBuilder = new StringBuilder();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
stringBuilder.append(node.element).append(" ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
System.out.println(stringBuilder.toString());
}

public static void inOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder sb = new StringBuilder();
Stack<Node> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.left;
while (root == null) {
if (stack.isEmpty()) {
break;
} else {
Node node = stack.pop();
sb.append(node.element).append(" ");
root = node.right;
}
}
}
System.out.println(sb.toString());
}

private static boolean oneIsChildOfAnother(Node one, Node another) {
return one != null && (one == another.left || one == another.right);
}

private static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}

private static void postOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder stringBuilder = new StringBuilder();
Stack<Node> stack = new Stack<>();
stack.push(root);
Node lastAccess = null;
while (!stack.isEmpty()) {
Node node = stack.peek();
// 当来到的节点node是叶子节点或上次访问的节点是其子节点时,需要进行访问
if (isLeaf(node) || oneIsChildOfAnother(lastAccess, node)) {
stack.pop();
stringBuilder.append(node.element).append(" ");
lastAccess = node;
} else {
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
System.out.println(stringBuilder.toString());
}

public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.right.left = new Node(9);

// preOrderUnRecur(root);
// inOrderUnRecur(root);
postOrderUnRecur(root);
}
鼓励一下~