中序遍历

中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。

1
2
3
4
5
            R
/ \
A B
/ \ / \
C D E F

上面这个树的中序遍历顺序是: C A D R E B F

遍历的实现

  • 递归实现
  • 迭代实现

递归实现

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 class InTraverse {
public static Tree init() {
Tree E = new Tree(null, null, "E");
Tree F = new Tree(null, null, "F");
Tree C = new Tree(null, null, "C");
Tree D = new Tree(null, null, "D");
Tree A = new Tree(C, D, "A");
Tree B = new Tree(E, F, "B");

Tree root = new Tree(A, B, "R");

return root;
}

public static void main(String[] args) {
Tree root = init();
traverse(root);
}

private static void traverse(Tree root) {
if(root == null) {
return;
}
//先访问左子树,然后访问根节点,其次访问右子树
traverse(root.getLeft());
System.out.print(root.getData() + " ");
traverse(root.getRight());
}
}

迭代实现

如下图所示:

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

import java.util.Stack;

public class InTraverse1 {
public static Tree init() {
Tree E = new Tree(null, null, "E");
Tree F = new Tree(null, null, "F");
Tree C = new Tree(null, null, "C");
Tree D = new Tree(null, null, "D");
Tree A = new Tree(C, D, "A");
Tree B = new Tree(E, F, "B");

Tree root = new Tree(A, B, "R");

return root;
}

public static void main(String[] args) {
Tree root = init();
traverse(root);
}

private static void traverse(Tree root) {
Stack<Tree> stack = new Stack<>();

while (true) {
findLeft(root, stack);
if (stack.isEmpty()) {
break;
}
Tree popTree = stack.pop();
//访问栈顶的节点,也就是最左的节点
System.out.print(popTree.getData() + " ");
//然后循环遍历右子树
root = popTree.getRight();
}

}
//沿着当前节点,把所有的左节点push到栈中
private static void findLeft(Tree root, Stack<Tree> stack) {
while (root != null) {
stack.push(root);
root = root.getLeft();
}
}
}

—EOF—