javascript二叉树基本功能实现

javascript二叉树基本功能实现

都是常用的功能。

删除是最复杂的。。

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

javascript二叉树基本功能实现

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108897.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • matlab新手入门_入门画画初学者

    matlab新手入门_入门画画初学者matlab入门MATLAB是“matrixlaboratory”的缩写形式。MATLAB®主要用于处理整个的矩阵和数组,而其他编程语言大多逐个处理数值。矩阵是指通常用来进行线性代数运算的二维数组。MATLAB是美国MathWorks公司出品的商业数学软件,用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境,主要包括MATLAB和Simulink两大部分。…

  • 微信定位精灵 android,微信定位精灵安卓版下载「建议收藏」

    微信定位精灵 android,微信定位精灵安卓版下载「建议收藏」微信定位精灵安卓版下载是一款非常好用的位置伪装软件。可以让用户不会受任何地理位置的限制,也不需要担心自己被查岗的问题了,支持的软件也是很丰富的,定位也都是非常精准的。感兴趣的话就不要错过了,不妨来下载体验一下吧!微信定位精灵安卓版下载软件特色:1、可以让用户在被查岗的时候可以更加的有底气,就不需要担心这个了。2、这里可以让用户进行摇一摇切换微信位置,不需要切换到软件的界面。3、这里可以一键分享自己…

  • 原生JS 扫雷游戏 自动插旗子 自定义雷区大小 雷数可调

    原生JS 扫雷游戏 自动插旗子 自定义雷区大小 雷数可调《扫雷》是Microsoft于1992年附带在Windows3.1操作系统中的单机游戏,它通过点击方格并以出现数字来判断附近雷的数量,将全部地雷做上标记即可胜利。最后在2015年7月发布的Windows10中移除了这个游戏。随机变换雷区颜色,以及其它CSS样式,动画效果全是CSS。点击网页上的元素触发游戏事件打开雷区。如果对于一个方格,其周围未打开的方格恰好全都有雷,那么这些雷将全部自动被标记为小红旗,而玩家只需要一直点击雷区直至雷区全被打开并胜利呈现YOUWIN~没错,全程左键操作。在地

  • 门户网站开发[通俗易懂]

    门户网站开发[通俗易懂]最近正在考虑开发一个门户网站。领导要求比较急,所以有的东西就得暂停一下了。关键是我个人也想早点做出来,做出来了有中成就感,感觉好极了。开发计划步骤:1.需求分析。在这个时候领导还是打算网站外包出去的,采取资源互换形式,即不花钱那种,我就开始认真的写需求,尽可能的详细精确,因为我也开发过网站,对于一个开发者来说一个好的需求是非常非常重要的。但是人家想让我们出一部分钱,领导不愿意了

  • linux dhcp服务器搭建_如何自己搭建服务器

    linux dhcp服务器搭建_如何自己搭建服务器本篇是关于在Linux服务器上安装并配置DHCP服务器的配置教程!

    2022年10月25日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号