树

树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。

树的定义

树由一组以边连接的节点组成。公司的组织结构图就是一个树的例子，参见图下

先序遍历 :

function preOrder(node) {
    if (node != null) {
        console.log(node.show() + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

后序遍历 :

function postOrder(node) {
    if (!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show() + " ");
    }
}

查找最大值和最小值

即找到最左边的节点和最右边的节点

    getMin() {
        let current = this.root;
        while (true) {
            if (current.left !== null) {
                current = current.left
            } else {
                break;
            }
        }
        return current.data;
    }
    getMax() {
        let current = this.root;
        while (true) {
            if (current.right !== null) {
                current = current.right
            } else {
                break;
            }
        }
        return current.data;
    }

从二叉查找树上删除节点

这里比较复杂，我们要边看代码边画图来讲解。

remove(data) {
    this.root = this.removeNode(this.root, data);
}
removeNode(node, data) {
    if (node == null) return null;

    if (data == node.data) {
        if (node.left == null && node.right == null) return null;
        // 没有左子节点的节点
        if (node.left == null) return node.right;
        // 没有右子节点的节点
        if (node.right == null) return node.left;
        // 有两个子节点的节点
        var tempNode = this.getMin(node.right);
        node.data = tempNode.data;
        node.right = this.removeNode(node.right, tempNode.data);
        return node;
    } else if (data < node.data) {
        node.left = this.removeNode(node.left, data);
        return node;
    } else {
        node.right = this.removeNode(node.right, data);
        return node;
    }
}

首先我们构建一个这样子的二叉树

bst.insert(15);
bst.insert(10);
bst.insert(12);
bst.insert(5);
bst.insert(8);
bst.insert(11);
bst.insert(14);
bst.insert(7);
bst.insert(4);
bst.insert(13);

bst.remove(10)

首先我们要删除10的节点，因为10节点的left已经有节点了，右边也有节点了，右边节点的数值肯定是比左边大的，所以我们在右边找到最小的节点，将这个最小的节点data复制给当前的10。此时10节点被11覆盖，但是原来的11还存在与树中，所以我们此时要删除11节点，按照之前的方法再进行查找一次，知道运行结束。