摘要：首先，我們了解一下關(guān)于樹的基本知識(shí)每一個(gè)樹都包含一系列的父子關(guān)系的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)和若干的子節(jié)點(diǎn)零個(gè)或者多個(gè)沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱作是根節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)可以有祖先和后代，子樹由節(jié)點(diǎn)和他的后代構(gòu)成，節(jié)點(diǎn)的一個(gè)屬性是深度深度就是一個(gè)節(jié)點(diǎn)祖先

首先，我們了解一下關(guān)于樹的基本知識(shí)：

每一個(gè)樹都包含一系列的父子關(guān)系的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)和若干的子節(jié)點(diǎn)（零個(gè) 或者 多個(gè)）

沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱作是根節(jié)點(diǎn)

一個(gè)節(jié)點(diǎn) 可以有祖先 和 后代，子樹由節(jié)點(diǎn)和他的后代構(gòu)成，節(jié)點(diǎn)的一個(gè)屬性是深度：深度就是一個(gè)節(jié)點(diǎn)祖先節(jié)點(diǎn)的數(shù)量

、樹的高度是 所有節(jié)點(diǎn)深度中的最大值

二叉樹：就是每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)節(jié)點(diǎn) 一個(gè)是左側(cè)的節(jié)點(diǎn) 另一個(gè)是右側(cè)的節(jié)點(diǎn)
二叉樹搜索又是一種特殊的二叉樹：只允許在左側(cè)存儲(chǔ)比父節(jié)點(diǎn)小的值 在右側(cè)存儲(chǔ)比父節(jié)點(diǎn)大的值，如下面的圖所示：

由上圖可以看出每一個(gè)節(jié)點(diǎn)都有兩個(gè)指針，一個(gè)是指向左側(cè)節(jié)點(diǎn)，一個(gè)是指向右側(cè)節(jié)點(diǎn)

由此，我們可以發(fā)現(xiàn)有關(guān)樹的規(guī)則：

樹的左側(cè)所有的節(jié)點(diǎn)的值肯定是小于根節(jié)點(diǎn)的值，樹的右側(cè)肯定是大于根節(jié)點(diǎn)的值

所以當(dāng)刪除一個(gè)擁有兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，為了遵循樹的規(guī)律，需要找到節(jié)點(diǎn)右側(cè)樹的最小節(jié)點(diǎn)值

接下來，我們將通過javascript 創(chuàng)建一個(gè)二叉樹類，二叉樹是由一個(gè)個(gè)節(jié)點(diǎn)組成的，所以，在類中需要有一個(gè)節(jié)點(diǎn)類，根節(jié)點(diǎn)屬性，還有基本的操作方法，分別是 插入，刪除，遍歷（前序，中序，后序），查詢（最大值，最小值，和某一指定值）

//創(chuàng)建一個(gè)二叉樹類
function BinarySearchTree(key){
   //節(jié)點(diǎn)類，有值，左節(jié)點(diǎn)，右節(jié)點(diǎn)三個(gè)公有屬性
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.rigth = null;
    }
    //在樹中插入一個(gè)節(jié)點(diǎn)
    this.insert = function(newNode){
        if(root === null){
            root = newNode;
        }else{
            insertNode(root,newNode);
        }
     }
    //在樹中查找一個(gè)鍵，如果鍵存在就返回true
    this.search = function(key){
        return searchNode(root,key);
    }
    //通過中序遍歷所有的節(jié)點(diǎn)
    this.inOrderTraverse = function(){
        inOrderTraverseNode(root,callback);
    }
    //通過先序遍歷所有的節(jié)點(diǎn)
    this.preOrderTravers = function(){
        preOrderTraverseNode(root,callback);
    }
    //通過后續(xù)遍歷所有的節(jié)點(diǎn)
    this.postOrderTravers = function(){
        postOrderTraverseNode(root,callback);
    }
    //返回樹中最小的鍵值
    this.min = function(){
       return minNode(root);
    }
    //返回樹中最大的鍵值
    this.max = function(){
        return maxNode(root);
    }
    //從樹中移除某一個(gè)鍵值
    this.remove = function(key){
        root = removeNode(root,key);
    }
    var root = null;
}

首先，實(shí)現(xiàn) insert方法，大致思路是這樣的：先判斷 根節(jié)點(diǎn)是否為空，如果為空的話，就直接將新的節(jié)點(diǎn)作為根節(jié)點(diǎn)，如果不為空的話就調(diào)用一個(gè)插入節(jié)點(diǎn)的私有方法。

