SOURCE

function BinarySearchTree() {
    this.root = null;

    function Node(key) {
        this.key = key;
        this.right = null;
        this.left = null;
    }

    // 插入节点
    BinarySearchTree.prototype.insert = function(key) {
        // 根据key创建节点
        const newNode = new Node(key);

        // 判断根节点是否有值
        if(!this.root) {
            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)
            }
        }

        if(newNode.key > node.key) {
            // 右插入
            if(node.right == null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right,newNode)
            }
        }
    }

    // 先序遍历
    BinarySearchTree.prototype.preOrderTraverse = function(handler) {
        this.preOrderTraverseNode(this.root,handler)
    }

    BinarySearchTree.prototype.preOrderTraverseNode = function(node,handler) {
        if(node !== null) {
            // 处理节点
            handler(node.key)
            // 处理节点的左子节点
            this.preOrderTraverseNode(node.left,handler)
            // 处理节点的右子节点
            this.preOrderTraverseNode(node.right,handler)
        }  
     }


     // 中序遍历
     BinarySearchTree.prototype.midOrderTraverse = function(handler) {
         this.midOrderTraverseNode(this.root,handler)
     }

     BinarySearchTree.prototype.midOrderTraverseNode = function(node,handler) {
         if(node !==null)  {
             // 处理左子节点
             this.midOrderTraverseNode(node.left,handler);
             // 处理节点
             handler(node.key);
             // 处理右子节点
             this.midOrderTraverseNode(node.right,handler);
         }
     }


     // 后序遍历
    BinarySearchTree.prototype.postOrderTraverse = function(handler) {
         this.postOrderTraverseNode(this.root,handler)
     }

     BinarySearchTree.prototype.postOrderTraverseNode = function(node,handler) {
         if(node !==null)  {
             // 处理左子节点
             this.postOrderTraverseNode(node.left,handler);
             // 处理右子节点
             this.postOrderTraverseNode(node.right,handler);
            // 处理节点
             handler(node.key);
         }
     }


    // 最值
     BinarySearchTree.prototype.min = function() {
         let node = this.root;
         while(node.left !== null) {
             node = node.left;
         }
         return node.key;
     }

     BinarySearchTree.prototype.max = function() {
         let node = this.root;
         while(node.right !== null) {
             node = node.right
         }
         return node.key
     }


     BinarySearchTree.prototype.remove = function(key) {
         // 从root出发寻找删除节点
         let current = this.root;
         let parent = null;
         // 是否为左子节点
         let isLeft = false;

         while(current.key != key) {
             parent = current;
             if(key < current.key) {
                current = current.left;
                isLeft = true;
             } else {
                 current = current.right;
                 isLeft = false
             }
            
            // 找到末尾依旧没有找到
             if(current == null) return false;
         }   

         // 找到的节点是叶子节点
         // 情况1是叶子节点也是根节点
         if(current.right == null && current.left == null) {
             if(current == this.root) {
                 this.root = null;
             } else if(isLeft) {
                 parentleft = null;
             } else {
                 parent.right = null;
             }
         } 
         // 情况2当前节点只存在一个子节点
         else if(current.right == null) {
             // 情况2当前节点只存在一个子节点
             // 当前节点只存在左子节点
             // 当前节点是根节点
             if(current == this.root) {
                 this.root = current.left
             } else if(isLeft) {
                 // 当前节点是左子节点
                 parent.left = current.left
             } else {
                 // 当前节点是右子节点
                 parent.right = current.left
             }
         } else if(current.left == null) {
             // 当前节点只存在右子节点
             // 当前节点是根节点
               if(current == this.root) {
                 this.root = current.right
                } else if(isLeft) {
                    // 当前节点是左子节点
                    parent.left = current.right
                } else {
                    parent.right =current.right
                }
         } else {
             // 找到后续节点
            let successor = this.getSuccessor(current);
            // 判断是否为根节点，左子节点，右子节点
             if(current == this.root) {
                 this.root = successor
                } else if(isLeft) {
                    // 当前节点是左子节点
                    parent.left = successor
                } else {
                    parent.right = successor
            }
         }

     }

     // 获取后续节点，即从要删除的节点的右边开始查找最小的值
     BinarySearchTree.prototype.getSuccessor = function(delNode) {
        // 定义变量，保存要找到的后续
         let current = delNode.right;
         let successorParent = delNode; // 后续节点的父节点 
         let successor = delNode.right; // 后续节点
        
        // 不断获取右边子树的深层左节点
        while(current.left != null) {
            successorParent = successor;
            current = current.left;
            successor = current;
            console.log(successor)
        }

        // 判断寻找到的后续节点是否直接就是要删除节点的 right
         if (successor != delNode.right) {
            successorParent.left = successor.right;
            successor.right = delNode.right;
        }
        

        return successor;
     }  

}


const BST = new BinarySearchTree();

BST.insert(11);
BST.insert(7);
BST.insert(15);
BST.insert(5);
BST.insert(3);
BST.insert(9);
BST.insert(8);
BST.insert(10);
BST.insert(13);
BST.insert(12);
BST.insert(14);
BST.insert(20);
BST.insert(18);
BST.insert(25);
BST.insert(6);


BST.remove(9)