《學習JavaScript數據結構與算法》（第8章）（樹）

30e8336b8229 發布于2019-08-26 10:36 / 1997人閱讀

摘要：先序遍歷的一種應用是打印一個結構化的文檔。方法的實現如下中序遍歷中序遍歷是一種以上行順序訪問所有節點的遍歷方式，也就是以從最小到最大的順序訪問所有節點。中序遍歷的一種應用就是對樹進行排序操作。

1、二叉搜索樹(兩個條件)：

（1）二叉樹中的節點最多只有兩個子節點：一個是左側節點，另一個是右側子節點；
（2）只允許在左側節點存儲（比父節點）小的值，在右側節點存儲（比父節點）大（或者等于）的值；

2、代碼主要架構：

主要包括有插入（insert）、搜索（search）、移除（removce）、遍歷（traverse）等功能

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;  //左節點
        this.right = null; //右節點
    }
    var root = null;    //根節點  
    /*
    插入節點：
    1、樹為空
    2、樹不為空 -> 比較（小于 -> 往左走；大于 -> 往右走）
    */ 
    this.insert = function(value) {};
    //搜索節點(搜索一個特定的值)
    this.search = function(value) {};
    //尋找樹的最小鍵的方法
    this.min = function() {};
    //尋找樹的最大鍵的方法
    this.max = function() {};
    /*
    移除節點：
    1、最簡單的情況：移除葉節點
    2、移除只有一個子節點的節點
    3、移除有兩個子節點的節點(替換為右側子樹的最小節點)
    */
    this.remove =function(value) {
    };
    //遍歷節點
    this.traverse = function(callback) {};
    
    //顯示樹
    this.getRoot = function() {};
}

3、整體詳細代碼部分

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    var root = null;    //根節點  
    /*
    插入節點：
    1、樹為空
    2、樹不為空 -> 比較（小于 -> 往左走；大于 -> 往右走）
    */ 
    this.insert = function(value) {
        var newNode = new Node(value);
        if(root == null) { //空樹          
            root = newNode;
        }else{//樹非空           
            insertNode(root, newNode);
        }
    };
    var insertNode = function(node, newNode) {
        if(newNode.value > node.value) {
            //往右走
            if(node.right == null) {
                node.right = newNode;
            }else{
                insertNode(node.right, newNode);
            }   
        }else if(newNode.value < node.value) {
            //往左走
            if(node.left == null) {
                node.left = newNode;
            }else{
                insertNode(node.left, newNode);
            }
        }
    };


    //搜索節點(搜索一個特定的值)
    this.search = function(value) {
        return searchNode(root, value);
    };
    var searchNode = function(node, value) {
        if(node === null) {
            return false;
        }
        if(value < node.value) {
            return searchNode(node.left, value);
        }else if(value > node.value) {
            return searchNode(node.right, value);
        }else{
            return true;
        }
    };
   //尋找樹的最小鍵的方法
   this.min = function() {
       return minNode(root);
   };
   var minNode = function(node) {
       if(node) {
           while(node && node.left !== null) {
               node = node.left;
           }
           return node.value;
       }
       return null;
   };
   //尋找樹的最大鍵的方法
   this.max = function() {
       return maxNode(root);
   };
   var maxNode = function(node) {
       if(node) {
           while(node && node.right !== null) {
               node = node.right;
           }
           return node.value;
       }
       return null;
   };

    /*
    移除節點：
    1、最簡單的情況：移除葉節點
    2、移除只有一個子節點的節點
    3、移除有兩個子節點的節點(替換為右側子樹的最小節點)
    */
    this.remove =function(value) {
        root = removeNode(root, value);
    };
    var removeNode = function(node,value) {
        if( node == null) return null;
        if(node.value < value) {
            //繼續向右查找
            node.right = removeNode(node.right , value);
            return node;
        }else if(node.value > value) {
            //向左查找
            node.left = removeNode(node.left, value);
            return node;
        }else{
            //value == node.value
            //執行刪除過程
            //葉節點條件
            if(node.left == null && node.right == null) {
                node = null;
                return node;
            }
            //只有一個子節點條件
            if(node.left == null && node.right) {
                node = node.right;
                return node;     
            }else if(node.right == null && node.left){
                node = node.left;
                return node;
            }

            //有兩個子節點（替換為右側子樹的最小節點）
            var aux = findMinNode(node.right);   //aux是查找到的最小的子節點
            node.value = aux.value;
            node.right = removeNode(node.right, aux.value);
            return node;
        }
    };
    var findMinNode = function(node) {
        if(node == null) return null;
        while(node && node.left) {
            node = node.left;
        }
        return node;
    };


    //遍歷節點
    this.traverse = function(callback) {
        traverse(root, callback);
    };
    var traverse = function(node, callback) {
        if(node == null) return;
        //（后續遍歷）左右中；（中序遍歷）左中右；（前序遍歷）中左右
        traverse(node.left, callback);
        traverse(node.right, callback);
        callback(node.value);
    };
    
    //顯示樹
    this.getRoot = function() {
        return root;
    };
}

