ext-2.实现二叉排序树

class BstNode {
    constructor(val, left = null, right = null) {
        this.val = val
        this.left = left
        this.right = right
    }
    print() {
        console.log(this.val);
    }
}

// 二叉搜索树，左节点 < 父节点 < 右节点
class BinarySearchTree {
    constructor() {
        this.root = null // 根节点
    }

    // 插入节点
    insert(val) {
        const node = new BstNode(val)
        if (!this.root) {
            this.root = node
            return
        }
        // 遍历，通过比较val大小找到合适的位置插入新节点
        let cur = this.root
        while (true) {
            // 比父节点小时，新节点位置一定在父节点左侧
            // 比父节点大时，新节点位置一定在父节点右侧
            if (val < cur.val) {
                if (cur.left === null) {
                    cur.left = node
                    break
                }
                cur = cur.left // 继续往左侧找
            } else {
                if (cur.right === null) {
                    cur.right = node
                    break
                }
                cur = cur.right // 继续往右侧找
            }
        }
    }
    // 查找节点
    find(val) {
        let cur = this.root
        while (cur) {
            if (val === cur.val) {
                return cur
            } else if (val < cur.val) {
                cur = cur.left
            } else if (val > cur.val) {
                cur = cur.right
            }
        }
        return null
    }
    // 查找节点，递归实现
    find2(val, node) {
        if (!node) {
            return null
        }
        if (val === node.val) {
            return node
        } else if (val < node.val) {
            return this.find2(val, node.left)
        } else if (val > node.val) {
            return this.find2(val, node.right)
        }
    }
    // 删除节点
    // 1.如果待删除的节点是叶子节点，那么只需要将它的父节点指向null
    // 2.如果待删除的节点包含一个子节点，那么将它的父节点指向它的子节点
    // 3.如果待删除的节点包含两个子节点，那么我们可以采用两种方式，一种是查找待删除节点左子树上的最大值，一种是查找待删除节点右子树上的最小值。
    //   我们采取后者，找到最小值后，将这个最小值节点的值赋给待删除节点，然后再删除这个最小值节点（采用递归）
    remove(node, val) {
        if (!node) {
            return null
        }
        // 先寻找待删除节点
        if (val < node.val) {
            node.left = this.remove(node.left, val)
            return node
        } else if (val > node.val) {
            node.right = this.remove(node.right, val)
            return node
        } else if (val === node.val) { // 找到待删除的节点了
            // 如果是叶子节点
            if (node.left === null && node.right === null) {
                return null
            } else if (node.right === null) { // 只含左节点
                return node.left
            } else if (node.left === null) { // 只含右节点
                return node.right
            } else if (node.left !== null && node.right !== null) { // 含两个子节点
                // 找到右子树的最小值
                let tempNode = this.getMin(node.right)
                // 将最小值节点
                node.val = tempNode.val
                // 然后删除这个最小值节点
                node.right = this.remove(node.right, tempNode.val)
                return node
            }
        }
    }

    // 前序遍历,中左右
    preOrder(node) {
        if (node) {
            node.print() // 中
            this.preOrder(node.left) // 左
            this.preOrder(node.right) // 右
        }
    }
    // 中序遍历，左中右
    inOrder(node) {
        if (node) {
            this.inOrder(node.left) // 左
            node.print() // 中
            this.inOrder(node.right) // 右
        }
    }
    // 后序遍历，左右中
    postOrder(node) {
        if (node) {
            this.postOrder(node.left) // 左
            this.postOrder(node.right) // 右
            node.print() // 中
        }
    }

    // 广度优先遍历，利用队列实现
    levelOrder() {
        if (!this.root) {
            return
        }
        let queue = []
        let res = []

        queue.push(this.root)
        while (queue.length) {
            // 从队列头取出节点
            let node = queue.shift()
            res.push(node.val)
            // 从队尾插入子节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        return res
    }
    levelOrder2() {
        let queue = []
        let res = []
        queue.push(this.root)
        while (queue.length) {
            let len = queue.length // 当前层的节点数
            // 循环把当前层的节点拿出来，再把左节点和右节点插入队列
            for (let i = 0; i < len; i++) {
                let node = queue.shift()
                res.push(node.val)
                if (node.left) {
                    queue.push(node.left)
                }
                if (node.right) {
                    queue.push(node.right)
                }
            }
        }
        return res
    }
    // 获取最小值,在左子树最后一层最左边的节点
    getMin(node) {
        node = node || this.root
        let curr = node
        while (curr.left !== null) {
            curr = curr.left
        }
        return curr
    }
    // 用递归实现
    getMin2(node) {
        node = node || this.root
        if (node.left === null) {
            return node
        } else {
            return this.getMin2(node.left)
        }
    }
    // 获取最大值，在右子树最后一层最右边的节点
    getMax(node) {
        node = node || this.root
        let curr = node
        while (curr) {
            if (curr.right === null) {
                return curr
            }
            curr = curr.right
        }
    }
    // 树的深度
    getDeep(node, deep) {
        deep = deep || 0
        if (node === null) {
            return deep
        }
        deep++
        let leftDeep = this.getDeep(node.left, deep) // 左子树深度
        let rightDeep = this.getDeep(node.right, deep) // 右子树深度
        return Math.max(leftDeep, rightDeep)
    }
    // 非递归
    getDeep2() {
        let queue = []
        let count = 0
        queue.push(this.root)
        while (queue.length) {
            let len = queue.length // 当前层的节点数
            for (let i = 0; i < len; i++) {
                let node = queue.shift()
                if (node.left) {
                    queue.push(node.left)
                }
                if (node.right) {
                    queue.push(node.right)
                }
            }
            count++
        }
        return count
    }
}

const tree = new BinarySearchTree()
tree.insert(3)
tree.insert(8)
tree.insert(1)
tree.insert(2)
tree.insert(5)
tree.insert(7)
tree.insert(6)
tree.insert(0)

// console.log(tree);
// tree.inOrder(tree.root)
// tree.preOrder(tree.root)
// tree.postOrder(tree.root)
// console.log(tree.getMin())
// console.log(tree.getMax())
// console.log(tree.getDeep(tree.root))
// console.log(tree.find(5))
tree.remove(tree.root, 5)
console.log(tree.find(8))