摘要：定義樹(shù)同散列表一樣，是一種非順序數(shù)據(jù)結(jié)構(gòu)。一個(gè)節(jié)點(diǎn)及其后代可以組成一個(gè)子樹(shù)如圖中的。方法允許傳入子樹(shù)一直遍歷左側(cè)子節(jié)點(diǎn)，直到底部搜索特定值搜索特定值的處理與插入值的處理類似。同理，找左側(cè)子樹(shù)的最大值替換上來(lái)也可以。

樹(shù)同散列表一樣，是一種非順序數(shù)據(jù)結(jié)構(gòu)。現(xiàn)實(shí)中樹(shù)的例子有家譜、公司組織架構(gòu)圖及其它樹(shù)形結(jié)構(gòu)關(guān)系。
樹(shù)由一系列節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)（除根節(jié)點(diǎn)外）以及零個(gè)或多個(gè)子節(jié)點(diǎn)，如圖：

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

二叉樹(shù)：二叉樹(shù)指節(jié)點(diǎn)最多只能包含兩個(gè)子節(jié)點(diǎn)的樹(shù)，即左側(cè)子節(jié)點(diǎn)與右側(cè)子節(jié)點(diǎn)。二叉樹(shù)有利于高效地插入、查找、刪除節(jié)點(diǎn)。

二叉搜索樹(shù)：二叉搜索樹(shù)是二叉樹(shù)的一種，它的左側(cè)節(jié)點(diǎn)的值必須大于右側(cè)節(jié)點(diǎn)的值，上圖就是一個(gè)二叉搜索樹(shù)。優(yōu)化的二叉搜索樹(shù)包括AVL樹(shù)、紅黑樹(shù)（待完成）等

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

search(key)：在樹(shù)中查找一個(gè)鍵，如果節(jié)點(diǎn)存在，則返回true；如果不存在，則返回false。

inOrderTraverse：通過(guò)中序遍歷方式遍歷所有節(jié)點(diǎn)。

preOrderTraverse：通過(guò)先序遍歷方式遍歷所有節(jié)點(diǎn)。

postOrderTraverse：通過(guò)后序遍歷方式遍歷所有節(jié)點(diǎn)。

min：返回樹(shù)中最小的值/鍵。

max：返回樹(shù)中最大的值/鍵。

remove(key)：從樹(shù)中移除某個(gè)鍵。

首選實(shí)現(xiàn)二叉查找樹(shù)類的骨架

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

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

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

在下圖的樹(shù)中插入健值為6的節(jié)點(diǎn)，過(guò)程如下：

樹(shù)的遍歷指訪問(wèn)樹(shù)的每一個(gè)節(jié)點(diǎn)，并對(duì)節(jié)點(diǎn)做一定操作。遍歷樹(shù)主要有三種方式：中序、先序、后序。

中序遍歷嚴(yán)格按照從小到大的方式遍歷樹(shù)，也就是優(yōu)先訪問(wèn)左子節(jié)點(diǎn)，相當(dāng)于對(duì)樹(shù)進(jìn)行了排序。

this.inOrderTraverse = function(callback){
    // callback用于對(duì)遍歷到的節(jié)點(diǎn)做操作
    inOrderTraverseNode(root, callback);
};
var inOrderTraverseNode = function (node, callback) {
    // 遍歷到node為null為止
    if (node !== null) {
        // 優(yōu)先遍歷左邊節(jié)點(diǎn)，保證從小到大遍歷
        inOrderTraverseNode(node.left, callback);
        // 處理當(dāng)前的節(jié)點(diǎn)
        callback(node.key);
        // 遍歷右側(cè)節(jié)點(diǎn)
        inOrderTraverseNode(node.right, callback);
    }
};

對(duì)下圖的樹(shù)做中序遍歷，并輸出各個(gè)節(jié)點(diǎn)的鍵值：

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

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

先序遍歷先訪問(wèn)節(jié)點(diǎn)本身，再遍歷其后代節(jié)點(diǎn)，最后遍歷其兄弟節(jié)點(diǎn)。它的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔。

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

用先序遍歷遍歷下圖所示的樹(shù)，并打印節(jié)點(diǎn)鍵值，輸出結(jié)果：11 7 5 3 6 9 8 10 15 13 12 14 20 18 25，
遍歷過(guò)程如圖：

