二叉搜索树

[wl05]

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

class BinarySearchTree {
    constructor() {
        this.root = null
    }

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

    insertNode(node, key) {
        if (node.key >= key) { // 往左边
            if (!node.left) {
                node.left = new Node(key)
            } else {
                this.insertNode(node.left, key)
            }
        } else {
            if (!node.right) {
                node.right = new Node(key)
            } else {
                this.insertNode(node.right, key)
            }
        }
    }

    /**
     * 中序遍历
     * @param callback
     */
    inOrderTraverse(callback = (val) => console.log(val)) {
        this.inOrderTraverseNode(this.root, callback)
    }

    inOrderTraverseNode(node, callback) {
        if (node) {
            this.inOrderTraverseNode(node.left, callback)
            callback(node.key)
            this.inOrderTraverseNode(node.right, callback)
        }
    }

    /**
     * 先序遍历
     * @param callback
     */
    preOrderTraverse(callback = (val) => console.log(val)) {
        this.preOrderTraverseNode(this.root, callback)
    }

    preOrderTraverseNode(node, callback) {
        if (node) {
            callback(node.key)
            this.preOrderTraverseNode(node.left, callback)
            this.preOrderTraverseNode(node.right, callback)
        }
    }

    /**
     * 后序遍历
     * @param callback
     */
    postOrderTraverse(callback = (val) => console.log(val)) {
        this.postOrderTraverseNode(this.root, callback)
    }

    postOrderTraverseNode(node, callback) {
        if (node) {
            this.postOrderTraverseNode(node.left, callback)
            this.postOrderTraverseNode(node.right, callback)
            callback(node.key)
        }
    }

    /**
     * 寻找最小值
     * @returns {*}
     */
    min() {
        return this.minNode(this.root)
    }

    minNode(node) {
        let current = node
        while (current && current.left !== null) {
            current = current.left
        }
        return current
    }

    /**
     * 寻找最大值
     * @returns {*}
     */
    max() {
        return this.maxNode(this.root)
    }

    maxNode(node) {
        let current = node
        while (current && current.right !== null) {
            current = current.right
        }
        return current
    }

    /**
     * 搜索值是否存在
     * @param key
     */
    search(key) {
        return this.searchNode(key, this.root)
    }

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

    /**
     * 删除指定元素
     * @param key
     */
    remove(key) {
        this.root = this.removeNode(key, this.root)
    }

    removeNode(key, node) {
        if (!node) {
            return null
        }

        if (node.key > key) {
            node.left = this.removeNode(key, node.left)
            return node
        } else if (node.key < key) {
            node.right = this.removeNode(key, node.right)
            return node
        } else {
            if (node.left === null && node.right === null) {
                node = null
                return node
            }

            if (node.left === null) {
                node = node.right
                return node
            }

            if (node.right === null) {
                node = node.left
                return node
            }

            const aux = this.minNode(node.right)
            node.key = aux.key
            node.right = this.removeNode(aux.key, node.right)
            return node
        }
    }

}


const tree = new BinarySearchTree()
const arr = [11, 7, 15, 5, 3, 9, 8, 10, 13, 12, 14, 20, 18, 25, 6]
arr.forEach((val) => {
    tree.insert(val)
})

const inOrderTraverse = []
tree.inOrderTraverse((val) => inOrderTraverse.push(val))
console.log("======inOrderTraverse=====")
console.log(inOrderTraverse)
console.log("=====================")
const preOrderTraverse = []
tree.preOrderTraverse((val) => preOrderTraverse.push(val))
console.log("======preOrderTraverse=====")
console.log(preOrderTraverse)
console.log("=====================")
const postOrderTraverse = []
tree.postOrderTraverse((val) => postOrderTraverse.push(val))
console.log("======postOrderTraverse=====")
console.log(postOrderTraverse)
console.log("=====================")

console.log("======min=====")
console.log(tree.min())
console.log("=====================")

console.log("======max=====")
console.log(tree.max())
console.log("=====================")

console.log("======search=====")
console.log(tree.search(1))
console.log(tree.search(8))
console.log("=====================")

console.log("======search=====")
// console.log(JSON.stringify(tree.root))
tree.remove(15)
console.log(JSON.stringify(tree.root))
console.log("=====================")