数据结构--树

const { log } = console;

function BinarySearchTree() {

    let root = null;
    //向树中插入一个新的键
    this.insert = key => {
        const node = new Node(key);
        if (root === null) {
            root = node;
        } else {
            _insertNode(root, node);
        }

    }
    //在树中查找一个键，如果节点存在，则返回 true ；如果不存在，则返回false 
    this.search = key => {
        return _searchNode(root, key);

    }
    //通过中序遍历方式遍历所有节点
    this.inOrderTraverse = (callback) => {
        _inOrderTraverseNode(root, callback);

    }
    //通过先序遍历方式遍历所有节点
    this.preOrderTraverse = (callback) => {

        _preOrderTraverseNode(root, callback);

    }

    //通过后序遍历方式遍历所有节点
    this.postOrderTraverse = (callback) => {

        _postOrderTraverseNode(root, callback);
    }
    //返回树中最小的值/键
    this.min = () => {
        return _minNode(root);

    }

    //返回树中最大的值/键
    this.max = () => {

        return _maxNode(root);

    }
    //从树中移除某个键
    this.remove = key => {
        root = _removeNode(root, key);

    }

    function _insertNode(node, newNode) {

        if (node.key > newNode.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                _insertNode(node.left, newNode)
            }

        } else {

            if (node.right === null) {
                node.right = newNode;
            } else {
                _insertNode(node.right, newNode)
            }
        }

    }


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

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

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

    function _minNode(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    }
    function _findMinNode(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node;
        }
        return null;
    }

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

    function _removeNode(node, key) {

        if (node === null) {
            return null;
        }
        if (key < node.key) {
            node.left = _removeNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = _removeNode(node.right, key);
            return node;
        } 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 minNode = _findMinNode(node.right);
            node.key = minNode.key;
            node.right = _removeNode(node.right, minNode.key);
            return node;
        }
    };

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


}


function printNode(value) {

    log(value);
}

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


const 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(printNode);
tree.preOrderTraverse(printNode);
tree.postOrderTraverse(printNode);
log(tree.min());
log(tree.max());
log(tree.search(6))
tree.remove(6)
log(tree.search(6))