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>

未完待续...

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容