JavaScript實現樹結構（二）

• 2020 年 3 月 11 日
• 筆記

JavaScript實現樹結構（二）

一、二叉搜索樹的封裝

二叉樹搜索樹的基本屬性：

如圖所示：二叉搜索樹有四個最基本的屬性：指向節點的根（root），節點中的鍵（key）、左指針（right）、右指針（right）。

所以，二叉搜索樹中除了定義root屬性外，還應定義一個節點內部類，裡面包含每個節點中的left、right和key三個屬性：

    //封裝二叉搜索樹      function BinarySearchTree(){          //節點內部類        function Node(key){          this.key = key          this.left = null          this.right = null        }          //屬性        this.root = null    }

二叉搜索樹的常見操作：

• insert（key）：向樹中插入一個新的鍵；
• search（key）：在樹中查找一個鍵，如果節點存在，則返回true；如果不存在，則返回false；
• inOrderTraverse：通過中序遍歷方式遍歷所有節點；
• preOrderTraverse：通過先序遍歷方式遍歷所有節點；
• postOrderTraverse：通過後序遍歷方式遍歷所有節點；
• min：返回樹中最小的值/鍵；
• max：返回樹中最大的值/鍵；
• remove（key）：從樹中移除某個鍵；

1.插入數據

實現思路：

• 首先根據傳入的key創建節點對象；
• 然後判斷根節點是否存在，不存在時通過：this.root = newNode，直接把新節點作為二叉搜索樹的根節點。
• 若存在根節點則重新定義一個內部方法insertNode（）用於查找插入點。

     //insert方法:對外向用戶暴露的方法        BinarySearchTree.prototype.insert = function(key){          //1.根據key創建節點          let newNode = new Node(key)            //2.判斷根節點是否存在          if (this.root == null) {            this.root = newNode            //根節點存在時          }else {            this.insertNode(this.root, newNode)          }        }  

內部方法insertNode（）的實現思路:

根據比較傳入的兩個節點，一直查找新節點適合插入的位置，直到成功插入新節點為止。

當newNode.key < node.key向左查找:

• 情況1：當node無左子節點時，直接插入：

• 情況2：當node有左子節點時，遞歸調用insertNode(),直到遇到無左子節點成功插入newNode後，不再符合該情況，也就不再調用insertNode()，遞歸停止。

當newNode.key >= node.key向右查找，與向左查找類似：

• 情況1：當node無右子節點時，直接插入：

• 情況2：當node有右子節點時，依然遞歸調用insertNode(),直到遇到傳入insertNode方法的node無右子節點成功插入newNode為止：

insertNode()程式碼實現：

      //內部使用的insertNode方法:用於比較節點從左邊插入還是右邊插入        BinarySearchTree.prototype.insertNode = function(node, newNode){          //當newNode.key < node.key向左查找  /*----------------------分支1:向左查找--------------------------*/          if(newNode.key < node.key){            //情況1：node無左子節點，直接插入  /*----------------------分支1.1--------------------------*/            if (node.left == null) {              node.left = newNode            //情況2：node有左子節點，遞歸調用insertNode(),直到遇到無左子節點成功插入newNode後，不再符合該情況，也就不再調用insertNode()，遞歸停止。  /*----------------------分支1.2--------------------------*/            }else{              this.insertNode(node.left, newNode)            }          //當newNode.key >= node.key向右查找  /*-----------------------分支2:向右查找--------------------------*/          }else{            //情況1：node無右子節點，直接插入  /*-----------------------分支2.1--------------------------*/            if(node.right == null){              node.right == newNode            //情況2：node有右子節點，依然遞歸調用insertNode(),直到遇到無右子節點成功插入newNode為止  /*-----------------------分支2.2--------------------------*/            }else{              this.insertNode(node.right, newNode)            }          }        }

過程詳解：

為了更好理解以下列二叉搜索樹為例：

想要上述的二叉搜索樹（藍色）中插入數據10：

