二叉树

基本定义简单如下:

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

先序遍历

首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回。

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

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

遍历的实现

  • 递归实现
  • 简单迭代实现
  • 优化迭代实现

基础 Tree 定义

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
public class Tree {
private Tree left;
private Tree right;
private String data;

public Tree(Tree left, Tree right, String data) {
super();
this.left = left;
this.right = right;
this.data = data;
}

public Tree getLeft() {
return left;
}

public void setLeft(Tree left) {
this.left = left;
}

public Tree getRight() {
return right;
}

public void setRight(Tree right) {
this.right = right;
}

public String getData() {
return data;
}

public void setData(String data) {
this.data = data;
}

}

递归实现

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
public class PreTraverse1 {
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;
}
//如果当前传入的节点是null,那么不进行处理
//第一步:先访问根节点,这里以输出代替
//第二步:递归访问左子树
//第三步:递归访问右子树
System.out.print(root.getData() + " ");
traverse(root.getLeft());
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

import java.util.Stack;

public class PreTraverse2 {
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<>();
stack.push(root);
//利用了栈的先进后出的特性,先把root入栈
while (!stack.isEmpty()) {//循环判断栈不是空
Tree popTree = stack.pop();//把栈顶的元素弹出
System.out.print(popTree.getData() + " ");//1. 访问元素
if (popTree.getRight() != null) {
stack.push(popTree.getRight());//2. 如果右节点不为空,push 到栈中,因为是先进后出,所以先 push 右节点
}
if (popTree.getLeft() != null) {
stack.push(popTree.getLeft());//3. push 左节点
}
}
}
}

优化迭代实现

如下图所示:

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 PreTraverse {

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);
}

public static void traverse(Tree root) {
Stack<Tree> stack = new Stack<>();
while (true) {
visitAlongLeftBranch(root, stack);
if (stack.isEmpty()) {
break;
}
//当最左节点已经访问完,弹出栈顶元素(也就是距离当前最近的右子树),然后循环这个过程,直到栈是空退出
root = stack.pop();
}
}

//遍历的过程可看成如下:
//先访问当前根节点
//然后把右节点 push 到栈
//在循环当前节点的左节点
private static void visitAlongLeftBranch(Tree root, Stack<Tree> stack) {
while (root != null) {
System.out.print(root.getData() + " ");
stack.push(root.getRight());
root = root.getLeft();
}
}
}

—EOF—