摘要：定義樹同散列表一樣，是一種非順序數據結構。一個節點及其后代可以組成一個子樹如圖中的。方法允許傳入子樹一直遍歷左側子節點，直到底部搜索特定值搜索特定值的處理與插入值的處理類似。同理，找左側子樹的最大值替換上來也可以。

樹同散列表一樣，是一種非順序數據結構。現實中樹的例子有家譜、公司組織架構圖及其它樹形結構關系。
樹由一系列節點構成，每個節點都有一個父節點（除根節點外）以及零個或多個子節點，如圖：

樹中的每一個元素叫作節點，最頂部的節點叫作根節點。至少有一個子節點的節點稱為內部節點（如圖中的7、9、15、13、20），沒有子節點的節點稱為外部節點或葉節點（如圖中的3、 6、 8、 10、 12、 14等）。一個節點可以包括祖先及后代，祖先包括父節點、祖父節點等，后代包括子節點、孫節點等。一個節點及其后代可以組成一個子樹（如圖中的13、12、14）。節點的深度指節點祖先節點的數量（如圖中的節點6的深度為3）。樹的高度指樹中節點深度的最大值。上圖中，節點中的數字稱為鍵。

二叉樹：二叉樹指節點最多只能包含兩個子節點的樹，即左側子節點與右側子節點。二叉樹有利于高效地插入、查找、刪除節點。

二叉搜索樹：二叉搜索樹是二叉樹的一種，它的左側節點的值必須大于右側節點的值，上圖就是一個二叉搜索樹。優化的二叉搜索樹包括AVL樹、紅黑樹（待完成）等

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

search(key)：在樹中查找一個鍵，如果節點存在，則返回true；如果不存在，則返回false。

inOrderTraverse：通過中序遍歷方式遍歷所有節點。

preOrderTraverse：通過先序遍歷方式遍歷所有節點。

postOrderTraverse：通過后序遍歷方式遍歷所有節點。

min：返回樹中最小的值/鍵。

max：返回樹中最大的值/鍵。

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

首選實現二叉查找樹類的骨架

// 二叉查找樹類
function BinarySearchTree() {
    // 用于實例化節點的類
    var Node = function(key){
        this.key = key; // 節點的健值
        this.left = null; // 指向左節點的指針
        this.right = null; // 指向右節點的指針
    };
    var root = null; // 將根節點置為null
}

insert方法，向樹中插入一個新的鍵。遍歷樹，將插入節點的鍵值與遍歷到的節點鍵值比較，如果前者大于后者，繼續遞歸遍歷右子節點，反之，繼續遍歷左子節點，直到找到一個空的節點，在該位置插入。

this.insert = function(key){
    var newNode = new Node(key); // 實例化一個節點
    if (root === null){
        root = newNode; // 如果樹為空，直接將該節點作為根節點
    } else {
        insertNode(root,newNode); // 插入節點（傳入根節點作為參數）
    }
};
// 插入節點的函數
var insertNode = function(node, newNode){
    // 如果插入節點的鍵值小于當前節點的鍵值
    // （第一次執行insertNode函數時，當前節點就是根節點）
    if (newNode.key < node.key){
        if (node.left === null){
            // 如果當前節點的左子節點為空，就直接在該左子節點處插入
            node.left = newNode;
        } else {
            // 如果左子節點不為空，需要繼續執行insertNode函數，
            // 將要插入的節點與左子節點的后代繼續比較，直到找到能夠插入的位置
            insertNode(node.left, newNode);
        }
    } else {
        // 如果插入節點的鍵值大于當前節點的鍵值
        // 處理過程類似，只是insertNode函數繼續比較的是右子節點
        if (node.right === null){
            node.right = newNode;
        } else {
            insertNode(node.right, newNode);
        }
    }
}

在下圖的樹中插入健值為6的節點，過程如下：

樹的遍歷指訪問樹的每一個節點，并對節點做一定操作。遍歷樹主要有三種方式：中序、先序、后序。

中序遍歷嚴格按照從小到大的方式遍歷樹，也就是優先訪問左子節點，相當于對樹進行了排序。