• 先把key = 10 傳入insert方法，由於存在根節點 9，所以直接調用insetNode方法，傳入的參數：node = 9，newNode = 10；
• 由於10 > 9，進入分支2，向右查找適合插入的位置；
• 由於根節點 9 的右子節點存在且為 13 ，所以進入分支2.2，遞歸調用insertNode方法，傳入的參數：node = 13，newNode = 10；
• 由於 10 < 13 ，進入分支1，向左查找適合插入的位置；
• 由於父節點 13 的左子節點存在且為11，所以進入分支1.2，遞歸調用insertNode方法，傳入的參數：node = 11，newNode = 10；
• 由於 10 < 11，進入分支1，向左查找適合插入的位置；
• 由於父節點 11 的左子節點不存在，所以進入分支1.1，成功插入節點 10 。由於不符合分支1.2的條件所以不會繼續調用insertNode方法，遞歸停止。

測試程式碼：

    //測試程式碼      //1.創建BinarySearchTree      let bst = new BinarySearchTree()        //2.插入數據      bst.insert(11);      bst.insert(7);      bst.insert(15);      bst.insert(5);      bst.insert(9);      console.log(bst);

應得到下圖所示的二叉搜索樹：

測試結果

2.遍曆數據

這裡所說的樹的遍歷不僅僅針對二叉搜索樹，而是適用於所有的二叉樹。由於樹結構不是線性結構，所以遍歷方式有多種選擇，常見的三種二叉樹遍歷方式為：

• 先序遍歷；
• 中序遍歷；
• 後序遍歷；

還有層序遍歷，使用較少。

2.1.先序遍歷

先序遍歷的過程為：

• 首先，遍歷根節點；
• 然後，遍歷其左子樹；
• 最後，遍歷其右子樹；

如上圖所示，二叉樹的節點遍歷順序為：A -> B -> D -> H -> I -> E -> C -> F -> G。

程式碼實現：

      //先序遍歷        //摻入一個handler函數方便之後對得到的key進行處理        BinarySearchTree.prototype.preOrderTraversal = function(handler){          this.preOrderTraversalNode(this.root, handler)        }          //封裝內部方法，對某個節點進行遍歷        BinarySearchTree.prototype.preOrderTraversalNode = function(node,handler){          if (node != null) {            //1.處理經過的節點            handler(node.key)  /*----------------------遞歸1----------------------------*/            //2.遍歷左子樹中的節點            this.preOrderTraversalNode(node.left, handler)  /*----------------------遞歸2----------------------------*/            //3.遍歷右子樹中的節點            this.preOrderTraversalNode(node.right, handler)          }        }

過程詳解：

以遍歷以下二叉搜索樹為例：

首先調用preOrderTraversal方法，在方法里再調用preOrderTraversalNode方法用於遍歷二叉搜索樹。在preOrderTraversalNode方法中，遞歸1負責遍歷左子節點，遞歸2負責遍歷右子節點。先執行遞歸1，執行過程如下圖所示：

記：preOrderTraversalNode() 為 A()

可以看到一共遞歸調用了4次方法A，分別傳入11、7、5、3，最後遇到null不滿足 node != null 條件結束遞歸1；注意此時只是執行完最開始的遞歸1，並沒有執行遞歸2，並且遞歸1執行到null停止後要一層層地往上返回，按順序將調用的函數壓出函數調用棧。

關於函數調用棧：之前的四次遞歸共把4個函數壓入了函數調用棧，現在遞歸執行完了一層層地把函數壓出棧。

值得注意的是：每一層函數都只是執行完了遞歸1，當返回到該層函數時，比如A（3）要繼續執行遞歸2遍歷二叉搜索樹中的右子節點；

在執行遞歸2的過程中會不斷調用方法A，並依次執行遞歸1和遞歸2，以此類推直到遇到null不滿足 node != null 條件為止，才停止遞歸併一層層返回，如此循環。同理A（5）層、A（7）層、A（11）層都要經歷上述循環，直到將二叉搜索樹中的節點全部遍歷完為止。

具體過程如下圖所示：

