Javascript實現(xiàn)二叉樹算法

最近正在看慕課網(wǎng)的《Javascript實現(xiàn)二叉樹算法》課程，現(xiàn)把看到的東西記錄下來阱表。
什么是二叉樹殿如？簡單來說，二叉樹是一種具有層級特性的數(shù)據(jù)結(jié)構(gòu)捶枢，一棵樹包含多個節(jié)點握截。節(jié)點自身含有一個屬性，就是他所代表的數(shù)值烂叔。
排序二叉樹具有以下特征：
1谨胞、如果他的左子樹上不為空，則他的左子樹上所有節(jié)點的值都小于根節(jié)點上的值蒜鸡；
2胯努、如果他的右子樹上不為空，則他的右子樹上所有節(jié)點的值都小于根節(jié)點上的值逢防；
3叶沛、他的左、右子樹也是二叉排序樹忘朝；
4灰署、沒有完全相等的兩個節(jié)點；

二叉樹

二叉排序樹的代碼實現(xiàn)

<script>
var BinaryTree = function(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var rootNode = null;

    var insertNode = function(node , newNode){
        if( newNode.key < node.key ){
            if( node.left == null ){
                node.left = newNode
            }else{
                insertNode(node.left , newNode)
            }
        }else{
            if( node.right == null ){
                node.right = newNode;
            }else{
                insertNode(node.right , newNode)
            }
        }
    }

    this.insert = function(key){
        var newNode = new Node(key);
        if( rootNode == null ){
            rootNode = newNode;
        }else{
            insertNode(rootNode , newNode);
        }
    }
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
    binaryTree.insert(key)
})
</script>

二叉樹的中序遍歷

從根節(jié)點開始局嘁，如果存在左子樹就開始遍歷左子樹溉箕，然后再遍歷右子樹，最后輸出根節(jié)點的值悦昵。遍歷左肴茄、右子樹時也是先遍歷左子樹，然后遍歷右子樹但指，最少輸出改接點寡痰，如此循環(huán)。

代碼實現(xiàn)：

<script>
var BinaryTree = function(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var rootNode = null;

    var insertNode = function(node , newNode){
        if( newNode.key < node.key ){
            if( node.left == null ){
                node.left = newNode
            }else{
                insertNode(node.left , newNode)
            }
        }else{
            if( node.right == null ){
                node.right = newNode;
            }else{
                insertNode(node.right , newNode)
            }
        }
    }

    this.insert = function(key){
        var newNode = new Node(key);
        if( rootNode == null ){
            rootNode = newNode;
        }else{
            insertNode(rootNode , newNode);
        }
    }

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

    this.inOrderTraverse = function(callback){
        inOrderTraverseNode(rootNode , callback)
    }
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
    binaryTree.insert(key)
})
var callback = function(key){
    console.log(key)
}
console.log("中序遍歷")
// 中序遍歷
binaryTree.inOrderTraverse(callback);
</script>

打印出來的結(jié)果

中序遍歷

二叉樹的前序遍歷

從根節(jié)點開始棋凳，先輸出當(dāng)前節(jié)點拦坠，如果存在左子樹就開始遍歷左子樹，然后再遍歷右子樹剩岳。遍歷左贪婉、右子樹的規(guī)則同上。

代碼實現(xiàn)：

<script>
var BinaryTree = function(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var rootNode = null;

    var insertNode = function(node , newNode){
        if( newNode.key < node.key ){
            if( node.left == null ){
                node.left = newNode
            }else{
                insertNode(node.left , newNode)
            }
        }else{
            if( node.right == null ){
                node.right = newNode;
            }else{
                insertNode(node.right , newNode)
            }
        }
    }

    this.insert = function(key){
        var newNode = new Node(key);
        if( rootNode == null ){
            rootNode = newNode;
        }else{
            insertNode(rootNode , newNode);
        }
    }

    var preOrderTraverseNode = function(node , callback){
        if( node !== null ){
            callback(node.key);
            preOrderTraverseNode(node.left , callback);
            preOrderTraverseNode(node.right , callback);
        }
    }
    this.preOrderTraverse = function(callback){
        preOrderTraverseNode(rootNode , callback);
    }   
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
    binaryTree.insert(key)
})
var callback = function(key){
    console.log(key)
}
console.log("前序遍歷")
// 前序遍歷
binaryTree.preOrderTraverse(callback)
</script>

