9 months ago

在筆者的『基礎資料結構 3 --- 樹狀結構與二元樹』的這篇文章中,我們介紹了樹的基本概念,也學習了如何遍歷樹的方法,在之前的文章中,我們有說到,如果要遍歷樹大至上有以下三種方法 :

  • 中序追蹤 (in-order) : 先走訪左子樹,然後在根,最後在右子樹。(DBEAFCG)
  • 前序追蹤 (pre-order) : 先走訪根,然後在左子樹,最後在右子樹。(ABDECFG)
  • 後序追蹤 (post-order) : 先走訪左子樹,然後在右子樹,最後是根。(DEBFGCA)
  • level-order : 先走訪第一層節點,再走訪第二層,最後會走到最後一層。(ABCDEFG)

補充: 這裡我們在補充第四種追蹤level-order,事實上它就是BFS,也就是一層一層的掃

那為什麼我們這裡要在拿來說一次呢 ?

因為我們之前實作的方法是用『 Recursion 』來實作。

有寫過程式的人大概會知道,在使用recursion實作程式碼,常常有可能會發生memory leak事件,所以我們這篇將要來說明,如何不使用它,來實作以上三種 traversal。

中序追蹤 (in-order)

左 => 根 => 右

iteration

  1. 直接先深入最深的左子樹,並將行經的節點,存放到 stack 中。
  2. 然後深入到最後時,發現是 null ,開始從 stack 中 pop 東西出來。
  3. 接下來在從 pop 出的節點的右子樹開始重複第一個步驟。
/**
 * Tree inordrTraversal (no recursive)
 * Tip: 左根右
 */
BinarySearchTree.prototype.inorderTraversal = function(){
    let stack = [];
    let current = this.root;

    while (current !== null || stack.length !== 0) {
        while(current != null){
          stack.push(current);
          current = current.left;
        }
        current = stack.pop();
        console.log(current.val);
        current = current.right;
    }
}

recursion

BinaryTree.prototype.inOrderTraverse = function(callback) {

    inOrderTraverseNode(this.root,callback);

    function inOrderTraverseNode(node,callback) {
        if(node !== null){
            inOrderTraverseNode(node.left,callback);
            callback(node.data);
            inOrderTraverseNode(node.right,callback);
        }
    }   
};

前序追蹤 (pre-order)

根 => 左 => 右

iteration

  1. 先將 root 存放到 stack 中。
  2. 然後因為pre-order 是先根在子樹,所以直接從 stack pop 出節點輸出。
  3. 接下來在將左右子樹放入 stack。
  4. 重複第二個步驟。
/**
 * Tree preorderTraversal (no recursive)
 * Tip: 根左右
 */
BinarySearchTree.prototype.preorderTraversal = function(){
    let stack = [];
    stack.push(this.root);
    let current;
    while (stack.length > 0) {
        current = stack.pop();
        console.log(current.data);

        if(current.right){
            stack.push(current.right);
        }

        if(current.left){
            stack.push(current.left);
        }
    }
}

recursion

BinaryTree.prototype.preOrderTraverse = function(callback) {

    preOrderTraverseNode(this.root,callback);

    function preOrderTraverseNode(node,callback) {
        if(node !== null){
            callback(node.data);
            preOrderTraverseNode(node.left,callback);
            preOrderTraverseNode(node.right,callback);
        }
    }   
};

後序追蹤 (post-order)

左 => 右 => 根

iteration

  1. 將第一個節點丟到 stack 中。
  2. 然後在進行 while
  3. pop 出節點,然後丟到 temp 陣列中。
  4. 在將該節點的左右子樹丟到 stack 中。
  5. 重複 while
  6. 最後在將 temp 陣列中的節點取出。
/**
 * Tree postOrder Traversal (no recursive)
 * Tip: 左右根
 */
BinarySearchTree.prototype.postOrderTraversal = function() {
    let stack = [];
    let temp = [];
    let current = this.root;
    let isEnd = false;

    stack.push(current);
    while(stack.length > 0){
        current = stack.pop();
        temp.push(current);

        if(current.left != null){
            stack.push(current.left);
        }
        if(current.right != null){
            stack.push(current.right);
        }
    }

    while(temp.length > 0){
        current = temp.pop();
        console.log(current.data);
    }

}

recursion

BinaryTree.prototype.postOrderTraverse = function(callback) {

    postOrderTraverseNode(this.root,callback);

    function postOrderTraverseNode(node,callback) {
        if(node !== null){
            postOrderTraverseNode(node.left,callback);
            postOrderTraverseNode(node.right,callback);
            callback(node.data);
        }
    }   
};

層級追蹤 (level-order BFS)

就是所謂的 BFS 廣度優先搜尋,也就是一層一層找。

  1. 將第一個 root 丟入 queue 中 ( queue 是先進先出 )。
  2. 從 queue 中取出節點。
  3. 然後再將左右子樹丟進去 queue 中。
  4. 然後就重複 2 的動作。

下面的程式碼中多了一些記 level 的東西,那是因為我希望的輸出結果會像下面這樣,所以才有下面的其它步驟。

  1
 2  3
 
[[1],[2,3]]

iteration

BinarySearchTree.prototype.bfsTraversal = function() {
    let current;
    let queue = [];
    let result = [];
    if(!this.root){
        return [];
    }
    
    queue.push({
        node: this.root,
        level: 0
    });
    
    while (queue.length > 0){
        current = queue.shift();

        if(result[current.level]){
            result[current.level].push(current.node.data);
        }else{
            result[current.level] = [];
            result[current.level].push(current.node.data);
        }
        
        if(current.node.left != null){
            queue.push({
                node: current.node.left,
                level: current.level + 1
            });
        }
        
        if(current.node.right != null){
            queue.push({
                node: current.node.right,
                level: current.level + 1
            })
        }
    }
    return result;
}

let tree = new BinarySearchTree();
tree.add(new Node(1));
tree.add(new Node(2));
tree.add(new Node(3));
tree.add(new Node(4));
tree.add(new Node(5));
tree.add(new Node(6));
tree.add(new Node(7));

//輸出: [ [ 1 ], [ 2, 3 ], [ 4, 5, 6, 7 ] ]

參考資料

← Socket.io 要建立連線時會如何跑呢 ?? 為什麼伊斯蘭教會分裂呢 ? →
 
comments powered by Disqus