測試程式碼：

    //測試程式碼      //1.創建BinarySearchTree      let bst = new BinarySearchTree()        //2.插入數據      bst.insert(11);      bst.insert(7);      bst.insert(15);      bst.insert(5);      bst.insert(3);      bst.insert(9);      bst.insert(8);      bst.insert(10);      bst.insert(13);      bst.insert(12);      bst.insert(14);      bst.insert(20);      bst.insert(18);      bst.insert(25);      bst.insert(6);        //3.測試遍歷      let resultString = ""      //摻入處理節點值的處理函數      bst.preOrderTraversal(function(key){        resultString += key + "->"      })      alert(resultString)

應輸出這樣的順序：11 -> 7 -> 5 -> 3 -> 6 -> 9 -> 8 -> 10 -> 15 -> 13 ->12 -> 14 -> 20 -> 18 -> 25 。

測試結果：

2.2.中序遍歷

實現思路：與先序遍歷原理相同，只不過是遍歷的順序不一樣了。

• 首先，遍歷其左子樹；
• 然後，遍歷根（父）節點；
• 最後，遍歷其右子樹；

程式碼實現：

      //中序遍歷        BinarySearchTree.prototype.midOrderTraversal = function(handler){          this.midOrderTraversalNode(this.root, handler)        }          BinarySearchTree.prototype.midOrderTraversalNode = function(node, handler){          if (node != null) {            //1.遍歷左子樹中的節點            this.midOrderTraversalNode(node.left, handler)              //2.處理節點            handler(node.key)              //3.遍歷右子樹中的節點            this.midOrderTraversalNode(node.right, handler)          }        }

過程詳解：

遍歷的順序應如下圖所示：

首先調用midOrderTraversal方法，在方法里再調用midOrderTraversalNode方法用於遍歷二叉搜索樹。先使用遞歸1遍歷左子樹中的節點；然後，處理父節點；最後，遍歷右子樹中的節點。

測試程式碼：

  //測試程式碼      //1.創建BinarySearchTree      let bst = new BinarySearchTree()        //2.插入數據      bst.insert(11);      bst.insert(7);      bst.insert(15);      bst.insert(5);      bst.insert(3);      bst.insert(9);      bst.insert(8);      bst.insert(10);      bst.insert(13);      bst.insert(12);      bst.insert(14);      bst.insert(20);      bst.insert(18);      bst.insert(25);      bst.insert(6);        //3.測試中序遍歷      let resultString2 =""      bst.midOrderTraversal(function(key){        resultString2 += key + "->"      })      alert(resultString2)

輸出節點的順序應為：3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 18 -> 20 -> 25 。

測試結果：

2.3.後續遍歷

實現思路：與先序遍歷原理相同，只不過是遍歷的順序不一樣了。

• 首先，遍歷其左子樹；
• 然後，遍歷其右子樹；
• 最後，遍歷根（父）節點；

程式碼實現：

      //後序遍歷        BinarySearchTree.prototype.postOrderTraversal = function(handler){          this.postOrderTraversalNode(this.root, handler)        }          BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler){          if (node != null) {            //1.遍歷左子樹中的節點            this.postOrderTraversalNode(node.left, handler)              //2.遍歷右子樹中的節點            this.postOrderTraversalNode(node.right, handler)              //3.處理節點            handler(node.key)          }        }

過程詳解：

遍歷的順序應如下圖所示：

首先調用postOrderTraversal方法，在方法里再調用postOrderTraversalNode方法用於遍歷二叉搜索樹。先使用遞歸1遍歷左子樹中的節點；然後，遍歷右子樹中的節點；最後，處理父節點。

測試程式碼：

    //測試程式碼      //1.創建BinarySearchTree      let bst = new BinarySearchTree()        //2.插入數據      bst.insert(11);      bst.insert(7);      bst.insert(15);      bst.insert(5);      bst.insert(3);      bst.insert(9);      bst.insert(8);      bst.insert(10);      bst.insert(13);      bst.insert(12);      bst.insert(14);      bst.insert(20);      bst.insert(18);      bst.insert(25);      bst.insert(6);        //3.測試後序遍歷      let resultString3 =""      bst.postOrderTraversal(function(key){        resultString3 += key + "->"      })      alert(resultString3)

