二叉搜索树 数据结构实现

BinarySearchTree.js

/* 二叉搜索树 数据结构实现 */


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

/* 二叉搜索树 */
class BinarySearchTree {

    constructor() {
        // 根节点
        this.root = null;
    }

    insert(key) {

        let newNode = new TreeNode(key);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this._insertNode(this.root, newNode);
        }
    }

    /* 将新节点插入正确的位置 */
    _insertNode(node, newNode) {
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this._insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this._insertNode(node.right, newNode);
            }
        }
    }


    search(key) {
        return this._searchNode(this.root, key);
    }

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

    /* 中序遍历 */
    inOrderTraverse(callback) {
        this._inOrderTraverseNode(this.root, callback)
    }

    _inOrderTraverseNode(node, callback) {
        if (node !== null) {
            this._inOrderTraverseNode(node.left, callback);
            callback(node.key);
            this._inOrderTraverseNode(node.right, callback);
        }
    }

    /* 先序遍历 */
    preOrderTraverse(callback) {
        this._preOrderTraverseNode(this.root, callback);
    }

    _preOrderTraverseNode(node, callback) {
        if (node !== null) {
            callback(node.key);
            this._preOrderTraverseNode(node.left, callback);
            this._preOrderTraverseNode(node.right, callback);
        }
    }

    /* 后序遍历 */
    postOrderTraverse(callback) {
        this._postOrderTraverseNode(this.root, callback);
    }

    _postOrderTraverseNode(node, callback) {
        if (node !== null) {
            this._postOrderTraverseNode(node.left, callback);
            this._postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    }

    min() {
        return this._minNode(this.root);
    }

    _minNode(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }

            return node.key;
        }
        return null;
    }

    max() {

        return this._maxNode(this.root);

    }

    _maxNode(node) {
        if (node) {
            while (node && node.right !== null) {
                node = node.right;
            }

            return node.key;
        }

        return null;
    }

    remove(key) {

        this.root = this._removeNode(this.root, key)
    }

    _removeNode(node, key) {

        if (node === null) {
            return null;
        }
        if (key < node.key) {
            node.left = this._removeNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = this._removeNode(node.right, key);
        } else {
            // 键等于node.key
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }
            if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }

            // 有两个节点
            let aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = this._removeNode(node.right, aux.key);
            return node;
        }


    }

    findMinNode(node) {
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    }
}

var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

// tree.inOrderTraverse((dt)=>console.log(dt))