二叉树的遍历(java实现)

这里先总结一下二叉树的遍历算法,包括层次遍历、前序遍历、中序遍历和后序遍历。

完整代码(包括测试用例): (https://github.com/FergusChen/AlgoCode) 包路径:main.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
38
39
40
41
42
43
44
45
46
47
/**
* 按层次打印二叉树
* 按层次遍历二叉树,其思想就是利用队列的先进先出的特点,逐个将左右结点放入队列中
*/
public static void levelOrder(BTNode root) {
if (root == null) {
System.out.println("null");
return;
}
Queue<BTNode> treeQueue = new LinkedList<BTNode>();
treeQueue.offer(root); //先将根结点放入队列。
while (!treeQueue.isEmpty()) {
BTNode node = treeQueue.poll(); //将队列中已有的结点出队列。
System.out.print(node.data + "\t");
//出队列的同时扫描该结点的左右孩子,并逐个放入到队列中。
if (node.left != null) {
treeQueue.offer(node.left);
}
if (node.right != null) {
treeQueue.offer(node.right);
}
}
System.out.println();
}
```
#### 前序遍历
##### 递归实现
前序遍历的递归算法非常简单,思路也很清晰。就是按照前序遍历的“根->左->右”来进行遍历。递归到左结点之前先处理(打印)根节点。
前序遍历递归实现:
```java
/**
* 前序遍历二叉树(递归实现)
* 思路:根据前序遍历的特点:根结点->左子树->右子树,用递归实现
* test:(null),(单结点),(默认二叉树)
* @param root 二叉树的根结点
*/
public static void preOrder(BTNode root) {
if (root != null) {
System.out.print(root.data + "\t");
preOrder(root.left);
preOrder(root.right);
}
}
非递归实现

前序遍历的非递归算法是用栈来辅助实现“根->左->右”的遍历。先处理(打印)再入栈,在出栈的时候处理该结点的右子树。
前序遍历的非递归实现:

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
/**
* 前序遍历二叉树(非递归实现)
* 思路:利用栈从根结点,一直将左子树入栈,直到左子树为null,
* 然后逐个将结点出栈,同时遍历该结点的右子树,
* 遍历右子树为根的子树时,用同样的方法从根节点,一直将左子树入栈。
* test:(null),(单结点),(默认二叉树)
*
* @param root 二叉树的根节点
*/
public static void preOrder_nonRec(BTNode root) {
if (root == null) {
System.out.println("empty tree");
return;
}
Stack<BTNode> treeStack = new Stack<BTNode>();
BTNode node = root;
while (node != null || treeStack.size() > 0) {
while (node != null) {
System.out.print(node.data + "\t");
treeStack.push(node);
node = node.left;
}
node = treeStack.pop();
node = node.right;
}
}

中序遍历

递归实现

明白前序遍历之后,中序遍历和后序遍历就顺理成章了。中序遍历是实现“左->根->右”的遍历。
中序遍历递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 中序遍历二叉树(递归遍历)
* 思路:根据中序遍历的特点:左子树->根结点->右子树 递归遍历
* test:(null),(单结点),(默认二叉树)
*
* @param root 二叉树的根结点
*/
public static void midOrder(BTNode root) {
if (root != null) {
midOrder(root.left);
System.out.print(root.data + "\t");
midOrder(root.right);
}
}

非递归实现

中序遍历非递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 中序遍历二叉树(非递归遍历)
* 思路:与非递归前序遍历类似。只是访问结点是时机不同
* test:(null),(单结点),(默认二叉树)
*
* @param root 二叉树的根结点
*/
public static void midOrder_nonRec(BTNode root) {
if (root == null) {
System.out.println("empty tree");
return;
}
Stack<BTNode> treeStack = new Stack<BTNode>();
BTNode node = root;
while (node != null || treeStack.size() > 0) {
while (node != null) {
treeStack.push(node);
node = node.left;
}
node = treeStack.pop();
System.out.print(node.data + "\t");
node = node.right;
}
}

后序遍历

递归实现

实现后序遍历的“左->右->中”,递归实现也是处理时机的问题。
后序遍历递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 后续遍历二叉树
* 思路:根据后序遍历的特点:左子树->右子树->根结点 递归遍历
* test:(null),(单结点),(默认二叉树)
*
* @param root 二叉树的根结点
*/
public static void postOrder(BTNode root) {
if (root != null) {
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + "\t");
}
}