二叉搜索树-完整代码

• 结构
  • Node 定义
  • BinarySearchTree 定义
    • insert <-- insertNode递归
    • search <-- searchNode递归
    • min <-- getMin递归
    • max <-- getMax递归
    • remove <-- removeNode递归

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

class BinarySearchTree {
    constructor() {
        this.root = null
    }
    insertNode(root, key) {
        if (key < root.key) {
            if (root.left) {
                this.insertNode(root.left, key);
            } else {
                root.left = new Node(key);
            }
        } else if (key > root.key) {
            if (root.right) {
                this.insertNode(root.right, key);
            } else {
                root.right = new Node(key);
            }
        } else {
            return;
        }
    }

    insert(key) {
        if (this.root === null) {
            this.root = new Node(key);
        } else {
            this.insertNode(this.root, key);
        }
    }

    searchNode(root, key) {
        if (key === root.key) {
            return true;
        } else if (key < root.key) {
            if (root.left) {
                return this.searchNode(root.left, key);
            } else {
                return false;
            }
        } else {
            if (root.right) {
                return this.searchNode(root.right, key);
            } else {
                return false;
            }
        }
    }

    search(key) {
        if (this.root === null) {
            return false;
        } else {
            return this.searchNode(this.root, key);
        }
    }

    getMin(root) {
        if (root.left) {
            return this.getMin(root.left);
        } else {
            return root;
        }
    }

    min() {
        if (this.root === null) {
            return undefined;
        } else {
            return this.getMin(this.root);
        }
    }

    getMax(root) {
        if (root.right) {
            return this.getMax(root.right);
        } else {
            return root;
        }
    }

    max() {
        if (this.root === null) {
            return undefined;
        } else {
            return this.getMax(this.root);
        }
    }

    removeNode(root, key) {
        if (root === null) return null;
        if (key < root.key) {
            root.left = this.removeNode(root.left, key);
        } else if (key > root.key) {
            root.right = this.removeNode(root.right, key);
        } else {
            if (!root.left && !root.right) {
                root = null;
            } else if (!root.left) {
                root = root.right;
            } else if (!root.right) {
                root = root.left;
            } else {
                const minNode = this.getMin(root.right);
                root.key = minNode.key;
                root.right = this.removeNode(root.right, minNode.key);
            }

            return root;
        }
    }

    remove(key) {
        this.root = this.removeNode(this.root, key);
    }
}

(() => {
    //测试用例
    const tree = new BinarySearchTree();
    tree.insert(3);
    tree.insert(1);
    tree.insert(6);
    tree.insert(7);
    tree.insert(2);
    tree.insert(5);
    tree.insert(4);
    tree.insert(4);
    console.log(tree.search(3));
    console.log(tree.search(8));
    console.log(tree.min());
    console.log(tree.max());
    console.log(tree.remove(3));
    console.log(tree.search(3));
})()