//創(chuàng)建插入節(jié)點(diǎn)的方法"
     this.insert = function(newNode){
        if(root === null){
            root = newNode;
        }else{
            insertNode(root,newNode);
        }
     }

insertNode的具體實(shí)現(xiàn)是這樣的：

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

函數(shù)解釋：基本思想就是 將節(jié)點(diǎn) 他的左節(jié)點(diǎn) 和 他的右節(jié)點(diǎn) 看作是一個(gè)小的子樹，先判斷新節(jié)點(diǎn)的鍵值 是否小于節(jié)點(diǎn)的鍵值，如果小，就判斷左節(jié)點(diǎn)是否為空，如果左節(jié)點(diǎn)為空，就將新的節(jié)點(diǎn)直接賦值給左節(jié)點(diǎn)，如果左節(jié)點(diǎn)不為空，就將左節(jié)點(diǎn)作為搜索比較的基點(diǎn)，調(diào)用自身再進(jìn)行搜索比較（遞歸算法），相反如果大于節(jié)點(diǎn)的鍵值，再判斷右節(jié)點(diǎn)是否為空，如果為空就直接將節(jié)點(diǎn)賦值給右節(jié)點(diǎn)，如果節(jié)點(diǎn)不為空同樣調(diào)用自身。

接下來，我們定義 中序遍歷的函數(shù)：
中序遍歷是二叉樹的一種遍歷方式之一，實(shí)質(zhì)上就是以從小到大的順序訪問二叉樹，中序遍歷的一種應(yīng)用就是對(duì)樹中存儲(chǔ)的值進(jìn)行從小到大的排列，中序遍歷的輔助方法如下所述：

 var inOrderTraverseNode = function(node,callback){
        if(node !== null){
            inOrderTraverseNode(node.left,callback);（1）
            callback(node.key);（2）
            inOrderTraverseNode(node.right.callback);（3）
        }
    }

我以一個(gè)例子畫了調(diào)用過程（簡(jiǎn)單粗糙，后期會(huì)修改）：

先序遍歷的作用是打印樹的一個(gè)結(jié)構(gòu)化文檔，他的輔助函數(shù)如下面所述：

    var preOrderTraverseNode = function(node,callback){
        if(node !== null){
            callback(node.key);
            preOrderTraverseNode(node.left,callback);
            preOrderTraverseNode(node.right,callback);
        }
    }

調(diào)用過程圖 與 中序遍歷相似

后序遍歷的作用的計(jì)算樹的子目錄 和 父目錄的所有文件所占空間的大小，其輔助函數(shù)的具體實(shí)現(xiàn)如下面所示：

 var postOrderTraverseNode = function(node,callback){
        if(node!== null){
            postOrderTraverseNode(node.left,callback);
            postOrderTraverseNode(node.right.callback);
            callback(node.key);
        }
    }

以上我們對(duì)三種遍歷方式做了具體的實(shí)現(xiàn)，接下來我們完成對(duì)樹中的所有值進(jìn)行搜索。
基于構(gòu)建樹時(shí)所遵循的具體規(guī)則，我們可以看出在樹的最左端是樹的最小值，樹的最右端就是樹的最大值
那么尋找最小值的輔助函數(shù)是這樣實(shí)現(xiàn)的：

    //搜索最小值時(shí)的搜索函數(shù)
    var minNode = function(node){
        //判斷節(jié)點(diǎn)是否存在，如果存在就執(zhí)行循環(huán)
        if(node){
            while(node && node.left !== null){
                node = node.left;
            }
            return node.key;
        }
        return null;
    }

函數(shù)解釋:首先判斷所傳的節(jié)點(diǎn)（一般是根節(jié)點(diǎn)，看是否存在），如果存在的話就進(jìn)行循環(huán)，直到找到最左端的節(jié)點(diǎn)（節(jié)點(diǎn)的左節(jié)點(diǎn)不存在，那么這就是最左邊的節(jié)點(diǎn)），返回節(jié)點(diǎn)的所有值

尋找最大值的輔助函數(shù)是這樣實(shí)現(xiàn)的：

//搜索樹中的最大值函數(shù)
    var maxNode = function(node){
        if(node){
            while(node && node.right !== null){
                node = node.right;
            }
            return node.key;
        }
        return null;
     }

與尋找最小值相反，該函數(shù)是循環(huán)找最右邊的節(jié)點(diǎn)

搜索特定值得輔助函數(shù)如下：

 //搜索特定值得輔助函數(shù)
     var searchNode = fucntion(node,key){
       var result;
       if(node === null){
           result = false;
       }
       if(key < node.key){
            searchNode(node.left,key);
       }else if(key > node.key){
            searchNode(node.right,key);
       }else{
           result = true;
       }
      return result; 
     }