輸出節點的順序應為：3 -> 6 -> 5 -> 8 -> 10 -> 9 -> 7 -> 12 -> 14 -> 13 -> 18 -> 25 -> 20 -> 15 -> 11 。

測試結果：

總結：以遍歷根（父）節點的順序來區分三種遍歷方式。比如：先序遍歷先遍歷根節點、中序遍歷第二遍歷根節點、後續遍歷最後遍歷根節點。

3.查找數據

3.1.查找最大值&最小值

在二叉搜索樹中查找最值非常簡單，最小值在二叉搜索樹的最左邊，最大值在二叉搜索樹的最右邊。只需要一直向左/右查找就能得到最值，如下圖所示：

程式碼實現：

      //尋找最大值        BinarySearchTree.prototype.max = function () {          //1.獲取根節點          let node = this.root          //2.定義key保存節點值          let key = null          //3.依次向右不斷查找，直到節點為null          while (node != null) {            key = node.key            node = node.right          }          return key        }          //尋找最小值        BinarySearchTree.prototype.min = function(){           //1.獲取根節點           let node = this.root          //2.定義key保存節點值          let key = null          //3.依次向左不斷查找，直到節點為null          while (node != null) {            key = node.key            node = node.left          }          return key        }

測試程式碼：

   //測試程式碼      //1.創建BinarySearchTree      let bst = new BinarySearchTree()        //2.插入數據      bst.insert(11);      bst.insert(7);      bst.insert(15);      bst.insert(5);      bst.insert(3);      bst.insert(9);      bst.insert(8);      bst.insert(10);      bst.insert(13);      bst.insert(12);      bst.insert(14);      bst.insert(20);      bst.insert(18);      bst.insert(25);      bst.insert(6);        //4.測試最值      console.log(bst.max());      console.log(bst.min());      

測試結果：

3.2.查找特定值

查找二叉搜索樹當中的特定值效率也非常高。只需要從根節點開始將需要查找節點的key值與之比較，若node.key < root則向左查找，若node.key > root就向右查找，直到找到或查找到null為止。這裡可以使用遞歸實現，也可以採用循環來實現。

實現程式碼：

     //查找特定的key        BinarySearchTree.prototype.search = function(key){          //1.獲取根節點          let node = this.root            //2.循環搜索key          while(node != null){            if (key < node.key) {              //小於根(父)節點就往左邊找              node = node.left              //大於根(父)節點就往右邊找            }else if(key > node.key){              node = node.right            }else{              return true            }          }          return false        }

測試程式碼：

    //測試程式碼      //1.創建BinarySearchTree      let bst = new BinarySearchTree()        //2.插入數據      bst.insert(11);      bst.insert(7);      bst.insert(15);      bst.insert(5);      bst.insert(3);      bst.insert(9);      bst.insert(8);      bst.insert(10);      bst.insert(13);      bst.insert(12);      bst.insert(14);      bst.insert(20);      bst.insert(18);      bst.insert(25);      bst.insert(6);        //3.測試搜索方法      console.log(bst.search(24));//false      console.log(bst.search(13));//true      console.log(bst.search(2));//false

測試結果：

4.刪除數據

實現思路：

第一步：先找到需要刪除的節點，若沒找到，則不需要刪除；

首先定義變數current用於保存需要刪除的節點、變數parent用於保存它的父節點、變數isLeftChild保存current是否為parent的左節點，這樣方便之後刪除節點時改變相關節點的指向。

實現程式碼：

        //1.1.定義變數          let current = this.root          let parent = null          let isLeftChild = true            //1.2.開始尋找刪除的節點          while (current.key != key) {            parent = current            // 小於則往左查找            if (key < current.key) {              isLeftChild = true              current = current.left            } else{              isLeftChild = false              current = current.rigth            }            //找到最後依然沒有找到相等的節點            if (current == null) {              return false            }          }          //結束while循環後：current.key = key