4、代碼功能驗證測試

var t = new Tree;
var print = function(value) {
    console.log("value -",value)   
};

t.insert(11);
t.insert(8);
t.insert(4);
t.insert(9);
t.insert(3);
t.insert(5);

t.insert(9);
t.insert(12);

t.search(9); //true
t.remove(8);
t.min(); //3
t.max(); //12
t.traverse(print);

5、遍歷方式 先序遍歷

先序遍歷是以優先于后代節點的順序訪問每個節點的。先序遍歷的一種應用是打印一個結構化的文檔。

11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

this.preOrderTraverse = function(callback){
    preOrderTraverseNode(root, callback);
};
preOrderTraverseNode方法的實現如下：
var preOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        callback(node.key); //{1}
        preOrderTraverseNode(node.left, callback); //{2}
        preOrderTraverseNode(node.right, callback); //{3}
    }
};

中序遍歷

中序遍歷是一種以上行順序訪問BST所有節點的遍歷方式，也就是以從最小到最大的順序訪問所有節點。中序遍歷的一種應用就是對樹進行排序操作。

3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

this.inOrderTraverse = function(callback){
    inOrderTraverseNode(root, callback); //{1}
};
var inOrderTraverseNode = function (node, callback) {
    if (node !== null) { //{2}
    inOrderTraverseNode(node.left, callback); //{3}
    callback(node.key); //{4}
    inOrderTraverseNode(node.right, callback); //{5}
    }
};

后序遍歷

后序遍歷則是先訪問節點的后代節點，再訪問節點本身。后序遍歷的一種應用是計算一個目錄和它的子目錄中所有文件所占空間的大小。

3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback);
};
postOrderTraverseNode方法的實現如下：
var postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        postOrderTraverseNode(node.left, callback); //{1}
        postOrderTraverseNode(node.right, callback); //{2}
        callback(node.key); //{3}
    }
};

GPU云服務器云服務器 javascript基礎教程第8版 js數據結構與算法第2 js數據結構與算法+第2 明解c語言第9章

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/106474.html

《學習JavaScript數據結構與算法》（第8章）（平衡二叉樹代碼實現）

摘要：平衡二叉樹代碼實現根節點插入節點樹為空樹不為空比較小于往左走大于往右走空樹樹非空自平衡樹插入新節點向左走向左子樹拆入新節點，且節點的值小于其左子節點時，應該進行旋轉。平衡二叉樹JS代碼實現 var Tree = function() { var Node = function(value) { this.value = value; this....

isLishude 2019-08-26 10:37 評論0 收藏0
ApacheCN 人工智能知識樹 v1.0

摘要：貢獻者飛龍版本最近總是有人問我，把這些資料看完一遍要用多長時間，如果你一本書一本書看的話，的確要用很長時間。為了方便大家，我就把每本書的章節拆開，再按照知識點合并，手動整理了這個知識樹。 Special Sponsors showImg(https://segmentfault.com/img/remote/1460000018907426?w=1760&h=200); 貢獻者：飛龍版...

劉厚水 2019-06-26 19:00 評論0 收藏0
高性能JavaScript（文檔）

摘要：最近在全力整理高性能的文檔，并重新學習一遍，放在這里方便大家查看并找到自己需要的知識點。最近在全力整理《高性能JavaScript》的文檔，并重新學習一遍，放在這里方便大家查看并找到自己需要的知識點。前端開發文檔高性能JavaScript 第1章：加載和執行腳本位置阻止腳本無阻塞的腳本延遲的腳本動態腳本元素 XMLHTTPRequest腳本注入推薦的無阻塞模式...

RayKr 2019-08-22 18:32 評論0 收藏0
翻譯連載 | 第 9 章：遞歸（上）－《JavaScript輕量級函數式編程》 |《你不知道的JS》

摘要：一旦我們滿足了基本條件值為，我們將不再調用遞歸函數，只是有效地執行了。遞歸深諳函數式編程之精髓，最被廣泛引證的原因是，在調用棧中，遞歸把大部分顯式狀態跟蹤換為了隱式狀態。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者關于譯者：這是一個流淌著滬江血液的純粹工程：認真，是 HTML 最堅實的梁柱；...

MasonEast 2019-08-22 11:11 評論0 收藏0
Java學習路線總結，搬磚工逆襲Java架構師（全網最強）

摘要：哪吒社區技能樹打卡打卡貼函數式接口簡介領域優質創作者哪吒公眾號作者架構師奮斗者掃描主頁左側二維碼，加入群聊，一起學習一起進步歡迎點贊收藏留言前情提要無意間聽到領導們的談話，現在公司的現狀是碼農太多，但能獨立帶隊的人太少，簡而言之，不缺干 ? 哪吒社區Java技能樹打卡?【打卡貼 day2...

Scorpion 2021-11-18 10:02 評論0 收藏0