[聚合文章] 基礎資料結構 6 --- 樹狀結構的遍歷 Traversal ( Iteration )

  1. 首页
  2. 聚合文章
  3. 文章详情
JavaScript 2017-11-26 17 阅读
原文链接: http://marklin-blog.logdown.com/posts/3865233-the-traversing-traversal-of-the-basic-data-structure-6-tree-structure-according

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

  • 中序追蹤 (in-order) : 先走訪左子樹，然後在根，最後在右子樹。(DBEAFCG)
  • 前序追蹤 (pre-order) : 先走訪根，然後在左子樹，最後在右子樹。(ABDECFG)
  • 後序追蹤 (post-order) : 先走訪左子樹，然後在右子樹，最後是根。(DEBFGCA)

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

因為我們之前實作的方法是用『 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 isEnd = false;
    let current = this.root;
    while (!isEnd) {
        if(current != null){
            stack.push(current);
            current = current.left;
        }
        else{
            if(stack.length > 0){
                current = stack.pop();
                console.log(current.data);
                current = current.right;
            }else{
                isEnd = true;
            }
        }
    }
}

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

參考資料

注：本文内容来自互联网，旨在为开发者提供分享、交流的平台。如有涉及文章版权等事宜，请你联系站长进行处理。