第二步：刪除找到的指定節點，後分3種情況：

• 刪除葉子節點；
• 刪除只有一個子節點的節點；
• 刪除有兩個子節點的節點；

4.1.情況1：沒有子節點

沒有子節點時也有兩種情況：

當該葉子節點為根節點時，如下圖所示，此時current == this.root，直接通過：this.root = null，刪除根節點。

當該葉子節點不為根節點時也有兩種情況，如下圖所示：

若current = 8，可以通過：parent.left = null，刪除節點8；

若current = 10，可以通過：parent.right = null，刪除節點10；

程式碼實現：

        //情況1：刪除的是葉子節點(沒有子節點)          if (current.left == null && current.right ==null) {            if (current == this.root) {              this.root = null            }else if(isLeftChild){              parent.left = null            }else {              parent.right =null            }          }

4.2.情況2：有一個子節點

有六種情況分別是：

當current存在左子節點時（current.right == null）：

• 情況1：current為根節點（current == this.root），如節點11，此時通過：this.root = current.left，刪除根節點11；

• 情況2：current為父節點parent的左子節點（isLeftChild == true），如節點5，此時通過：parent.left = current.left，刪除節點5；

• 情況3：current為父節點parent的右子節點（isLeftChild == false），如節點9，此時通過：parent.right = current.left，刪除節點9；

當current存在右子節點時（current.left = null）：

• 情況4：current為根節點（current == this.root），如節點11，此時通過：this.root = current.right，刪除根節點11。

• 情況5：current為父節點parent的左子節點（isLeftChild == true），如節點5，此時通過：parent.left = current.right，刪除節點5；

• 情況6：current為父節點parent的右子節點（isLeftChild == false），如節點9，此時通過：parent.right = current.right，刪除節點9；

實現程式碼：

        //情況2：刪除的節點有一個子節點          //當current存在左子節點時          else if(current.right == null){              if (current == this.root) {                this.root = current.left              } else if(isLeftChild) {                  parent.left = current.left              } else{                  parent.right = current.left              }          //當current存在右子節點時        } else if(current.left == null){              if (current == this.root) {                this.root = current.rigth              } else if(isLeftChild) {                  parent.left = current.right              } else{                  parent.right = current.right              }        }

4.3.情況3：有兩個子節點

這種情況十分複雜，首先依據以下二叉搜索樹，討論這樣的問題：

刪除節點9

在保證刪除節點9後原二叉樹仍為二叉搜索樹的前提下，有兩種方式：

• 方式1：從節點9的左子樹中選擇一合適的節點替代節點9，可知節點8符合要求；
• 方式2：從節點9的右子樹中選擇一合適的節點替代節點9，可知節點10符合要求；

刪除節點7

在保證刪除節點7後原二叉樹仍為二叉搜索樹的前提下，也有兩種方式：

• 方式1：從節點7的左子樹中選擇一合適的節點替代節點7，可知節點5符合要求；
• 方式2：從節點7的右子樹中選擇一合適的節點替代節點7，可知節點8符合要求；

刪除節點15

在保證刪除節點15後原樹二叉樹仍為二叉搜索樹的前提下，同樣有兩種方式：

• 方式1：從節點15的左子樹中選擇一合適的節點替代節點15，可知節點14符合要求；
• 方式2：從節點15的右子樹中選擇一合適的節點替代節點15，可知節點18符合要求；

相信你已經發現其中的規律了！

規律總結：如果要刪除的節點有兩個子節點，甚至子節點還有子節點，這種情況下需要從要刪除節點下面的子節點中找到一個合適的節點，來替換當前的節點。

若用current表示需要刪除的節點，則合適的節點指的是：

• current左子樹中比current小一點點的節點，即current左子樹中的最大值；
• current右子樹中比current大一點點的節點，即current右子樹中的最小值；