打印出來的結(jié)果

前序遍歷

二叉樹的后序遍歷

代碼實現(xiàn)：

<script>
var BinaryTree = function(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var rootNode = null;

    var insertNode = function(node , newNode){
        if( newNode.key < node.key ){
            if( node.left == null ){
                node.left = newNode
            }else{
                insertNode(node.left , newNode)
            }
        }else{
            if( node.right == null ){
                node.right = newNode;
            }else{
                insertNode(node.right , newNode)
            }
        }
    }

    this.insert = function(key){
        var newNode = new Node(key);
        if( rootNode == null ){
            rootNode = newNode;
        }else{
            insertNode(rootNode , newNode);
        }
    }

    var nextOrderTraverseNode = function(node , callback){
        if( node !== null ){
            nextOrderTraverseNode(node.left , callback);
            nextOrderTraverseNode(node.right , callback);
            callback(node.key);
        }
    }
    this.nextOrderTraverse = function(callback){
        nextOrderTraverseNode(rootNode , callback);
    }   
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
    binaryTree.insert(key)
})
var callback = function(key){
    console.log(key)
}
console.log("后序遍歷")
// 后序遍歷
binaryTree.nextOrderTraverse(callback)
</script>

打印結(jié)果

后序遍歷

查找最小值

<script>
var BinaryTree = function(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var rootNode = null;

    var insertNode = function(node , newNode){
        if( newNode.key < node.key ){
            if( node.left == null ){
                node.left = newNode
            }else{
                insertNode(node.left , newNode)
            }
        }else{
            if( node.right == null ){
                node.right = newNode;
            }else{
                insertNode(node.right , newNode)
            }
        }
    }

    this.insert = function(key){
        var newNode = new Node(key);
        if( rootNode == null ){
            rootNode = newNode;
        }else{
            insertNode(rootNode , newNode);
        }
    }

    var minNode = function(node){
        if(node){
            while(node && node.left !== null){
                node = node.left;
            }
            return node.key;
        }
        return null;
    }
    this.min = function(){
        return minNode(rootNode);
    }   
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
    binaryTree.insert(key)
})
console.log("查找最小值")
// 查找最小值
console.log(binaryTree.min())
</script>

查找最大值

<script>
var BinaryTree = function(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var rootNode = null;

    var insertNode = function(node , newNode){
        if( newNode.key < node.key ){
            if( node.left == null ){
                node.left = newNode
            }else{
                insertNode(node.left , newNode)
            }
        }else{
            if( node.right == null ){
                node.right = newNode;
            }else{
                insertNode(node.right , newNode)
            }
        }
    }

    this.insert = function(key){
        var newNode = new Node(key);
        if( rootNode == null ){
            rootNode = newNode;
        }else{
            insertNode(rootNode , newNode);
        }
    }

    var maxNode = function(node){
        if( node ){
            while(node && node.right !== null){
                node = node.right
            }
            return node.key
        }
        return null;
    }
    this.max = function(){
        return maxNode(rootNode);
    }   
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
    binaryTree.insert(key)
})
console.log("查找最大值")
// 查找最大值
console.log(binaryTree.max())
</script>

查找某個值

