BSTII.js

// 定义节点
function Node(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;       
}

/*
 * 定义二分搜索树
 */
module.exports.BST = class BST {
    constructor() {
        this.root = null; // 根节点
        this.count = 0; // 节点个数
    }

    // 向二分搜索树种插入一个新的数据对
    insert(key, value) {
        this.root = this.__insert(this.root, key, value);
    }
    // 向以node为根的二分搜索树中，插入节点(key, value),使用递归算法
    // 返回插入新节点后的二分搜索树的根
    __insert(node, key, value) {
        if(node === null) {
            this.count++;
            return new Node(key, value);
        }
        // 如果key在树中已经存在，则更新value
        if(key === node.key) node.value = value;
        else if(key < node.key)
            node.left = this.__insert(node.left, key, value);
        else
            node.right = this.__insert(node.right, key, value);
        return node; // 返回原来的节点
    }

    // 查看二分搜索树种是否存在键key
    contain(key) {
        return this.__contain(this.root, key);
    }
    // 查看node为根的二分搜索树种是否包含键值为key的节点，使用递归算法
    __contain(node, key) {
        if(node === null) return false;
        if(key === node.key) return true;
        else if(key < node.key) return this.__contain(node.left, key);
        else return this.__contain(node.right, key);
    }

    // 在二分搜索树种搜索键key所对应的值。如果这个值不存在返回null
    search(key) {
        return this.__search(this.root, key);
    }
    // 在以node为根的二分搜索树种中查找key所对应的value，使用递归算法
    __search(node, key) {
        if(node === null) return null;
        if(key === node.key) return node.value;
        else if(key < node.key) return this.__search(node.left, key);
        else return this.__search(node.right, key);
    }

    // 二分搜索树的前序遍历,深度优先遍历
    preOrder() {
        let str = "";
        this.__preOrder(this.root, (node) => {
            str += node.key + " ";
        });
        console.log(str);
    }
    // 对以node为根的二叉搜索树进行前序遍历，递归算法
    // 传入handle函数用于输出数据
    __preOrder(node, handle) {
        if(node !== null) {
            handle(node);
            this.__preOrder(node.left, handle);
            this.__preOrder(node.right, handle);
        }
    }

    // 二分搜索树的中序遍历,深度优先遍历
    inOrder() {
        let str = "";
        this.__inOrder(this.root, (node) => {
            str += node.key + " ";
        });
        console.log(str);
    }
    // 对以node为根的二叉搜索树进行中序遍历，递归算法
    // 传入handle函数用于输出数据
    __inOrder(node, handle) {
        if(node !== null) {
            this.__inOrder(node.left, handle);
            handle(node);
            this.__inOrder(node.right, handle);
        }
    }

    // 二分搜索树的后序遍历,深度优先遍历
    postOrder() {
        let str = "";
        this.__postOrder(this.root, (node) => {
            str += node.key + " ";
        });
        console.log(str);
    }
    // 对以node为根的二叉搜索树进行后序遍历，递归算法
    // 传入handle函数用于输出数据
    __postOrder(node, handle) {
        if(node !== null) {
            this.__postOrder(node.left, handle);
            this.__postOrder(node.right, handle);
            handle(node);
        }
    }

    // 二分搜索树的层序遍历,广度优先遍历
    levelOrder() {
        let queue = [];
        let str = "";
        queue.push(this.root);
        while(queue.length > 0) {
            let node = queue.shift();
            str += node.key + " ";
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        console.log(str);
    }

    // 寻找二分搜索树的最小的值
    minimun() {
        let node = this.__minimum(this.root);
        return node.key;
    }
    // 返回以node为根的二分搜索树的最小键值所在的节点，递归算法
    __minimum(node) {
        if(node.left === null) return node;
        return this.__minimum(node.left);
    }

    // 寻找二分搜索树的最大的值
    maximun() {
        let node = this.__maximum(this.root);
        return node.key;
    }
    // 返回以node为根的二分搜索树的最小键值所在的节点，递归算法
    __maximum(node) {
        if(node.right === null) return node;
        return this.__maximum(node.right);
    }

    // 删除二分搜索树中最小值所在的节点
    removeMin() {
        if(this.root) this.root = this.__removeMin(this.root);
    }
    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后的二分搜索树的根
    __removeMin(node) {
        if(node.left === null) {
            let rightNode = node.right;
            this.count--;
            return rightNode;
        }
        node.left = this.__removeMin(node.left);
        return node;
    }

    // 删除二分搜索树中最小值所在的节点
    removeMax() {
        if(this.root) this.root = this.__removeMax(this.root);
    }
    // 删除掉以node为根的二分搜索树中的最大节点
    // 返回删除节点后的二分搜索树的根
    __removeMax(node) {
        if(node.right === null) {
            let leftNode = node.left;
            this.count--;
            return leftNode;
        }
        node.right = this.__removeMax(node.right);
        return node;
    }

    // 从二分搜索树种删除键值为key的节点
    remove(key) {
        this.root = this.__remove(this.root, key);
    }
    // 删除掉以node为根的二分搜索树种键值为key的节点
    // 返回删除节点后新的二分搜索树的根
    __remove(node, key) {
        if(node === null) return null;
        if(key < node.key) {
            node.left = this.__remove(node.left, key);
            return node;
        } else if(key > node.key) {
            node.right = this.__remove(node.right, key);
            return node;
        }
        else {
            // 待删除节点左子树为空的情况
            if(node.left === null) {
                let rightNode = node.right;
                this.count--;
                return rightNode;
            }
            // 待删除节点右子树为空的情况
            if(node.right === null) {
                let leftNode = node.left;
                this.count--;
                return leftNode;
            }
            // 待删除节点左右子树均不为空的情况
            // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
            // 用这个节点替代删除节点的位置
            // 获得待删除节点右子树的最小节点
            let getRMinNode = this.__minimum(node.right);
            // 创建新的节点
            let successor = new Node(getRMinNode.key, getRMinNode.value);
            this.count++;
            successor.right = this.__removeMin(node.right);
            successor.left = node.left;
            this.count--;
            return successor;
        }
    }

    // 返回二分搜索树的节点个数
    size() {
        return this.count;
    }
    // 判断二分搜索树是否为空
    isEmpty() {
        return this.count === 0;
    }
}