bst2.js

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

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

    insert(key) {
        let node = new Node(key);

        if (!this.root) {
            this.root = node;
        } else {
            this._insert(node, this.root);
        }
    }

    _insert(node, parent) {
        if (node.key === parent.key) {
            throw new Error('same node key!');
        }

        if (node.key < parent.key) {
            if (!parent.left) {
                parent.left = node;
            } else {
                this._insert(node, parent.left);
            }
        } else {
            if (!parent.right) {
                parent.right = node;
            } else {
                this._insert(node, parent.right);
            }
        }
    }

    inOrder(node, cb) {
        if (node) {
            this.inOrder(node.left, cb);
            cb && cb(node.key);
            this.inOrder(node.right, cb);
        }
    }

    preOrder(node, cb) {
        if (node) {
            cb && cb(node.key);
            this.preOrder(node.left, cb);
            this.preOrder(node.right, cb);
        }
    }

    postOrder(node, cb) {
        if (node) {
            this.postOrder(node.left, cb);
            this.postOrder(node.right, cb);
            cb && cb(node.key);
        }
    }

    getMin() {
        let node = this.root;
        if (node) {
            while(node.left) {
                node = node.left;
            }
            return node.key;
        } else {
            return null;
        }
    }

    getMax() {
        let node = this.root;
        if (node) {
            while(node.right) {
                node = node.right;
            }
            return node.key;
        } else {
            return null;
        }
    }

    search(key) {
        if (!this.root) {
            return false;
        }

        let node = this.root;
        return this._search(key, node);
    }

    _search(key, node) {
        if (!node) {
            return false;
        }

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

    get length() {
        let node = this.root;
        if (node) {
            return this._length(node);
        } else {
            return 0;
        }
    }

    _length(node) {
        let length = 0;

        if (node) {
            length++;
            if (node.left) {
                length += this._length(node.left);
            }

            if (node.right) {
                length += this._length(node.right);
            }
        }

        return length;
    }

    /**
     * @name bfc 广度遍历
     * 
     * @param {any} node 
     * @param {any} cb 
     * @returns 
     * 
     * @memberOf BST
     */
    bfc(node, cb) {
        if (node) {
            let nodeQueue = [],
                keyQueue = [],
                current = 0;

            nodeQueue.push(node);

            while(keyQueue.length < nodeQueue.length) {
                keyQueue.push(nodeQueue[current].key);
                if (nodeQueue[current].left) {
                    nodeQueue.push(nodeQueue[current].left);
                }
                if (nodeQueue[current].right) {
                    nodeQueue.push(nodeQueue[current].right);
                }
                current++;
            }
            return keyQueue;
        }
    }
}

O(∩_∩)O~~