数据结构的那些事（三）

继续前面系列，这一章主要分析二叉树和二叉查找树。 树的定义：

我们先来了解一下有关树的术语：一棵树最上面的节点称为根节点，如果下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。没有任何子节点的节点称为叶子节点。

二叉树是一种特殊的树。它的子节点个数不超过两个，一个父节点左边的称为左节点，右边的称为右节点。

正是因为二叉树的这些特性，让它的查找效率极高，从而引出了 二叉查找树 ，左子节点保存相对父节点较小的值，右节点保存相对父节点较大的值

接下来，我们来一起实现这个二叉查找树。 我们要定义一个对象Node来表示这棵树：

function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}
function show() {
    return this.data;
}
复制代码

这个Node对象可以保存数据，也保存和其他节点的链接。 现在，可以创建一个类，用来表示二叉查找树，简称 BST 。

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
}
function insert(data) {
    var n = new Node(data, null, null);
    if (this.root == null) {
        this.root = n;
    }else {
        var current = this.root;
        var parent;
        while (true) {
            parent = current;
            if (data < current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = n;
                    break;
            }
        }else {
            current = current.right;
                if (current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}
复制代码

这个BST的 insert 方法有点复杂，我们来分析下都做了那些事：

（1）首先创建一个没有左右子节点的Node实例；

（2）如果这是第一个插入BST的节点就作为根节点；

（3）不是的话，获取这个根节点赋值给current变量往下走

（4）进入一个循环判断，找到正确的插入点会跳出循环

（5）如果待插入节点保存的数据小于当前节点，则设新的当前为原节点的左节点

（6）如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环，反之，继续往下循环查找。

（7）查找右节点也类似。

有了insert方法我们就能插入节点创建一个二叉查找树的数据结构。

有了二叉查找树，接下来我们该考虑怎么遍历这个BST

有三种遍历BST的方法：分别是中序，先序和后序，其中中序遍历最为常见。

我们先来看下中序遍历是如何工作的：

有了这个思路我们就可以写出这个中序遍历的方法：

function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);
        putstr(node.show() + " ");
        inOrder(node.right);
    }
}
复制代码

这里用到了 递归 的思想，该方法需要以升序访问树中所有节点，所以它首先会递归查找到最下面的左叶子节点，然后访问左子树，再访问根节点，最后访问右子树。

先序遍历：

上面是先序遍历的访问路径， 根据上面的思路可以写出这样的代码：

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

复制代码

注意：中序遍历和先序遍历的唯一区别，就是if语句中的代码顺序。

最后是后序遍历

function postOrder(node){
    if(!(node == null)){
        postOrder(node.left);
        postOrder(node.right);
        putstr(node.show() + " ")
    }
}
复制代码

查找最小值，最大值和给定值

因为较小的值总是在左子节点，在BST上查找最小值，只要遍历左子树，直到找到最后一个节点：

function getMin(){
    let current = this.root;
    while(!(current.left == null)){
        current = current.left;
    }
    return current.data
}
复制代码

查找最大值只要遍历右子树直到找到最后一个节点即可。

查找给定值，稍微麻烦点，我们需要将给定值和当前节点进行比较，来决定是左遍历还是右遍历。

function find(data){
    let current = this.root;
    while(current !=null){
        if(current.data == data){
            return current
        }
        else if(data<current.data){
            current = current.left
        }else{
            current = current.right
        }
    }
    return null;
}
复制代码

如果找到给定值，返回给定值，找不到会返回null

从二叉树上删除节点

从BST上删除节点的操作最复杂，因为我们要考虑几种情况：

（1）是否包含待删除的数据

（2）待删除节点是否是叶子节点

（3）待删除节点是否只包含一个子节点

（4）待删除节点是否包含两个子节点

为了方便，我们将删除节点拆分成两个方法，remove()方法接收待删除的数据，removeNode()方法删除节点:

function remove(data){
    root = removeNode(this.root, data)
}

function 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
        }
        //有两个子节点
        let tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node
    }
    else if (data < node.data){
        node.left = removeNode(node.left, data);
    }
    else {
        node.right = removeNode(node.right, data);
    }
}
复制代码

上面，我们就完成了二叉查找树的增删改查。

我们之前有说到：

数组的搜索比较方便，可以直接用下标，但删除或者插入某些元素就比较麻烦。 链表 与之相反，删除和插入元素很快，但查找很慢。 二叉查找树 就既有链表的好处，也有数组的好处。 在处理大批量的动态的数据是比较有用。

但是，人无完人，当考虑到二叉查找树的随机性，在最坏的情况下（ 就是那种一条腿的感觉 ），时间复杂度和顺序查找差不多，这就让人有点无法接受了。

究其原因，还是因为左右子树相差悬殊导致的，于是有人通过算法研究出了平衡二叉查找树 ，也就是 红黑树

就长这样，这个要讲清楚又是一个大东西，博主也没完全研究明白，等后续有时间弄清楚了奉贤给大家0.0