Binary Search Tree

// 定义节点类
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 定义二叉搜索树类
class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    // 插入节点
    insert(value) {
        const newNode = new Node(value);

        if (this.root === null) {
            this.root = newNode;
            return this;
        }

        let current = this.root;
        while (true) {
            // 如果新值等于当前节点值
            if (value === current.value) return;

            // 如果新值小于当前节点值，往左走
            if (value < current.value) {
                if (current.left === null) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            }
            // 如果新值大于当前节点值，往右走
            else {
                if (current.right === null) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }

    // 查找节点
    find(value) {
        if (!this.root) return false;

        let current = this.root;
        while (current) {
            if (value === current.value) return current;
            if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    // 判断是否存在某个值
    contains(value) {
        return this.find(value) !== false;
    }

    // 广度优先遍历（BFS）
    BFS() {
        let node = this.root;
        const data = [];
        const queue = [];
        queue.push(node);

        while (queue.length) {
            node = queue.shift();
            data.push(node.value);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        return data;
    }

    // 深度优先遍历 - 前序遍历（DFS PreOrder）
    DFSPreOrder() {
        const data = [];

        function traverse(node) {
            data.push(node.value);
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
        }

        traverse(this.root);
        return data;
    }

    // 深度优先遍历 - 中序遍历（DFS InOrder）
    DFSInOrder() {
        const data = [];

        function traverse(node) {
            if (node.left) traverse(node.left);
            data.push(node.value);
            if (node.right) traverse(node.right);
        }

        traverse(this.root);
        return data;
    }

    // 深度优先遍历 - 后序遍历（DFS PostOrder）
    DFSPostOrder() {
        const data = [];

        function traverse(node) {
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
            data.push(node.value);
        }

        traverse(this.root);
        return data;
    }

    // 获取最小值
    getMin() {
        if (!this.root) return null;
        let current = this.root;
        while (current.left) {
            current = current.left;
        }
        return current.value;
    }

    // 获取最大值
    getMax() {
        if (!this.root) return null;
        let current = this.root;
        while (current.right) {
            current = current.right;
        }
        return current.value;
    }
}