JS中的二叉搜索树

2021-01-18 10:42发布

代码封装:

//封装二叉搜索树
        function BinarySearchTree(){
            //节点
            function Node(key){
                this.key = key;
                this.left = null;
                this.right = null;
            }
            //属性
            this.root = null;

            //方法
            //插入节点:给用户调用的方法
            BinarySearchTree.prototype.insert = function (key){
                //1.根据key创建节点
                var newNode = new Node(key);
                //2.判断根节点是否有值
                if(this.root == null){
                    this.root = newNode;
                }else{
                    this.insertNode(this.root,newNode)
                }
            }
            //内部插入方法
            BinarySearchTree.prototype.insertNode = function(node,newNode){
                if(newNode.key < node.key){
                    //向左查找
                    //如果左节点为空
                    if(node.left == null){
                        node.left = newNode;
                    }else{
                         //如果左节点不为空,递归查询
                        this.insertNode(node.left,newNode);
                    }
                }else{
                    //向右查找
                    //如果右节点为空
                    if(node.right == null){
                        node.right = newNode;
                    }else{
                        this.insertNode(node.right,newNode);
                        
                    }
                }
            }
            //树的遍历
            //1.先序遍历
            BinarySearchTree.prototype.preOrderTraversal = function(handler){
                this.preOrderTraversalNode(this.root, handler);
            }
            BinarySearchTree.prototype.preOrderTraversalNode = function(node,handler){
                if(node != null){
                    //1.处理经过的节点
                    handler(node.key);
                    //2.处理经过的节点的左子节点
                    this.preOrderTraversalNode(node.left,handler);
                    //3.处理经过的节点的右子节点
                    this.preOrderTraversalNode(node.right,handler);
                }
            }

            //中序遍历
            BinarySearchTree.prototype.midOrderTraversal = function(handler){
                this.midOrderTraversalNode(this.root, handler);
            }
            BinarySearchTree.prototype.midOrderTraversalNode = function(node,handler){
                if(node != null){
                    //1.处理经过的节点的左子节点
                    this.midOrderTraversalNode(node.left,handler);
                    //2.处理经过的节点
                    handler(node.key);
                    //3.处理经过的节点的右子节点
                    this.midOrderTraversalNode(node.right,handler);
                }
            }
             //后序遍历
             BinarySearchTree.prototype.postOrderTraversal = function(handler){
                this.postOrderTraversalNode(this.root, handler);
            }
            BinarySearchTree.prototype.postOrderTraversalNode = function(node,handler){
                if(node != null){
                    //1.处理经过的节点的左子节点
                    this.postOrderTraversalNode(node.left,handler);
                    //2.处理经过的节点的右子节点
                    this.postOrderTraversalNode(node.right,handler);
                    //3.处理经过的节点
                    handler(node.key);
                    
                }
            }
            //寻找最大值
            BinarySearchTree.prototype.max = function(){
                //1.获取根节点
                //2.依次向右不断的查找,直到节点为null
                var node = this.root;
                var key = null;
                while(node !== null){
                    key = node.key;
                    node = node.right;
                }
                return key;
            }
             //寻找最小值
             BinarySearchTree.prototype.min = function(){
                var node = this.root;
                var key = null;
                //2.依次向右不断的查找,直到节点为null
                while(node !== null){
                    key = node.key;
                    node = node.left;
                }

                return key;
            }
            BinarySearchTree.prototype.findMaxNode = function(node){
                //1.获取根节点
                //2.依次向右不断的查找,直到节点为null
                var parent = null;
                var current = node;
                while(1){
                    parent = current
                    current = current.right;
                    if(current.right === null){
                        break;
                    }
                }
                return [current,parent];
            }
            //搜索某一个key
            BinarySearchTree.prototype.search = function (key){
                //1.获取根节点
                var node = this.root;
                //2.循环搜索key
                while(node!= null){
                    if(key < node.key){
                        node = node.left;
                    }else if(key > node.key){
                        node = node.right;
                    }else{
                        return true;
                    }
                }
                return false;
            }
            //删除节点
            BinarySearchTree.prototype.remove = function (key){
                //1.寻找我们要删除的节点
                //1.1定义变量,保存信息
                var current = this.root;
                var parent = null;
                var isLeftChild = true;
                //1.2开始寻找删除的节点
                while(current.key != key){
                    parent = current;
                    if(key < current.key){
                        isLeftChild = true;
                        current = current.left;
                    }else{
                        isLeftChild = false;
                        current = current.right;
                    }
                    //如果已经找到了最后一个节点,依然没找到
                    if(current == null){
                        return false;
                    }
                }
                //2.根据对应的情况,删除节点
                //找到了current.key === key
                if(current.left == null && current.right == null){  //2.1删除的节点是叶子节点
                    //2.1.1删除的是只有一个节点的根节点
                    if(current == this.root){
                        this.root = null;
                    }else{
                        if(isLeftChild){
                            parent.left = null;
                        }else{
                            parent.right = null;
                        }
                    }
                    
                }else if(current.left != null && current.right != null){   //2.2删除的节点有两个子节点
                    var [max,maxParent] = this.findMaxNode(current.left);
                    console.log(max);
                    console.log(parent);
                    if(isLeftChild){
                        parent.left = max;
                        if(max!==current.left){
                            parent.left.left = current.left;
                            maxParent.right = null;
                        }
                        parent.left.right = current.right;

                    }else{
                        parent.right = max;
                        if(max!==current.left){
                            parent.right.left = current.left;
                            maxParent.right = null;
                        }
                        parent.right.right = current.right;
                        return;
                    }
                     
                }else{     //2.3删除的节点有一个子节点  
                    if(current === this.root){  //2.3.1删除节点的是只有一个子节点的根节点
                        if(isLeftChild){
                            this.root = current.left;
                        }else{
                            this.root = current.right;
                        }
                    }else if(current.left == null){   //2.3.2删除节点的左子节点为空
                        //要删除的节点是父节点的左子节点
                        if(isLeftChild){
                            parent.left = current.right;
                        }else{
                             //要删除的节点是父节点的右子节点
                             parent.right = current.right                        }
                    }else{                                         //2.3.2删除节点的右子节点为空
                        //要删除的节点是父节点的左子节点
                        if(isLeftChild){
                            parent.left = current.left;
                        }else{
                             //要删除的节点是父节点的右子节点
                             parent.right = current.left                        }
                    }
                }
            }
        }



作者:cake_eat

链接:https://blog.csdn.net/cake_eat/article/details/110956760

来源:CSDN
著作权归作者所有,转载请联系作者获得授权,切勿私自转载。