<script>
var BinaryTree = function(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var rootNode = null;

    var insertNode = function(node , newNode){
        if( newNode.key < node.key ){
            if( node.left == null ){
                node.left = newNode
            }else{
                insertNode(node.left , newNode)
            }
        }else{
            if( node.right == null ){
                node.right = newNode;
            }else{
                insertNode(node.right , newNode)
            }
        }
    }

    this.insert = function(key){
        var newNode = new Node(key);
        if( rootNode == null ){
            rootNode = newNode;
        }else{
            insertNode(rootNode , newNode);
        }
    }

    var searchNode = function(num ,node){
        if( node == null ){
            return false;
        }
        if( node.key < num ){
            return searchNode(num , node.right)
        }else if( node.key > num ){
            return searchNode(num , node.left)
        }else{
            return true;
        }
    }
    this.search = function(num){
        return searchNode(num , rootNode);
    }   
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree();
nodes.forEach(function(key){
    binaryTree.insert(key)
})
console.log("查找某個值")
// 查找某個值
var num = 7;
console.log(binaryTree.search(num))
</script>

未完待續(xù)...

最后編輯于：2017.12.11 05:54:41

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末卢肃，一起剝皮案震驚了整個濱河市疲迂，隨后出現(xiàn)的幾起案子才顿，更是在濱河造成了極大的恐慌，老刑警劉巖尤蒿，帶你破解...
沈念sama閱讀 206,378評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件郑气，死亡現(xiàn)場離奇詭異，居然都是意外死亡腰池，警方通過查閱死者的電腦和手機尾组，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,356評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來示弓，“玉大人讳侨，你說我怎么就攤上這事∽嗍簦” “怎么了跨跨？”我有些...
開封第一講書人閱讀 152,702評論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長囱皿。經(jīng)常有香客問我勇婴，道長，這世上最難降的妖魔是什么嘱腥？我笑而不...
開封第一講書人閱讀 55,259評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任耕渴，我火速辦了婚禮，結(jié)果婚禮上齿兔，老公的妹妹穿的比我還像新娘橱脸。我一直安慰自己，他們只是感情好分苇，可當(dāng)我...
茶點故事閱讀 64,263評論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著组砚，像睡著了一般。火紅的嫁衣襯著肌膚如雪糟红。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,036評論 1贊 285
城市分裂傳說
那天乌叶，我揣著相機與錄音，去河邊找鬼准浴。笑死事扭，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的乐横。我是一名探鬼主播求橄，決...
沈念sama閱讀 38,349評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼今野，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了罐农？” 一聲冷哼從身側(cè)響起条霜，我...
開封第一講書人閱讀 36,979評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎涵亏，沒想到半個月后宰睡，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,469評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡气筋，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,938評論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年拆内，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片宠默。...
茶點故事閱讀 38,059評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡麸恍，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出光稼，到底是詐尸還是另有隱情或南，我是刑警寧澤，帶...
沈念sama閱讀 33,703評論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布艾君，位于F島的核電站采够，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏冰垄。R本人自食惡果不足惜蹬癌，卻給世界環(huán)境...
茶點故事閱讀 39,257評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望虹茶。院中可真熱鬧逝薪，春花似錦、人聲如沸蝴罪。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,262評論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽要门。三九已至虏肾，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間欢搜，已是汗流浹背封豪。一陣腳步聲響...
開封第一講書人閱讀 31,485評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留炒瘟，地道東北人吹埠。一個月前我還...
沈念sama閱讀 45,501評論 2贊 354
代替公主和親
正文我出身青樓，卻偏偏與公主長得像，于是被迫代替她去往敵國和親缘琅。傳聞我的和親對象是個殘疾皇子粘都，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 42,792評論 2贊 345

Javascript實現(xiàn)二叉樹算法

二叉排序樹的代碼實現(xiàn)

二叉樹的中序遍歷

代碼實現(xiàn)：

二叉樹的前序遍歷

代碼實現(xiàn)：

二叉樹的后序遍歷

查找最小值

查找最大值

查找某個值

推薦閱讀更多精彩內(nèi)容