函數(shù)解釋：如果想要尋找的key值小于節(jié)點(diǎn)值就在節(jié)點(diǎn)的右側(cè)樹上尋找，在節(jié)點(diǎn)不為空的情況下回調(diào)該函數(shù)，縮小右側(cè)樹的尋找范圍，最后節(jié)點(diǎn)如果為空就是沒有找到，反之，找到；大于節(jié)點(diǎn)值同理

最后，我們完成移除節(jié)點(diǎn)的方法
根據(jù)子節(jié)點(diǎn)的數(shù)量，我們將節(jié)點(diǎn)分為三種情況：

葉子節(jié)點(diǎn)，既沒有左節(jié)點(diǎn)也沒有右節(jié)點(diǎn)

只有一個(gè)節(jié)點(diǎn)，左節(jié)點(diǎn) 或者 右節(jié)點(diǎn)

有兩個(gè)節(jié)點(diǎn)左節(jié)點(diǎn)和右節(jié)點(diǎn)

針對(duì)上面三種情況，有三種刪除節(jié)點(diǎn)的方法
對(duì)于第一種情況：因?yàn)槿~子節(jié)點(diǎn)即沒有左節(jié)點(diǎn)，也沒有右節(jié)點(diǎn)，所以直接將該節(jié)點(diǎn)賦值為null就可以了，但是，單單這樣是遠(yuǎn)遠(yuǎn)不夠的，我們還需要對(duì)其相應(yīng)的指針進(jìn)行處理，對(duì)于葉子節(jié)點(diǎn)來說，我們需要處理葉子節(jié)點(diǎn)父節(jié)點(diǎn)的指針，使其的指針指向null，所以需要在執(zhí)行完刪除以后返回當(dāng)前所基于的node節(jié)點(diǎn),層層返回后實(shí)質(zhì)上是以node節(jié)點(diǎn)為root的子樹

對(duì)于第二種情況：移除只有一個(gè)節(jié)點(diǎn)時(shí)的節(jié)點(diǎn)，那么節(jié)點(diǎn)的左側(cè)節(jié)點(diǎn)或者右側(cè)節(jié)點(diǎn)就可以取代節(jié)點(diǎn)的位置

對(duì)于第三種情況：當(dāng)移除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，需要找到該節(jié)點(diǎn)右側(cè)樹上節(jié)點(diǎn)值最小的節(jié)點(diǎn)，并用該節(jié)點(diǎn)代替它，最后使其的右側(cè)節(jié)點(diǎn)指向刪除節(jié)點(diǎn)后的樹

    //移除一個(gè)節(jié)點(diǎn)的輔助函數(shù)
     var removeNode = function(node,key){
       if(node === null){
           return null;
       }
       //尋找節(jié)點(diǎn)是key值的節(jié)點(diǎn)
       if(key < node.key){
           node.left = removeNode(node.left,key);
           return node;
       }else if(key > node.key){
           node.right = removeNode(node.right,key);
           return node;
       }else{
           //第一種情況——兩個(gè)葉子節(jié)點(diǎn)都沒有
           if(node.left === null && node.right === null){
               node = null;
               return node;
           }
           //第二種情況——只有一個(gè)葉子節(jié)點(diǎn)
           if(node.left === null){
              node = node.right;
              return node;
           }else if(node.right === null){
               node = node.left;
               return node;
           }
           //第三種情況——有兩個(gè)葉子節(jié)點(diǎn)的節(jié)點(diǎn)
           var min = minNode(node.right);
           node.key = min;
           node.right = removeNode(node.right,min);
           return node;        
       }
     
     }

最后，我們?cè)敿?xì)解釋一下第三種情況為什么會(huì)這樣寫，當(dāng)該節(jié)點(diǎn)被刪除的時(shí)候，我們需要尋找一個(gè)節(jié)點(diǎn)來代替，尋找哪個(gè)節(jié)點(diǎn)呢？肯定是尋找比他值大的節(jié)點(diǎn)，因?yàn)橐ＷC左節(jié)點(diǎn)的值要小于尋找到的新值，所以我們鎖定的目標(biāo)是節(jié)點(diǎn)的右側(cè)樹，然而找的節(jié)點(diǎn)值還必須小于右節(jié)點(diǎn)的值，所以尋找右側(cè)樹的最小值，并將該節(jié)點(diǎn)刪除

以上是我對(duì)樹的理解和總結(jié)，本人接受各位同仁大神的指點(diǎn)，謝謝