前驅&後繼

在二叉搜索樹中，這兩個特殊的節點有特殊的名字：

• 比current小一點點的節點，稱為current節點的前驅。比如下圖中的節點5就是節點7的前驅；
• 比current大一點點的節點，稱為current節點的後繼。比如下圖中的節點8就是節點7的後繼；

程式碼實現：

• 查找需要被刪除的節點current的後繼時，需要在current的右子樹中查找最小值，即在current的右子樹中一直向左遍歷查找；

• 查找前驅時，則需要在current的左子樹中查找最大值，即在current的左子樹中一直向右遍歷查找。

下面只討論查找current後繼的情況，查找前驅的原理相同，這裡暫不討論。

4.4.完整實現

      //刪除節點        BinarySearchTree.prototype.remove = function(key){  /*------------------------------1.尋找要刪除的節點---------------------------------*/          //1.1.定義變數current保存刪除的節點，parent保存它的父節點。isLeftChild保存current是否為parent的左節點          let current = this.root          let parent = null          let isLeftChild = true            //1.2.開始尋找刪除的節點          while (current.key != key) {            parent = current            // 小於則往左查找            if (key < current.key) {              isLeftChild = true              current = current.left            } else{              isLeftChild = false              current = current.right            }            //找到最後依然沒有找到相等的節點            if (current == null) {              return false            }          }          //結束while循環後：current.key = key    /*------------------------------2.根據對應情況刪除節點------------------------------*/          //情況1：刪除的是葉子節點(沒有子節點)          if (current.left == null && current.right ==null) {            if (current == this.root) {              this.root = null            }else if(isLeftChild){              parent.left = null            }else {              parent.right =null            }          }          //情況2：刪除的節點有一個子節點          //當current存在左子節點時          else if(current.right == null){              if (current == this.root) {                this.root = current.left              } else if(isLeftChild) {                  parent.left = current.left              } else{                  parent.right = current.left              }          //當current存在右子節點時        } else if(current.left == null){              if (current == this.root) {                this.root = current.right              } else if(isLeftChild) {                  parent.left = current.right              } else{                  parent.right = current.right              }        }          //情況3：刪除的節點有兩個子節點          else{            //1.獲取後繼節點            let successor = this.getSuccessor(current)              //2.判斷是否根節點            if (current == this.root) {              this.root = successor            }else if (isLeftChild){              parent.left = successor            }else{              parent.right = successor            }              //3.將後繼的左子節點改為被刪除節點的左子節點            successor.left = current.left          }        }          //封裝查找後繼的方法        BinarySearchTree.prototype.getSuccessor = function(delNode){          //1.定義變數,保存找到的後繼          let successor = delNode          let current = delNode.right          let successorParent = delNode            //2.循環查找current的右子樹節點          while(current != null){            successorParent = successor            successor = current            current = current.left          }            //3.判斷尋找到的後繼節點是否直接就是刪除節點的right節點          if(successor != delNode.right){            successorParent.left = successor.right            successor.right = delNode.right          }          return successor        }

測試程式碼：

   //測試程式碼      //1.創建BinarySearchTree      let bst = new BinarySearchTree()        //2.插入數據      bst.insert(11);      bst.insert(7);      bst.insert(15);      bst.insert(5);      bst.insert(3);      bst.insert(9);      bst.insert(8);      bst.insert(10);      bst.insert(13);      bst.insert(12);      bst.insert(14);      bst.insert(20);      bst.insert(18);      bst.insert(25);      bst.insert(6);      bst.insert(19);       //3.測試刪除程式碼      //刪除沒有子節點的節點      bst.remove(3)      bst.remove(8)      bst.remove(10)        //刪除有一個子節點的節點      bst.remove(5)      bst.remove(19)        //刪除有兩個子節點的節點      bst.remove(9)      bst.remove(7)      bst.remove(15)        //遍歷二叉搜索樹並輸出      let resultString = ""      bst.midOrderTraversal(function(key){        resultString += key + "->"      })      alert(resultString)  

