javascript二叉树基本功能实现-阿里云开发者社区

开发者社区> 天飞> 正文

javascript二叉树基本功能实现

简介: 都是常用的功能。 删除是最复杂的。。 test function BinarySearchTree(){ var Node = function(key){ this.
+关注继续查看

都是常用的功能。

删除是最复杂的。。

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>test</title>
    <script src="js/lib/angular.min.js"></script>
    <script >
        function BinarySearchTree(){
            var Node = function(key){
                this.key = key;
                this.left = null;
                this.right = null;
            };
            var root = null;
            
            this.insert = function(key){
                var newNode = new Node(key);
                
                if (root === null) {
                    root = newNode;
                } else {
                    insertNode(root, newNode);
                }
            };
            
            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.inOrderTraverse = function(callback) {
                inOrderTraverseNode(root, callback);
            };
            
            var inOrderTraverseNode = function(node, callback) {
                if (node !== null) {
                    inOrderTraverseNode(node.left, callback);
                    callback(node.key);
                    inOrderTraverseNode(node.right, callback);
                }
            };
            
            this.preOrderTraverse = function(callback){
                        preOrderTraverseNode(root, callback);
                    };
                    
                    var preOrderTraverseNode = function (node, callback) {
                        if (node !== null) {
                            callback(node.key); //{1}
                            preOrderTraverseNode(node.left, callback); //{2}
                            preOrderTraverseNode(node.right, callback); //{3}
                        }
                    };
                    
                    this.postOrderTraverse = function(callback){
                        postOrderTraverseNode(root, callback);
                    };
            
            var postOrderTraverseNode = function (node, callback) {
                        if (node !== null) {
                            postOrderTraverseNode(node.left, callback); //{1}
                            postOrderTraverseNode(node.right, callback); //{2}
                            callback(node.key); //{3}
                        }
                    };
                    
                    this.min = function() {
                        return minNode(root);
                    };
                    
                    var minNode = function(node) {
                        if (node) {
                            while (node && node.left !== null) {
                                node = node.left;
                            }
                            return node.key;
                        }
                        return null;
                    };
                    
                    this.max = function() {
                        return maxNode(root);
                    };
                    
                    var maxNode = function (node) {
                        if (node){
                            while (node && node.right !== null) { //{5}
                                node = node.right;
                            }
                            return node.key;
                        }
                        return null;
                    };
                    
                    this.search = function(key) {
                        return searchNode(root, key);
                    };
                    
                    var searchNode = function(node, key) {
                        if (node === null) {
                            return false;
                        }
                        if (key < node.key) {
                            return searchNode(node.left, key);
                        } else if (key > node.key) {
                            return searchNode(node.right, key);
                        }else{
                            return true;
                        }
                    };
                    
                    this.remove = function(key) {
                        root = removeNode(root, key);
                    };
                    
                    var removeNode = function(node, key){
                        if (node === null){ //{2}
                            return null;
                        }
                        if (key < node.key){ //{3}
                            node.left = removeNode(node.left, key); //{4}
                            return node; //{5}
                        } else if (key > node.key){ //{6}
                            node.right = removeNode(node.right, key); //{7}
                            return node; //{8}
                        } else { //键等于node.key
                            //第一种情况——一个叶节点
                            if (node.left === null && node.right === null){ //{9}
                            node = null; //{10}
                            return node; //{11}
                            }
                            //第二种情况——一个只有一个子节点的节点
                            if (node.left === null){ //{12}
                            node = node.right; //{13}
                            return node; //{14}
                            } else if (node.right === null){ //{15}
                            node = node.left; //{16}
                            return node; //{17}
                            }
                            //第三种情况——一个有两个子节点的节点
                            var aux = findMinNode(node.right); //{18}
                            node.key = aux.key; //{19}
                            node.right = removeNode(node.right, aux.key); //{20}
                            return node; //{21}
                        }
                    };
                    
        }
        
        function printNode(value) {
                console.log(value);
        }
            
          var tree = new BinarySearchTree();
          tree.insert(11);
          tree.insert(7);
                tree.insert(15);
                tree.insert(5);
                tree.insert(3);
                tree.insert(9);
                tree.insert(8);
                tree.insert(10);
                tree.insert(13);
                tree.insert(12);
                tree.insert(14);
                tree.insert(20);
                tree.insert(18);
                tree.insert(25);
                tree.insert(6);
                
                tree.inOrderTraverse(printNode);
                tree.preOrderTraverse(printNode);
                tree.postOrderTraverse(printNode);
                console.log(tree.min());
                console.log(tree.max());
                console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.');
                console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.');
                    
        
    </script>

</head>
<body>

</body>
</html>

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Sharding-Proxy的基本功能使用
Sharding-Proxy是一个分布式数据库中间件,定位为透明化的数据库代理端。作为开发人员可以完全把它当成数据库,而它具体的分片规则在Sharding-Proxy中配置。
871 0
Jsp+JavaBean+Servlet实现模拟银行账户存取款等功能的网站(实习第4-8天)
本来想学J2EE的3个经典框架(Spring + Struts +Hibernate),奈何负责实习的老师只讲了Jsp+JavaBean+Servlet,项目时间还蛮紧的,所以只用JJS实现了这个项目,后面寒假有时间的话再用SSH实现并完善这个网站吧。前几天抽时间学了点前端的东西,感觉还是有点麻烦的,前端做既漂亮又有良好的兼容性不是件太容易的事情,所幸现在觉得能够静下来学技术做开发是件
1320 0
dubbo-go 的开发、设计与功能介绍
dubbo-go 的前世今生 dubbo-go 是目前 Dubbo 多语言生态最火热的项目。dubbo-go 最早的版本应该要追溯到 2016 年,由社区于雨同学编写 dubbo-go 的初版。当时很多东西没有现成的轮子,如 Go 语言没有像 netty 一样的基于事件的网络处理引擎、 hessian2 协议没有 Go 语言版本实现,加上当时 Dubbo 也没有开始重新维护。
8132 0
剑指Offer——二叉树的镜像(JS实现)
剑指Offer——二叉树的镜像(JS实现)
16 0
+关注
天飞
一个运维老同志
1512
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载