概念
树是由N个结点和N-1条边组成的集合。其中的一个节点做为根，每个节点有0个或多个节点。将没有父节点的称作为根节点，其它的节点为子节点。如下所示：
A为要节点，B,C,D是A的子节点，一层一层往下生成结点，看上去就像一颗树。
常见的树二叉树，二叉搜索树、2-3树、红黑树。这里主要介绍下比较特殊的二叉搜索树。
二叉搜索树
二叉树是每个节点最多有两个节点的树，子节点通常称为左子树和右子树。二叉树中有个比较特殊的树，就是二叉搜索树，主要特点是：左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。如下所示：
创建二叉搜索树
首先创建一个BinarySearchTree类，并申明一个节点类和一个根节点，如下所示：
var Node = function (data) {
this.data = data;
this.left = null;
this.right = null;
}
var root = null;
Node作为辅助类，用于定义数据项、左子树、右子树、定义root作为要节点。
二叉搜索树基本方法
实现二叉搜索树主要包括节点的插入、搜索、删除、前序遍历、中序遍历、后序遍历、获取最大节点、获取最小节点等，基本的实现代码如下所示：
/*
* 插入节点
* */
this.insert = function (data) {
}
/*
* 查找
* */
this.search = function (data) {
}
/*
* 中序遍历
* */
this.inOrderTraverse = function () {
}
/*
* 前序遍历
* */
this.preOrderTraverse = function () {
}
/*
* 后序遍历
* */
this.postOrderTraverse = function () {
}
/*
* 删除
* */
this.remove = function (data) {
}
/*
* 获取最大的节点
* */
this.getMax = function () {
}
/*
* 获取最小节点
* */
this.getMin = function () {
}
插入节点
二叉树的插入相对数组和链表来说要复杂一些，主要采取递归的方法来插入，对于新插入的节点，首先和根节点上的节点进行对比，如果小于根节点上的值就往左边查找，一层一层的先对比然后再插入。同事右节点也是用一样的方式进行查找和插入。如下所示：
/*
* 插入节点
* */
this.insert = function (data) {
var node = new Node(data);
if (!root) {
root = node;
}else{
this.insertNode(root,data);
}
}
/*
* 递归插入
* */
this.insertNode = function (node,data) {
var curNode = null;
if(data > node.data){//往右边插
curNode = node.right;
if (curNode){
this.insertNode(curNode,data);
}else{
node.right = new Node(data);
}
}else{//往左边插
curNode = node.left;
if (curNode){
this.insertNode(curNode,data);
}else{
node.left = new Node(data);
}
}
}
中序遍历
中序遍历是指先遍历左边的节点，然后再遍历父节点，再遍历右节点。具体的代码如下所示：
/*
* 中序遍历
* */
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root,callback);
}
var inOrderTraverseNode = function (node,callback) {
if(node){
inOrderTraverseNode(node.left,callback);//先遍历左边
callback(node.data);//打印中间的节点
inOrderTraverseNode(node.right,callback);//最后遍历右边
}
}
前序遍历
前序遍历是指先遍历根节点，再遍历左边的节点，最后再遍历父节点。具体的代码如下所示：
/*
* 前序遍历
* */
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root,callback);
}
var preOrderTraverseNode = function (node,callback) {
if(node){
callback(node.data);
preOrderTraverseNode(node.left,callback);//遍历左边
preOrderTraverseNode(node.right,callback);//遍历右边
}
}
后序遍历
后序遍历是指先遍历左边的节点，然后再遍历右节点，再遍历根节点。具体的代码如下所示：
/*
* 后序遍历
* */
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root,callback)
}
var postOrderTraverseNode = function (node,callback) {
if(node){
postOrderTraverseNode(node.left,callback);//遍历左边
postOrderTraverseNode(node.right,callback);//遍历右边
callback(node.data);
}
}
查找
二叉搜索树的查找主要包括查找最大节点、最小节点、指定节点等，查找一个结点的方法是比较简单的，通过二叉搜索树本身具有的特性，很容易查找到对应的节点。
查找最小节点
查找最小节点，主要是在节点的左边进行查找，通过遍历来查找节点的左节点，直到找到最后一个节点，就为最小的节点，具体的代码如下所示：
/*
* 获取最小节点
* */
this.getMin = function () {
return minNode(root);
}
var minNode = function (node) {
if(node){
while (node && node.left){
node = node.left;
}
return node.data;
}
return null;
}
查找最大节点
查找最大节点，主要是在节点的右边进行查找，通过遍历来查找节点的右节点，直到找到最后一个节点，就为最大的节点，具体的代码如下所示：
/*
* 获取最大的节点
* */
this.getMax = function () {
return maxNode(root)
}
var maxNode = function (node) {
if(node){
while (node && node.right){
node = node.right;
}
return node.data;
}
return node.data;
}
查找指定节点
查找指定节点也比较容易，主要是根据节点上的数值跟指定节点上的数值进行对比，如果大于根节点，就往右查找，如果小于根节点就往左查找，如果相等，直接返回，具体的代码如下所示：
/*
* 查找
* */
this.search = function (data) {
return searchtNode(root,data)
}
var searchtNode = function (node,data) {
if(!node){
return false;
}
if(data > node.data){//往右边搜索
return searchtNode(node.right,data);
}else if(data < node.data){//往左边搜索
return searchtNode(node.left,data);
}else{
return true;
}
return false;
}
删除节点
删除节点算是比较复杂的，因为要考虑两种情况，如果删除的节点为叶子节点，直接删除就可以了。但如果是删除父节点上的数据，删除后就破坏了原有树，需要对树进行重新构造。具体的实现可查看代码中的注释。
/*
* 删除
* */
this.remove = function (data) {
root = removeNode(root,data)
}
var removeNode = function (node,data) {
if(!node){
return null;
}
if (node.data < data){//在右节点上的情况
node.right = removeNode(node.right,data);
return node;
}else if(node.data > data){//在左节点上的情况
node.left = removeNode(node.left,data);
return node;
}else {//相等的情况
//左节点和右节点都为空的情况
if(node.right === null && node.left === null){
node = null;
return node;
}else if(node.right === null){//没有右节点的情况
node = node.left;
return node;
}else if(node.left === null){//没有左节点的情况
node = node.right;
return node;
}else{//同时具有左节点和子节点的情况
var rightMinNode = getMinNode(node.right);//找出右子树中最小的节点
node.data = rightMinNode.data;//将最小节点的值赋值到当前节点
node.right = removeNode(node.right,rightMinNode.data);//删除右树中最小的节点
return node;
}
}
}
var getMinNode = function (node) {
if(node){
while (node && node.left){
node = node.left;
}
return node;
}
return null;
}
