摘要：簡介二叉樹是一種非常重要的數據結構，很多其它數據結構都是基于二叉樹的基礎演變而來的。二叉搜索樹是二叉樹的一種，但是它只允許你在左側節點存儲比父節點小的值，在右側節點存儲比父節點大或者等于的值。樹的高度，樹的高度體現為節點深度的最大值。

二叉樹是一種非常重要的數據結構，很多其它數據結構都是基于二叉樹的基礎演變而來的。

對于二叉樹，有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及后序三種遍歷方法，廣度遍歷即我們平常所說的層次遍歷。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現樹的三種遍歷不僅容易理解而且代碼很簡潔，而對于廣度遍歷來說，需要其他數據結構的支撐，比如堆了。

二叉樹中的節點最多只能有兩個節點：一個是左側子節點，另一個是右側子節點。
二叉搜索樹（BST）是二叉樹的一種，但是它只允許你在左側節點存儲（比父節點）小的值，在右側節點存儲（比父節點）大（或者等于）的值。

樹中的每個元素，都叫做節點。從節點延伸而下的，叫子節點。
樹頂部的節點叫根節點。每棵樹只有一個根節點。
在節點中，有子節點的節點也稱為內部節點，沒有的話則被稱為外部節點或者葉節點。
同時在節點中是有祖先和后代關系的，比如節點9的祖先就有13,7,6,15四個。

深度: 節點的深度取決于其祖先的數量，節點9的深度就是4。
樹的高度，樹的高度體現為節點深度的最大值。
比如上圖，節點深度最大值為4，則樹的高度為4。

下面我們先來簡單實現一個二叉搜索樹類，并包含以下的方法：

insert(key): 向樹中插入一個新的鍵

min(): 返回樹中最小的值

max(): 返回樹中最大的值

search(key): 搜索某個值，在樹中則返回true

remove(key): 從樹中移除某個鍵

代碼如下：

function BinarySearchTree() {
    var Node = function(key){ //數據結構類
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null; //根節點
    this.insert = function(key){ //插入新的鍵
        var newNode = new Node(key);
        //special case - first element
        if (root === null){ //根節點為空，作為根節點
            root = newNode;
        } else {
            insertNode(root,newNode); //插入節點操作
        }
    };
    var insertNode = function(node, newNode){
        if (newNode.key < node.key){
            if (node.left === null){ //如果沒有左側節點就插入新的節點
                node.left = newNode;
            } else { //有的話遞歸
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null){  //如果沒有右側節點就插入新的節點
                node.right = newNode;
            } else { //有的話遞歸
                insertNode(node.right, newNode);
            }
        }
    };
    this.getRoot = function(){
        return root;
    };
    this.search = function(key){  //搜索鍵
        return searchNode(root, key); //搜索操作
    };
    var searchNode = function(node, key){
        if (node === null){
            return false;
        }
        if (key < node.key){ //如果小于繼續從左邊搜索
            return searchNode(node.left, key);
        } else if (key > node.key){ //如果大于繼續從右邊搜索
            return searchNode(node.right, key);
        } else { //命中
            return true;
        }
    };
    this.min = function() { //找最小鍵
        return minNode(root);
    };
    var minNode = function (node) {
        if (node){
            while (node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    };
    this.max = function() { //找最大鍵
        return maxNode(root);
    };
    var maxNode = function (node) {
        if (node){
            while (node && node.right !== null) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    };
    this.remove = function(element){
        root = removeNode(root, element);
    };
    var findMinNode = function(node){ //返回節點
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    };
    var removeNode = function(node, element){ //移除一個節點
        if (node === null){
            return null;
        }
        if (element < node.key){
            node.left = removeNode(node.left, element);
            return node;
        } else if (element > node.key){
            node.right = removeNode(node.right, element);
            return node;
        } else { //命中后分三種情況         
            //移除葉子節點，即該節點沒有左側或者右側子節點的葉結點
            if (node.left === null && node.right === null){
                node = null;
                return node;
            }
            //移除有一個左側或者右側子節點的節點
            if (node.left === null){
                node = node.right; //把引用改為子節點的引用，下同
                return node;
            } else if (node.right === null){
                node = node.left;
                return node;
            }
            //移除有兩個子節點的節點
            var aux = findMinNode(node.right); //找到右邊子樹的最小節點
            node.key = aux.key; //改變節點的鍵，更新節點的值
            node.right = removeNode(node.right, aux.key); //移除有相同鍵的節點
            return node; //返回更新后節點的引用
        }
    };
}

前序遍歷：根結點 ---> 左子樹 ---> 右子樹
中序遍歷：左子樹---> 根結點 ---> 右子樹
后序遍歷：左子樹 ---> 右子樹 ---> 根結點
層次遍歷：只需按層次遍歷即可

例如，求下面二叉樹的各種遍歷

前序遍歷：1 2 4 5 7 8 3 6
中序遍歷：4 2 7 5 8 1 3 6
后序遍歷：4 7 8 5 2 6 3 1
層次遍歷：1 2 3 4 5 6 7 8

代碼實現如下：

/**
 * 先序遍歷
 * @param {any} callback 回調函數
 */
this.preOrderTranverse = function (callback) {
    preOrderTranverseNode(root, callback)
}
var preOrderTranverseNode = function (node, callback) {
    if (node !== null) {
        callback && callback(node.key);
        preOrderTranverseNode(node.left, callback);
        preOrderTranverseNode(node.right, callback);
    }
}

代碼實現如下：
/**

中序遍歷

@param {any} callback 回調函數
*/

this.inOrderTraverse = function (callback) {

inOrderTraverseNode(root, callback)

}
var inOrderTraverseNode = function (node, callback) {

if (node !== null) {
    inOrderTraverseNode(node.left, callback);
    callback && callback(node.key)
    inOrderTraverseNode(node.right, callback);
}

}

代碼實現如下：

 /**
  * 后序遍歷
  * @param {any} callback 回調函數
  */
 this.postOrderTranverse = function (callback) {
     postOrderTranverseNode(root, callback);
 }
 var postOrderTranverseNode = function (node, callback) {
     if (node !== null) {
         postOrderTranverseNode(node.left, callback);
         postOrderTranverseNode(node.right, callback);
         callback(node.key);
     }
 }