JS实现二叉搜索树

[akeymo]

二叉搜索树的左节点值比根节点小，右节点值比根节点大。因此，整棵树的最小值总是在最左边叶子节点，而最大值总在最右边叶子节点。

class binarySearchTree {
    constructor() {
        this.root = null;
    }

    // 初始化节点
    initNode(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }

    // 插入节点
    insert(key) {
        const node = new this.initNode(key);
        if (this.root === null) {
            this.root = node;
        } else {
            insertNode(node, this.root);
        }
    }

    insertNode(newNode, node) {
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(newNode, node.left);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(newNode, node.right);
            }
        }
    }

    // 查找一个节点
    search(key) {
        this.searchNode(this.root, key);
    }

    searchNode(node, key) {
        if (node === null) return false;

        if (key < node.key) {
            this.searchNode(node.left, key);
        } else if (key > node.key) {
            this.searchNode(node.right, key);
        } else {
            return true;
        }
    }

    // 前序遍历（根-左-右）
    preOrderTraverse(callback) {
        this.preOrderTraverseNode(this.root, callback);
    }

    preOrderTraverseNode(node, callback) {
        if (node !== null) {
            callback(node.key);
            this.preOrderTraverseNode(node.left, callback);
            this.preOrderTraverseNode(node.right, callback);
        }
    }

    // 中序遍历（左-根-右）
    inOrderTraverse(callback) {
        this.inOrderTraverseNode(this.root, callback);
    }

    inOrderTraverseNode(node, callback) {
        if (node !== null) {
            this.inOrderTraverseNode(node.left);
            callback(node.key);
            this.inOrderTraverseNode(node.right);
        }
    }

    // 后序遍历（左-右-根）
    postOrderTraverse(callback) {
        this.postOrderTraverseNode(this.root, callback);
    }

    postOrderTraverseNode(node, callback) {
        if (node !== null) {
            this.postOrderTraverseNode(node.left, callback);
            this.postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    }

    // 最小值-最左边值
    min() {
        this.minNode(this.root);
    }

    minNode(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node;
        }
        return null;
    }

    // 最大值-最右边值
    max() {
        this.maxNode(this.root);
    }

    maxNode(node) {
        if (node) {
            while (node && node.right) {
                node = node.right;
            }

            return node;
        }

        return null;
    }

    // 删除一个节点
    remove(key) {
        this.root = this.removeNode(this.root, key);
    }

    removeNode(node, key) {
        if (node === null) return null;

        if (key < node.key) {
            node.left = this.removeNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = this.removeNode(node.right, key);
            return node;
        } else {
            // key等于node.key


            if (node.left === null && node.right === null) {
                // 叶子节点
                node = null;
                return node;
            }

            if (node.left === null) {
                // 只有一个右叶子，将右叶子替代node
                node = node.right;
                return node;
            } else if (node.right === null) {
                // 只有一个左叶子，左叶子替代node
                node = node.left;
                return node;
            }

            // 有两个子节点的非叶子节点
            // 找到它右侧最小节点来继承它
            const aux = this.minNode(node.right);
            node.key = aux.key;
            // 删除它的继承者原本的节点
            node.right = this.removeNode(node.right, aux.key);
            return node;
        }
    }
}