二叉树的遍历(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");
    }
}