二叉查找树（Binary Search Tree）

定义

• 二叉树

二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

• 二叉查找树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

实现二叉查找树

BST 的基本方法

要实现二叉查找树，首先实现 Node 类，Node 类定义如下：

function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

我们可以定义一个二叉查找树类（BST）如下：

// BST类
function BST() {
    this.root = null;
    this.insert = insert; // 插入数据方法
}

接着我们实现一个 insert 方法，实现这个方法的思路：

首先检查 BST 是否有根节点，如果没有，则这是一个新树，这个需要插入的数据就成为了根节点，这个方法就完成了；否则，进入下一步。

1. 设置根节点为当前节点。

2. 如果待插入数据小于当前节点的数据，则设置新的当前节点为原节点的左节点；反之，执行第4步。

3. 如果当前节点的左节点为null，那么就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。

4. 设置新的当前节点为原节点的右节点。

5. 如果当前节点的右节点为null，那么就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。

所以，我们现在可以实现 insert 方法如下：

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

遍历二叉查找树

BST 类目前已经初步成型，我们已经可以插入数据，现在我们还需要有能力遍历
BST ， 我们有三种遍历 BST 的方式： 中序、先序和后序。

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

则 BST 类现在可以写成如下：

// BST类
function BST() {
    this.root = null;
    this.insert = insert; // 插入数据方法
    this.inOrder = inOrder; // 中序遍历
    this.preOrder = preOrder; // 先序遍历
    this.postOrder = postOrder; // 后序遍历
}

现在我们首先实现中序遍历方法如下：

function inOrder(node) {
    if(node) {
        inOrder(node.left);
        console.log(node.show() + " ");
        inOrder(node.right);
    }
}

先序遍历如下：

// 先序遍历 
function  preOrder (node) {
    if (node) {
        console.log(node.show()+"");
        preOrder(node.left);
        preOrder(node.right);
    }
}

后序遍历如下：

// 后序遍历
function postOrder(node) {
    if (node) {
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show()+"");
    }
}