二叉樹（連結清單實作）–前序、中序、後序、層序周遊

​ 我們把樹簡單的畫作上圖中的樣子，由一個根節點、一個左子樹、一個右子樹組成，那麼按照根節點什麼時候被通路，我們可以把二叉樹的周遊分為以下三種方式：

1.前序周遊；

​ 先通路根結點，然後再通路左子樹，最後通路右子樹

2.中序周遊；

​ 先通路左子樹，中間通路根節點，最後通路右子樹

3.後序周遊；

​ 先通路左子樹，再通路右子樹，最後通路根節點

如果我們分别對下面的樹使用三種周遊方式進行周遊，得到的結果如下：

前序周遊

public Queue<Key> preErgodic()：使用前序周遊，擷取整個樹中的所有鍵

private void preErgodic(Node x,Queue<Key> keys)：使用前序周遊，把指定樹x中的所有鍵放入到keys隊列中

實作過程中，我們通過前序周遊，把,把每個結點的鍵取出，放入到隊列中傳回即可。

實作步驟：

1.把目前結點的key放入到隊列中;

2.找到目前結點的左子樹，如果不為空，遞歸周遊左子樹

3.找到目前結點的右子樹，如果不為空，遞歸周遊右子樹

代碼：

// 使用前序周遊(根->左->右)，擷取整個樹中的所有鍵
public Queue<Key> preErgodic() {
    Queue<Key> keys = new Queue<>();
    preErgodic(root, keys);
    return keys;
}
// 使用前序周遊(根->左->右)，把指定樹x中的所有鍵放入到keys隊
private void preErgodic(Node x, Queue
    // 如果x結點為空，結束周遊
    if (x == null) {
        return;
    }
    // 如果x結點不為空，進行前序周遊(根->左->右)
    // 将x結點的key值存入隊列中
    keys.enqueue(x.key);
    // 遞歸調用前序周遊，儲存左子樹
    if (x.left != null) {
        preErgodic(x.left, keys);
    }
    // 遞歸調用前序周遊，儲存右子樹
    if (x.right != null) {
        preErgodic(x.right, keys);
    }
}
           

中序周遊

public Queue midErgodic()：使用中序周遊，擷取整個樹中的所有鍵

private void midErgodic(Node x,Queue keys)：使用中序周遊，把指定樹x中的所有鍵放入到keys隊列中

實作步驟：

1.找到目前結點的左子樹，如果不為空，遞歸周遊左子樹

2.把目前結點的key放入到隊列中;

3.找到目前結點的右子樹，如果不為空，遞歸周遊右子樹

代碼：

// 使用中序周遊(左->根->右)，擷取整個樹中的所有鍵
public Queue<Key> midErgodic() {
    Queue<Key> keys = new Queue<>();
    midErgodic(root, keys);
    return keys;
}
// 使用中序周遊(左->根->右)，把指定樹x中的所有鍵放入到keys隊列中
private void midErgodic(Node x, Queue<Key> keys) {
    // 如果x結點為null，結束周遊
    if (x == null) {
        return;
    }
    // 如果x結點為空，進行中序周遊(左->根->右)
    // 遞歸周遊左子樹，将key存入隊列中
    if (x.left != null) {
        midErgodic(x.left, keys);
    }
    // 将x結點的key值存入隊列中
    keys.enqueue(x.key);
    // 遞歸周遊右子樹，将key存入隊列中
    if (x.right != null) {
        midErgodic(x.right, keys);
    }
}
           

後序周遊

public Queue<Key> afterErgodic()：使用後序周遊，擷取整個樹中的所有鍵

private void afterErgodic(Node x,Queue<Key> keys)：使用後序周遊，把指定樹x中的所有鍵放入到keys隊列中

實作步驟：

1.找到目前結點的左子樹，如果不為空，遞歸周遊左子樹

2.找到目前結點的右子樹，如果不為空，遞歸周遊右子樹

3.把目前結點的key放入到隊列中;

代碼：

// 使用後序周遊(左->右->根)，擷取整個樹中的所有鍵
public Queue<Key> afterErgodic() {
    Queue<Key> keys = new Queue<>();
    afterErgodic(root, keys);
    return keys;
}
// 使用後序周遊(左->右->根)，把指定樹x中的所有鍵放入到keys隊列中
private void afterErgodic(Node x, Queue<Key> keys) {
    // 如果x結點為null，結束周遊
    if (x == null) {
        return;
    }
    // 如果x結點為空，進行中序周遊(左->右->根)
    // 遞歸周遊左子樹，将key存入隊列中
    if (x.left != null) {
        afterErgodic(x.left, keys);
    }
    // 遞歸周遊右子樹，将key存入隊列中
    if (x.right != null) {
        afterErgodic(x.right, keys);
    }
    // 将x結點的key值存入隊列中
    keys.enqueue(x.key);
}
           

層序周遊

​ 所謂的層序周遊，就是從根節點（第一層）開始，依次向下，擷取每一層所有結點的值，有二叉樹如下：

那麼層序周遊的結果是：EBGADFHC

public Queue<Key> layerErgodic()：使用層序周遊，擷取整個樹中的所有鍵

實作步驟：

1.建立隊列，存儲每一層的結點；

2.使用循環從隊列中彈出一個結點：

2.1擷取目前結點的key；

2.2如果目前結點的左子結點不為空，則把左子結點放入到隊列中

2.3如果目前結點的右子結點不為空，則把右子結點放入到隊列中

代碼：

// 使用層序周遊，擷取整個樹中的所有鍵
public Queue<Key> layerErgodic() {
    // 存放層序周遊的結果key
    Queue<Key> keys = new Queue<>();
    // 存放按照層序周遊的要求，周遊的所有的結點
    Queue<Node> nodes = new Queue<>();
    if (root == null) { // 判斷樹是否為空，不為空，将根結點存入nodes隊列中
        return null;
    }
    nodes.enqueue(root);
    // 循環隊列，完成層序周遊
    while (!nodes.isEmpty()) {
        // 從隊列中取出一個結點，并将key存入keys隊列中
        Node currNode = nodes.dequeue();
        keys.enqueue(currNode.key);
        // 如果目前結點的左結點不為空，将左結點存入nodes隊列
        if (currNode.left != null) {
            nodes.enqueue(currNode.left);
        }
        // 如果目前結點的右結點不為空，将左結點存入nodes隊列
        if (currNode.right != null) {
            nodes.enqueue(currNode.right);
        }
    }
    return keys;
}