[JavaScript知识库]二叉树的增删改查--js实现

        //二叉搜索树
   function BinarySearchTree(){
       function Node(key){
           this.key = key
           this.left = null
           this.right = null
       }
       this.root = null
       //插入操作 向数组中插入一个新的key
       BinarySearchTree.prototype.insert = function insert(key){
             const newNode = new Node(key)
             if(this.root == null){
                this.root = newNode
             }else{
                this.insertNode(this.root,newNode)
             }
       }
       //封装一个往下继续查找的递归函数。方便插入时调用.Node就是往这里插，newNode就是要插的值
       BinarySearchTree.prototype.insertNode = function(node,newNode){
           //判断这两个节点的哪个大,如果新传的newNode大，就往node.right插
            if(node.key<newNode.key){
                //判断node.right是否为空
                if(node.right == null){
                    node.right = newNode
                }else{
                    this.insertNode(node.right,newNode)
                }
            }else{
                if(node.left == null){
                    node.left = newNode
                }else{
                    this.insertNode(node.left,newNode)
                }
            }
       }
   }
       //先序遍历，遍历所有节点
       BinarySearchTree.prototype.preOverTraverses = function preOverTraverses(){
            this.preOverTraversesNode(this.root)
       }
       BinarySearchTree.prototype.preOverTraversesNode = function(node){
             if(node == null) return ;
             console.log(node.key);
             //先遍历左节点，再右节点就是先序遍历
             this.preOverTraversesNode(node.left)
             this.preOverTraversesNode(node.right)
       }
       //中序遍历
       BinarySearchTree.prototype.inOverTraverses = function inOverTraverses(){
            this.OverTraversesNode(this.root)
       }
       BinarySearchTree.prototype.OverTraversesNode = function(node){
             if(node == null) return ;
             this.OverTraversesNode(node.left)
             console.log(node.key);
             this.OverTraversesNode(node.right)
       }
       //后序遍历
       BinarySearchTree.prototype.outOverTraverses = function outOverTraverses(){
            this.ouTraversesNode(this.root)
       }
       BinarySearchTree.prototype.ouTraversesNode = function(node){
             if(node == null) return ;
             this.ouTraversesNode(node.left)
             this.ouTraversesNode(node.right)
             console.log(node.key);
       }
       //求二叉树最大值
       BinarySearchTree.prototype.max = function max(){
           let node = this.root
           while(node.right != null){
               node = node.right
           }
           return node.key
       }
       //求二叉树最小值
       BinarySearchTree.prototype.min = function min(){
        let node = this.root
           while(node.left != null){
               node = node.left
           }
           return node.key
       }
       //search 查找这个key是否存在，返回定影true false
       BinarySearchTree.prototype.search = function search(key){
           //1.第一种循环算法
        //    let node = this.root
        //    while(node != null){
        //        if(node.key<key){
        //            node = node.right
        //        }else if(node.key>key){
        //            node = node.left
        //        }else{
        //            return true
        //        }
        //    }
        //    return false
        //2.第二种递归算法
         return this.lSearch(this.root,key)
       }
       BinarySearchTree.prototype.lSearch = function (node,key){
        if(node == null)  return false
            if(node.key>key){
                return this.lSearch(node.left,key)
            }else if(node.key<key){
                return this.lSearch(node.right,key)
            }else{
                return true
            }
       }
       //remove删除节点
       BinarySearchTree.prototype.remove = function remove(key){
           //定义变量
           let current = this.root
           let parent = null
           let isLeft = true
           //查找要删除的节点
           while(current.key != key){
                   parent = current
               if(key<current.key){
                   isLeft = true
                   current = current.left
               }else{
                   isLeft = false
                   current = current.right
               }
               if(current == null) return false
           }
           //找到节点 current
           //情况一，删除的节点，没有子节点
           if(current.left == null && current.right == null){
               if(current == this.root){
                   this.root = null
               }else if(isLeft){
                   parent.left = null
               }else{
                   parent.right = null
               }
           }
           //isLeft时记录的此时current在parent的左边还是右边
           else if(current.right == null){ //只有左子节点
               if(current == this.root){
                   this.root = current.left
               }else if(isLeft){
                   current.left = parent.left
               }else{
                   current.left = parent.right
               }
           }else if(current.left == null){ //只有右字节点
               if(current == this.root){
                   this.root = current.right
               }else if(isLeft){
                   current.right = parent.left
               }else{
                   parent.right = current.right
               }
           }else{
               //1.获取后继节点
               let successor = this.getSuccess(current)
               //判断是否为根节点
               if(this.root == current){
                   this.root = successor
               }else if(isLeft){
                   parent.left = successor
               }else{
                   parent.right = successor
               }
               
               successor.left = current.left
           }
           return true
       }
       //获取删除的节点要更替的值
       BinarySearchTree.prototype.getSuccess = function getSuccess(delNode){
            //1.定义变量，存储临时节点
            let successParent = delNode;
            let success = delNode;
            let current = delNode.right
            //循环之至找出对应的节点
            while(current != null){
                successParent = success
                success = current;
                current = current.left
            }
            //如果后继节点不是删除节点的右节点
            if(success != delNode.right){
                successParent.left = success.right
                success.right = delNode.right
            }
            return success
       }



   const binarysearchtree = new BinarySearchTree()