《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》（第8章）（樹）

30e8336b8229 發(fā)布于2019-08-26 10:36 / 2002人閱讀

摘要：先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔。方法的實現(xiàn)如下中序遍歷中序遍歷是一種以上行順序訪問所有節(jié)點的遍歷方式，也就是以從最小到最大的順序訪問所有節(jié)點。中序遍歷的一種應(yīng)用就是對樹進(jìn)行排序操作。

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

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

2、代碼主要架構(gòu)：

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

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

3、整體詳細(xì)代碼部分

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    var root = null;    //根節(jié)點  
    /*
    插入節(jié)點：
    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);
            }
        }
    };


    //搜索節(jié)點(搜索一個特定的值)
    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;
   };

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

            //有兩個子節(jié)點（替換為右側(cè)子樹的最小節(jié)點）
            var aux = findMinNode(node.right);   //aux是查找到的最小的子節(jié)點
            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;
    };


    //遍歷節(jié)點
    this.traverse = function(callback) {
        traverse(root, callback);
    };
    var traverse = function(node, callback) {
        if(node == null) return;
        //（后續(xù)遍歷）左右中；（中序遍歷）左中右；（前序遍歷）中左右
        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、遍歷方式 先序遍歷

先序遍歷是以優(yōu)先于后代節(jié)點的順序訪問每個節(jié)點的。先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔。

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

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

中序遍歷

中序遍歷是一種以上行順序訪問BST所有節(jié)點的遍歷方式，也就是以從最小到最大的順序訪問所有節(jié)點。中序遍歷的一種應(yīng)用就是對樹進(jìn)行排序操作。

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

后序遍歷

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

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

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

云服務(wù)器 GPU云服務(wù)器 javascript基礎(chǔ)教程第8版 js數(shù)據(jù)結(jié)構(gòu)與算法第2 js數(shù)據(jù)結(jié)構(gòu)與算法+第2 明解c語言第9章

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/106474.html

發(fā)表評論

登陸后可評論

0條評論

30e8336b8229

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow2.2

閱讀 2999·2023-04-25 21:23
云主機(jī)能干什么-云主機(jī)能做什么？

閱讀 3042·2021-09-22 15:24
css 預(yù)編譯器的再次理解

閱讀 870·2019-08-30 12:55
daily-question-02（前端每日一題02）

閱讀 2104·2019-08-29 18:42
前端每日實戰(zhàn)：112# 視頻演示如何用純 CSS 創(chuàng)作切換背景的按鈕懸停效果

閱讀 2615·2019-08-29 16:27
30分鐘從零開始教會你什么是PWA

閱讀 955·2019-08-26 17:40
Umi.js

閱讀 2189·2019-08-26 13:29
數(shù)據(jù)結(jié)構(gòu)與算法（動態(tài)規(guī)劃與貪婪算法） --javascript語言描述

閱讀 2614·2019-08-26 11:45

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》（第8章）（樹）

相關(guān)文章

**《*學(xué)習(xí)JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法》（第8章）（平衡二叉樹代碼實現(xiàn)）**

ApacheCN 人工智能知識樹 v1.0

**高性能JavaScript（文檔）**

**翻譯連載 | 第 9 章：遞歸（上）－《JavaScript輕量級函數(shù)式編程》 |《你不知道的JS》**

Java學(xué)習(xí)路線總結(jié)，搬磚工逆襲Java架構(gòu)師（全網(wǎng)最強）

發(fā)表評論

0條評論

30e8336b8229

男|高級講師

TA的文章

tensorflow2.2

云主機(jī)能干什么-云主機(jī)能做什么？

css 預(yù)編譯器的再次理解

daily-question-02（前端每日一題02）

前端每日實戰(zhàn)：112# 視頻演示如何用純 CSS 創(chuàng)作切換背景的按鈕懸停效果

30分鐘從零開始教會你什么是PWA

Umi.js

數(shù)據(jù)結(jié)構(gòu)與算法（動態(tài)規(guī)劃與貪婪算法） --javascript語言描述

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》（第8章）（樹）

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！