this.inOrderTraverse = function(callback){
    // callback用于對遍歷到的節點做操作
    inOrderTraverseNode(root, callback);
};
var inOrderTraverseNode = function (node, callback) {
    // 遍歷到node為null為止
    if (node !== null) {
        // 優先遍歷左邊節點，保證從小到大遍歷
        inOrderTraverseNode(node.left, callback);
        // 處理當前的節點
        callback(node.key);
        // 遍歷右側節點
        inOrderTraverseNode(node.right, callback);
    }
};

對下圖的樹做中序遍歷，并輸出各個節點的鍵值：

tree.inOrderTraverse(function(value){
        console.log(value);
});

依次輸出：3 5 6 7 8 9 10 11 12 13 14 15 18 20 25，
遍歷過程如圖：

先序遍歷先訪問節點本身，再遍歷其后代節點，最后遍歷其兄弟節點。它的一種應用是打印一個結構化的文檔。

this.preOrderTraverse = function(callback){
    // 同樣的，callback用于對遍歷到的節點做操作
    preOrderTraverseNode(root, callback);
};
var preOrderTraverseNode = function (node, callback) {
    // 遍歷到node為null為止
    if (node !== null) {
        callback(node.key); // 先處理當前節點
        preOrderTraverseNode(node.left, callback); // 再繼續遍歷左子節點
        preOrderTraverseNode(node.right, callback); // 最后遍歷右子節點
    }
};

用先序遍歷遍歷下圖所示的樹，并打印節點鍵值，輸出結果：11 7 5 3 6 9 8 10 15 13 12 14 20 18 25，
遍歷過程如圖：

后序遍歷先訪問節點的后代節點，再訪問節點本身。它的一種應用是計算一個目錄和它的子目錄中所有文件的大小。

this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback);
};
var postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        postOrderTraverseNode(node.left, callback); //{1}
        postOrderTraverseNode(node.right, callback); //{2}
        callback(node.key); //{3}
    }
};

可以看到，中序、先序、后序遍歷的實現方式幾乎一模一樣，只是{1}、{2}、{3}行代碼的執行順序不同。
對下圖的樹進行后序遍歷，并打印鍵值：3 6 5 8 10 9 7 12 14 13 18 25 20 15 11，
遍歷過程如圖：

在二叉搜索樹里，不管是整個樹還是其子樹，最小值一定在樹最左側的最底層。因此給定一顆樹或其子樹，只需要一直向左節點遍歷到底就行了。

this.min = function(node) {
    // min方法允許傳入子樹
    node = node || root;
    // 一直遍歷左側子節點，直到底部
    while (node && node.left !== null) {
        node = node.left;
    }
    return node;
};

搜索最大值與搜索最小值類似，只是沿著樹的右側遍歷。

this.max = function(node) {
    // min方法允許傳入子樹
    node = node || root;
    // 一直遍歷左側子節點，直到底部
    while (node && node.right !== null) {
        node = node.right;
    }
    return node;
};

搜索特定值的處理與插入值的處理類似。遍歷樹，將要搜索的值與遍歷到的節點比較，如果前者大于后者，則遞歸遍歷右側子節點，反之，則遞歸遍歷左側子節點。

this.search = function(key, node){
    // 同樣的，search方法允許在子樹中查找值
    node = node || root;
    return searchNode(key, node);
};
var searchNode = function(key, node){
    // 如果node是null，說明樹中沒有要查找的值，返回false
    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 node;
    }
};

移除節點，首先要在樹中查找到要移除的節點，再判斷該節點是否有子節點、有一個子節點或者有兩個子節點，最后分別處理。

this.remove = function(key, node){
    // 同樣的，允許僅在子樹中刪除節點
    node = node || root;
    removeNode(key, node);
};
var removeNode = function (node, key) {
    // 找到要刪除的節點
    var delete_node = this.search(node, key);
    // 如果node不存在，直接返回
    if (node === false) {
        return null;
    }
    // 第一種情況，該節點沒有子節點
    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 = this.min(node.right);
    // 替換
    node.key = aux.key;
    // 刪除最小值
    node.right = removeNode(node.right, aux.key);
    return node;
}

第三種情況的處理過程，如下圖所示。當要刪除的節點有兩個子節點時，為了不破壞樹的結構，刪除后要替補上來的節點的鍵值大小必須在已刪除節點的左、右子節點的鍵值之間，且替補上來的節點不應該有子節點，否則會產生一個節點有多個字節點的情況，因此，找右側子樹的最小值替換上來。同理，找左側子樹的最大值替換上來也可以。