天天看點

二叉樹(連結清單實作)--前序、中序、後序、層序周遊二叉樹(連結清單實作)–前序、中序、後序、層序周遊

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

二叉樹(連結清單實作)--前序、中序、後序、層序周遊二叉樹(連結清單實作)–前序、中序、後序、層序周遊

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

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

繼續閱讀