后序遍歷先訪問(wèn)節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問(wèn)節(jié)點(diǎn)本身。它的一種應(yīng)用是計(jì)算一個(gè)目錄和它的子目錄中所有文件的大小。

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}
    }
};

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

在二叉搜索樹(shù)里，不管是整個(gè)樹(shù)還是其子樹(shù)，最小值一定在樹(shù)最左側(cè)的最底層。因此給定一顆樹(shù)或其子樹(shù)，只需要一直向左節(jié)點(diǎn)遍歷到底就行了。

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

搜索最大值與搜索最小值類似，只是沿著樹(shù)的右側(cè)遍歷。

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

搜索特定值的處理與插入值的處理類似。遍歷樹(shù)，將要搜索的值與遍歷到的節(jié)點(diǎn)比較，如果前者大于后者，則遞歸遍歷右側(cè)子節(jié)點(diǎn)，反之，則遞歸遍歷左側(cè)子節(jié)點(diǎn)。

this.search = function(key, node){
    // 同樣的，search方法允許在子樹(shù)中查找值
    node = node || root;
    return searchNode(key, node);
};
var searchNode = function(key, node){
    // 如果node是null，說(shuō)明樹(shù)中沒(méi)有要查找的值，返回false
    if (node === null){
        return false;
    }
    if (key < node.key){
        // 如果要查找的值小于該節(jié)點(diǎn)，繼續(xù)遞歸遍歷其左側(cè)節(jié)點(diǎn)
        return searchNode(node.left, key);
    } else if (key > node.key){
        // 如果要查找的值大于該節(jié)點(diǎn)，繼續(xù)遞歸遍歷其右側(cè)節(jié)點(diǎn)
        return searchNode(node.right, key);
    } else {
        // 如果要查找的值等于該節(jié)點(diǎn)，說(shuō)明查找成功，返回改節(jié)點(diǎn)
        return node;
    }
};

移除節(jié)點(diǎn)，首先要在樹(shù)中查找到要移除的節(jié)點(diǎn)，再判斷該節(jié)點(diǎn)是否有子節(jié)點(diǎn)、有一個(gè)子節(jié)點(diǎn)或者有兩個(gè)子節(jié)點(diǎn)，最后分別處理。

this.remove = function(key, node){
    // 同樣的，允許僅在子樹(shù)中刪除節(jié)點(diǎn)
    node = node || root;
    removeNode(key, node);
};
var removeNode = function (node, key) {
    // 找到要?jiǎng)h除的節(jié)點(diǎn)
    var delete_node = this.search(node, key);
    // 如果node不存在，直接返回
    if (node === false) {
        return null;
    }
    // 第一種情況，該節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)
    if (node.left === null && node.right === null) {
        node = null;
        return node;
    }
    // 第二種情況，該節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
    if (node.left === null) { // 只有右節(jié)點(diǎn)
        node = node.right;
        return node;
    } else if (node.right === null) { // 只有左節(jié)點(diǎn)
        node = node.left;
        return node;
    }
    // 第三種情況，有有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
    // 將右側(cè)子樹(shù)中的最小值，替換到要?jiǎng)h除的位置
    // 找到最小值
    var aux = this.min(node.right);
    // 替換
    node.key = aux.key;
    // 刪除最小值
    node.right = removeNode(node.right, aux.key);
    return node;
}

第三種情況的處理過(guò)程，如下圖所示。當(dāng)要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)時(shí)，為了不破壞樹(shù)的結(jié)構(gòu)，刪除后要替補(bǔ)上來(lái)的節(jié)點(diǎn)的鍵值大小必須在已刪除節(jié)點(diǎn)的左、右子節(jié)點(diǎn)的鍵值之間，且替補(bǔ)上來(lái)的節(jié)點(diǎn)不應(yīng)該有子節(jié)點(diǎn)，否則會(huì)產(chǎn)生一個(gè)節(jié)點(diǎn)有多個(gè)字節(jié)點(diǎn)的情況，因此，找右側(cè)子樹(shù)的最小值替換上來(lái)。同理，找左側(cè)子樹(shù)的最大值替換上來(lái)也可以。