定义
- 二叉树
二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于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 是否有根节点，如果没有，则这是一个新树，这个需要插入的数据就成为了根节点，这个方法就完成了；否则，进入下一步。
设置根节点为当前节点。
如果待插入数据小于当前节点的数据，则设置新的当前节点为原节点的左节点；反之，执行第4步。
如果当前节点的左节点为null，那么就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
设置新的当前节点为原节点的右节点。
如果当前节点的右节点为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()+"");
}
}
