Javascript实现二叉树算法

最近正在看慕课网的《Javascript实现二叉树算法》课程，现把看到的东西记录下来。
什么是二叉树？简单来说，二叉树是一种具有层级特性的数据结构，一棵树包含多个节点。节点自身含有一个属性，就是他所代表的数值。
排序二叉树具有以下特征：
1、如果他的左子树上不为空，则他的左子树上所有节点的值都小于根节点上的值；
2、如果他的右子树上不为空，则他的右子树上所有节点的值都小于根节点上的值；
3、他的左、右子树也是二叉排序树；
4、没有完全相等的两个节点；

二叉树

二叉排序树的代码实现

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

二叉树的中序遍历

从根节点开始，如果存在左子树就开始遍历左子树，然后再遍历右子树，最后输出根节点的值。遍历左、右子树时也是先遍历左子树，然后遍历右子树，最少输出改接点，如此循环。

代码实现：

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

打印出来的结果

中序遍历

二叉树的前序遍历

从根节点开始，先输出当前节点，如果存在左子树就开始遍历左子树，然后再遍历右子树。遍历左、右子树的规则同上。

代码实现：

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

打印出来的结果

前序遍历

二叉树的后序遍历

代码实现：

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

打印结果

后序遍历

查找最小值

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

未完待续...

最后编辑于：2017.12.11 05:54:41

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,319评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,801评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,567评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,156评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,019评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,090评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,500评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,192评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,474评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,566评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,338评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,212评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,572评论 3赞 298
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,890评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,169评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,478评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,661评论 2赞 335

Javascript实现二叉树算法

二叉排序树的代码实现

二叉树的中序遍历

代码实现：

二叉树的前序遍历

代码实现：

二叉树的后序遍历

查找最小值

查找最大值

查找某个值

推荐阅读更多精彩内容