測試結果：

可見三種情況的節點都被成功刪除了。

5.二叉搜索樹完整封裝

    //封裝二叉搜索樹      function BinarySearchTree(){          //節點內部類        function Node(key){          this.key = key          this.left = null          this.right = null        }          //屬性        this.root = null          //方法        //一.插入數據：insert方法:對外向用戶暴露的方法        BinarySearchTree.prototype.insert = function(key){          //1.根據key創建節點          let newNode = new Node(key)            //2.判斷根節點是否存在          if (this.root == null) {            this.root = newNode            //根節點存在時          }else {            this.insertNode(this.root, newNode)          }        }          //內部使用的insertNode方法:用於比較節點從左邊插入還是右邊插入        BinarySearchTree.prototype.insertNode = function(node, newNode){          //當newNode.key < node.key向左查找          if(newNode.key < node.key){            //情況1：node無左子節點，直接插入            if (node.left == null) {              node.left = newNode            //情況2：node有左子節點，遞歸調用insertNode(),直到遇到無左子節點成功插入newNode後，不再符合該情況，也就不再調用insertNode()，遞歸停止。            }else{              this.insertNode(node.left, newNode)            }          //當newNode.key >= node.key向右查找          }else{            //情況1：node無右子節點，直接插入            if(node.right == null){              node.right = newNode            //情況2：node有右子節點，依然遞歸調用insertNode(),直到遇到無右子節點成功插入newNode為止            }else{              this.insertNode(node.right, newNode)            }          }        }          //二.樹的遍歷        //1.先序遍歷        //摻入一個handler函數對得到的key進行處理        BinarySearchTree.prototype.preOrderTraversal = function(handler){          this.preOrderTraversalNode(this.root, handler)        }          //封裝內部方法，對某個節點進行遍歷        BinarySearchTree.prototype.preOrderTraversalNode = function(node,handler){          if (node != null) {            //1.處理經過的節點            handler(node.key)              //2.遍歷經過節點的左子節點            this.preOrderTraversalNode(node.left, handler)              //3.遍歷經過節點的右子節點            this.preOrderTraversalNode(node.right, handler)          }        }          //2.中序遍歷        BinarySearchTree.prototype.midOrderTraversal = function(handler){          this.midOrderTraversalNode(this.root, handler)        }          BinarySearchTree.prototype.midOrderTraversalNode = function(node, handler){          if (node != null) {            //1.遍歷左子樹中的節點            this.midOrderTraversalNode(node.left, handler)              //2.處理節點            handler(node.key)              //3.遍歷右子樹中的節點            this.midOrderTraversalNode(node.right, handler)          }        }          //3.後序遍歷        BinarySearchTree.prototype.postOrderTraversal = function(handler){          this.postOrderTraversalNode(this.root, handler)        }          BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler){          if (node != null) {            //1.遍歷左子樹中的節點            this.postOrderTraversalNode(node.left, handler)              //2.遍歷右子樹中的節點            this.postOrderTraversalNode(node.right, handler)              //3.處理節點            handler(node.key)          }        }          //三.尋找最值        //尋找最大值        BinarySearchTree.prototype.max = function () {          //1.獲取根節點          let node = this.root          //2.定義key保存節點值          let key = null          //3.依次向右不斷查找，直到節點為null          while (node != null) {            key = node.key            node = node.right          }          return key        }          //尋找最小值        BinarySearchTree.prototype.min = function(){           //1.獲取根節點           let node = this.root          //2.定義key保存節點值          let key = null          //3.依次向左不斷查找，直到節點為null          while (node != null) {            key = node.key            node = node.left          }          return key        }          //查找特定的key        BinarySearchTree.prototype.search = function(key){          //1.獲取根節點          let node = this.root            //2.循環搜索key          while(node != null){            if (key < node.key) {              //小於根(父)節點就往左邊找              node = node.left              //大於根(父)節點就往右邊找            }else if(key > node.key){              node = node.right            }else{              return true            }          }          return false        }          //四.刪除節點        BinarySearchTree.prototype.remove = function(key){  /*------------------------------1.尋找要刪除的節點---------------------------------*/          //1.1.定義變數current保存刪除的節點，parent保存它的父節點。isLeftChild保存current是否為parent的左節點          let current = this.root          let parent = null          let isLeftChild = true            //1.2.開始尋找刪除的節點          while (current.key != key) {            parent = current            // 小於則往左查找            if (key < current.key) {              isLeftChild = true              current = current.left            } else{              isLeftChild = false              current = current.right            }            //找到最後依然沒有找到相等的節點            if (current == null) {              return false            }          }          //結束while循環後：current.key = key    /*------------------------------2.根據對應情況刪除節點------------------------------*/          //情況1：刪除的是葉子節點(沒有子節點)          if (current.left == null && current.right ==null) {            if (current == this.root) {              this.root = null            }else if(isLeftChild){              parent.left = null            }else {              parent.right =null            }          }          //情況2：刪除的節點有一個子節點          //當current存在左子節點時          else if(current.right == null){              if (current == this.root) {                this.root = current.left              } else if(isLeftChild) {                  parent.left = current.left              } else{                  parent.right = current.left              }          //當current存在右子節點時        } else if(current.left == null){              if (current == this.root) {                this.root = current.right              } else if(isLeftChild) {                  parent.left = current.right              } else{                  parent.right = current.right              }        }          //情況3：刪除的節點有兩個子節點          else{            //1.獲取後繼節點            let successor = this.getSuccessor(current)              //2.判斷是否根節點            if (current == this.root) {              this.root = successor            }else if (isLeftChild){              parent.left = successor            }else{              parent.right = successor            }              //3.將後繼的左子節點改為被刪除節點的左子節點            successor.left = current.left          }        }          //封裝查找後繼的方法        BinarySearchTree.prototype.getSuccessor = function(delNode){          //1.定義變數,保存找到的後繼          let successor = delNode          let current = delNode.right          let successorParent = delNode            //2.循環查找current的右子樹節點          while(current != null){            successorParent = successor            successor = current            current = current.left          }            //3.判斷尋找到的後繼節點是否直接就是刪除節點的right節點          if(successor != delNode.right){            successorParent.left = successor.right            successor.right = delNode.right          }          return successor        }      }

