js封装一个二叉搜索树

function BinarySearchTree() {
    this.root = null;
    this.count = 0;
    // 内部类  存放节点的信息
    function Node(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }

    // insert 对外用户插入方法
    BinarySearchTree.prototype.insert = function (key) {
        // 创建一个新节点
        let newNode = new Node(key);
        // 判断是否存在根节点
        if (this.root == null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
        this.count++
    }
    // insertNode  内部插入节点方法 递归比较直到找到合适的位置
    BinarySearchTree.prototype.insertNode = function (node, newNode) {
        if (node.key > newNode.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)
            }
        }
    }

    // preOrderTravelsal  先序遍历  
    BinarySearchTree.prototype.preOrderTravelsal = function (handler) {
        this.preOrderTravelsalNode(this.root, handler);
    }
    // preOrderTravelsalNode  根节点->left->right
    BinarySearchTree.prototype.preOrderTravelsalNode = function (node, handler) {
        if (node != null) {
            handler(node.key)
            this.preOrderTravelsalNode(node.left, handler);
            this.preOrderTravelsalNode(node.right, handler);
        }
    }

    // centerOrderTravelsal  中序遍历
    BinarySearchTree.prototype.midOrderTravelsal = function (handler) {
        this.midOrderTravelsalNode(this.root, handler)
    }
    // centerOrderTravelsalNode  left->根节点->right
    BinarySearchTree.prototype.midOrderTravelsalNode = function (node, handler) {
        if (node != null) {
            this.midOrderTravelsalNode(node.left, handler)
            handler(node.key);
            this.midOrderTravelsalNode(node.right, handler)
        }
    }

    // afterOrderTravelsalNode  后序遍历
    BinarySearchTree.prototype.postOrderTravelsal = function (handler) {
        this.postOrderTravelsalNode(this.root, handler)
    }
    // afterOrderTravelsalNode   left->right->root
    BinarySearchTree.prototype.postOrderTravelsalNode = function (node, handler) {
        if (node != null) {
            this.postOrderTravelsalNode(node.left, handler);
            this.postOrderTravelsalNode(node.right, handler);
            handler(node.key)
        }
    }

    // 查找最小值
    BinarySearchTree.prototype.min = function () {
        if (this.root == null) return null;
        let node = this.root;
        while (node.left != null) {
            node = node.left
        }
        return node.key
    }
    // 查找最大值
    BinarySearchTree.prototype.max = function () {
        if (this.root == null) return null;
        let node = this.root;
        while (node.right != null) {
            node = node.right
        }
        return node.key
    }
    // 查找特定值
    BinarySearchTree.prototype.search = function (key) {
        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
    }

    // remove   删除节点
    BinarySearchTree.prototype.remove = function (key) {
        if (this.root == null) return false;
        // 定义一些需要用到的属性
        let current = this.root;
        let parent = null;
        let isLeftChild = false;
        // 1.先找到要删除的节点
        while (current.key != key) {
            parent = current;
            if (current.key > key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            // 没找到节点
            if (current == null) return false
        }
        // 2.找到节点，判断情况处理
        // 2.1 叶子节点
        if (current.left == null && current.right == null) {
            if (current == this.root) {
                this.root = null
            } else if (isLeftChild) {
                parent.left = null
            } else {
                parent.right = null
            }
            return true
        }
        // 2.2 只有一个子节点
        if (current.left == null || current.right == null) {
            if (current == this.root) {
                this.root = current.left || current.right
            } else if (isLeftChild) {
                parent.left = current.left || current.right
            } else {
                parent.right = current.left || current.right
            }
            return true
        }
        // 2.3 有两个子节点
        // 2.3.1 找到后继
        let succssor = this.getSuccssor(current);
        // 2.3.2 情况处理
        if (current == this.root) {
            this.root = succssor
        } else if (isLeftChild) {
            parent.left = succssor
        } else {
            parent.right = succssor
        }
        succssor.left = current.left;
        return true
    }
    // 找删除节点的后继(比删除节点稍微大一点点的节点)
    BinarySearchTree.prototype.getSuccssor = function (delNode) {
        // 定义一些需要用到的属性
        let succssor = delNode.right;
        let parent = delNode;
        // 循环找后继
        while (succssor.left != null) {
            parent = succssor;
            succssor = succssor.left
        }
        // 找到后继，情况处理
        if (succssor != delNode.right) {
            parent.left = succssor.right;
            succssor.right = delNode.right;
        }
        return succssor


    }


}



// -----------------测试-----------------
let bst = new BinarySearchTree();
// 插入节点
bst.insert(6)
bst.insert(5)
bst.insert(8)
bst.insert(9)
bst.insert(2)
bst.insert(4)
bst.insert(7)
bst.insert(1)
bst.insert(3)
// console.log(bst);

// 先序遍历
var str = '';
bst.preOrderTravelsal((key) => {
    str += key + ' '
})
console.log(str);
// 中序遍历
str = '';
bst.midOrderTravelsal((key) => {
    str += key + ' '
})
console.log(str);
// 后序遍历
str = '';
bst.postOrderTravelsal((key) => {
    str += key + ' '
})
console.log(str);
// 最小值
// console.log(bst.min());
// 最大值
// console.log(bst.max());
// 特定值
// console.log(bst.search(3));
// console.log(bst.search(10));

// 删除节点
console.log(bst.remove(9));
// console.log(bst.remove(10));
// console.log(bst.search(4));
str = '';
bst.postOrderTravelsal((key) => {
    str += key + ' '
})
console.log(str);