摘要：首先，我們了解一下關于樹的基本知識每一個樹都包含一系列的父子關系的節點，每個節點都有一個父節點和若干的子節點零個或者多個沒有父節點的節點稱作是根節點一個節點可以有祖先和后代，子樹由節點和他的后代構成，節點的一個屬性是深度深度就是一個節點祖先

首先，我們了解一下關于樹的基本知識：

每一個樹都包含一系列的父子關系的節點，每個節點都有一個父節點和若干的子節點（零個 或者 多個）

沒有父節點的節點稱作是根節點

一個節點 可以有祖先 和 后代，子樹由節點和他的后代構成，節點的一個屬性是深度：深度就是一個節點祖先節點的數量

、樹的高度是 所有節點深度中的最大值

二叉樹：就是每個節點最多只能有兩個節點 一個是左側的節點 另一個是右側的節點
二叉樹搜索又是一種特殊的二叉樹：只允許在左側存儲比父節點小的值 在右側存儲比父節點大的值，如下面的圖所示：

由上圖可以看出每一個節點都有兩個指針，一個是指向左側節點，一個是指向右側節點

由此，我們可以發現有關樹的規則：

樹的左側所有的節點的值肯定是小于根節點的值，樹的右側肯定是大于根節點的值

所以當刪除一個擁有兩個節點的節點時，為了遵循樹的規律，需要找到節點右側樹的最小節點值

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

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

首先，實現 insert方法，大致思路是這樣的：先判斷 根節點是否為空，如果為空的話，就直接將新的節點作為根節點，如果不為空的話就調用一個插入節點的私有方法。

//創建插入節點的方法"
     this.insert = function(newNode){
        if(root === null){
            root = newNode;
        }else{
            insertNode(root,newNode);
        }
     }

insertNode的具體實現是這樣的：

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

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

接下來，我們定義 中序遍歷的函數：
中序遍歷是二叉樹的一種遍歷方式之一，實質上就是以從小到大的順序訪問二叉樹，中序遍歷的一種應用就是對樹中存儲的值進行從小到大的排列，中序遍歷的輔助方法如下所述：

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

我以一個例子畫了調用過程（簡單粗糙，后期會修改）：

先序遍歷的作用是打印樹的一個結構化文檔，他的輔助函數如下面所述：

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

調用過程圖 與 中序遍歷相似

后序遍歷的作用的計算樹的子目錄 和 父目錄的所有文件所占空間的大小，其輔助函數的具體實現如下面所示：

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

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

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

函數解釋:首先判斷所傳的節點（一般是根節點，看是否存在），如果存在的話就進行循環，直到找到最左端的節點（節點的左節點不存在，那么這就是最左邊的節點），返回節點的所有值

尋找最大值的輔助函數是這樣實現的：

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

與尋找最小值相反，該函數是循環找最右邊的節點

搜索特定值得輔助函數如下：

 //搜索特定值得輔助函數
     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; 
     }

函數解釋：如果想要尋找的key值小于節點值就在節點的右側樹上尋找，在節點不為空的情況下回調該函數，縮小右側樹的尋找范圍，最后節點如果為空就是沒有找到，反之，找到；大于節點值同理

最后，我們完成移除節點的方法
根據子節點的數量，我們將節點分為三種情況：

葉子節點，既沒有左節點也沒有右節點

只有一個節點，左節點 或者 右節點

有兩個節點左節點和右節點

針對上面三種情況，有三種刪除節點的方法
對于第一種情況：因為葉子節點即沒有左節點，也沒有右節點，所以直接將該節點賦值為null就可以了，但是，單單這樣是遠遠不夠的，我們還需要對其相應的指針進行處理，對于葉子節點來說，我們需要處理葉子節點父節點的指針，使其的指針指向null，所以需要在執行完刪除以后返回當前所基于的node節點,層層返回后實質上是以node節點為root的子樹

對于第二種情況：移除只有一個節點時的節點，那么節點的左側節點或者右側節點就可以取代節點的位置

對于第三種情況：當移除有兩個子節點的節點時，需要找到該節點右側樹上節點值最小的節點，并用該節點代替它，最后使其的右側節點指向刪除節點后的樹

    //移除一個節點的輔助函數
     var removeNode = function(node,key){
       if(node === null){
           return null;
       }
       //尋找節點是key值的節點
       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{
           //第一種情況——兩個葉子節點都沒有
           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 min = minNode(node.right);
           node.key = min;
           node.right = removeNode(node.right,min);
           return node;        
       }
     
     }

最后，我們詳細解釋一下第三種情況為什么會這樣寫，當該節點被刪除的時候，我們需要尋找一個節點來代替，尋找哪個節點呢？肯定是尋找比他值大的節點，因為要保證左節點的值要小于尋找到的新值，所以我們鎖定的目標是節點的右側樹，然而找的節點值還必須小于右節點的值，所以尋找右側樹的最小值，并將該節點刪除

以上是我對樹的理解和總結，本人接受各位同仁大神的指點，謝謝