二、平衡樹

二叉搜索樹的缺陷：

當插入的數據是有序的數據，就會造成二叉搜索樹的深度過大。比如原二叉搜索樹右 11 7 15 組成，如下圖所示：

當插入一組有序數據：6 5 4 3 2就會變成深度過大的搜索二叉樹，會嚴重影響二叉搜索樹的性能。

非平衡樹

• 比較好的二叉搜索樹，它的數據應該是左右均勻分布的；
• 但是插入連續數據後，二叉搜索樹中的數據分布就變得不均勻了，我們稱這種樹為非平衡樹；
• 對於一棵平衡二叉樹來說，插入/查找等操作的效率是O（logN）；
• 而對於一棵非平衡二叉樹來說，相當於編寫了一個鏈表，查找效率變成了O（N）;

樹的平衡性

為了能以較快的時間O（logN）來操作一棵樹，我們需要保證樹總是平衡的：

• 起碼大部分是平衡的，此時的時間複雜度也是接近O（logN）的；
• 這就要求樹中每個節點左邊的子孫節點的個數，應該儘可能地等於右邊的子孫節點的個數；

常見的平衡樹

• AVL樹：是最早的一種平衡樹，它通過在每個節點多存儲一個額外的數據來保持樹的平衡。由於AVL樹是平衡樹，所以它的時間複雜度也是O（logN）。但是它的整體效率不如紅黑樹，開發中比較少用。
• 紅黑樹：同樣通過一些特性來保持樹的平衡，時間複雜度也是O（logN）。進行插入/刪除等操作時，性能優於AVL樹，所以平衡樹的應用基本都是紅黑樹。

參考資料：JavaScript數據結構與演算法