怎么利用JavaScript實(shí)現(xiàn)二叉搜索樹(shù)

這篇文章給大家分享的是有關(guān)怎么利用JavaScript實(shí)現(xiàn)二叉搜索樹(shù)的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

計(jì)算機(jī)科學(xué)中最常用和討論最多的數(shù)據(jù)結(jié)構(gòu)之一是二叉搜索樹(shù)。這通常是引入的第一個(gè)具有非線性插入算法的數(shù)據(jù)結(jié)構(gòu)。二叉搜索樹(shù)類似于雙鏈表，每個(gè)節(jié)點(diǎn)包含一些數(shù)據(jù)，以及兩個(gè)指向其他節(jié)點(diǎn)的指針；它們?cè)谶@些節(jié)點(diǎn)彼此相關(guān)聯(lián)的方式上有所不同。二叉搜索樹(shù)節(jié)點(diǎn)的指針通常被稱為“左”和“右”，用來(lái)指示與當(dāng)前值相關(guān)的子樹(shù)。這種節(jié)點(diǎn)的簡(jiǎn)單 JavaScript 實(shí)現(xiàn)如下：

var node = {
  value: 125,
  left: null,
  right: null
};

從名稱中可以看出，二叉搜索樹(shù)被組織成分層的樹(shù)狀結(jié)構(gòu)。第一個(gè)項(xiàng)目成為根節(jié)點(diǎn)，每個(gè)附加值作為該根的祖先添加到樹(shù)中。但是，二叉搜索樹(shù)節(jié)點(diǎn)上的值是唯一的，根據(jù)它們包含的值進(jìn)行排序：作為節(jié)點(diǎn)左子樹(shù)的值總是小于節(jié)點(diǎn)的值，右子樹(shù)中的值都是大于節(jié)點(diǎn)的值。通過(guò)這種方式，在二叉搜索樹(shù)中查找值變得非常簡(jiǎn)單，只要你要查找的值小于正在處理的節(jié)點(diǎn)則向左，如果值更大，則向右移動(dòng)。二叉搜索樹(shù)中不能有重復(fù)項(xiàng)，因?yàn)橹貜?fù)會(huì)破壞這種關(guān)系。下圖表示一個(gè)簡(jiǎn)單的二叉搜索樹(shù)。

上圖表示一個(gè)二叉搜索樹(shù)，其根的值為 8。當(dāng)添加值 3 時(shí)，它成為根的左子節(jié)點(diǎn)，因?yàn)?3 小于 8。當(dāng)添加值 1 時(shí)，它成為 3 的左子節(jié)點(diǎn)，因?yàn)?1 小于 8（所以向左）然后 1 小于3（再向左）。當(dāng)添加值 10 時(shí)，它成為跟的右子節(jié)點(diǎn)，因?yàn)?10 大于 8。不斷用此過(guò)程繼續(xù)處理值 6，4，7，14 和 13。此二叉搜索樹(shù)的深度為 3，表示距離根最遠(yuǎn)的節(jié)點(diǎn)是三個(gè)節(jié)點(diǎn)。

二叉搜索樹(shù)以自然排序的順序結(jié)束，因此可用于快速查找數(shù)據(jù)，因?yàn)槟憧梢粤⒓聪總€(gè)步驟的可能性。通過(guò)限制需要查找的節(jié)點(diǎn)數(shù)量，可以更快地進(jìn)行搜索。假設(shè)你要在上面的樹(shù)中找到值 6。從根開(kāi)始，確定 6 小于 8，因此前往根的左子節(jié)點(diǎn)。由于 6 大于 3，因此你將前往右側(cè)節(jié)點(diǎn)。你就能找到正確的值。所以你只需訪問(wèn)三個(gè)而不是九個(gè)節(jié)點(diǎn)來(lái)查找這個(gè)值。

要在 JavaScript 中實(shí)現(xiàn)二叉搜索樹(shù)，第一步要先定義基本接口：

function BinarySearchTree() {
  this._root = null;
}

BinarySearchTree.prototype = {

  //restore constructor
  constructor: BinarySearchTree,

  add: function (value){
  },

  contains: function(value){
  },

  remove: function(value){
  },

  size: function(){
  },

  toArray: function(){
  },

  toString: function(){
  }

};

基本接與其他數(shù)據(jù)結(jié)構(gòu)類似，有添加和刪除值的方法。我還添加了一些方便的方法，size()，toArray()和toString()，它們對(duì) JavaScript 很有用。

要掌握使用二叉搜索樹(shù)的方法，最好從 contains() 方法開(kāi)始。contains() 方法接受一個(gè)值作為參數(shù)，如果值存在于樹(shù)中則返回 true，否則返回 false。此方法遵循基本的二叉搜索算法來(lái)確定該值是否存在：

BinarySearchTree.prototype = {

  //more code

  contains: function(value){
    var found    = false,
      current   = this._root

    //make sure there's a node to search
    while(!found && current){

      //if the value is less than the current node's, go left
      if (value < current.value){
        current = current.left;

      //if the value is greater than the current node's, go right
      } else if (value > current.value){
        current = current.right;

      //values are equal, found it!
      } else {
        found = true;
      }
    }

    //only proceed if the node was found
    return found;
  },

  //more code

};

搜索從樹(shù)的根開(kāi)始。如果沒(méi)有添加數(shù)據(jù)，則可能沒(méi)有根，所以必須要進(jìn)行檢查。遍歷樹(shù)遵循前面討論的簡(jiǎn)單算法：如果要查找的值小于當(dāng)前節(jié)點(diǎn)則向左移動(dòng)，如果值更大則向右移動(dòng)。每次都會(huì)覆蓋 current 指針，直到找到要找的值（在這種情況下 found 設(shè)置為 true）或者在那個(gè)方向上沒(méi)有更多的節(jié)點(diǎn)了（在這種情況下，值不在樹(shù)上）。

在 contains() 中使用的方法也可用于在樹(shù)中插入新值。主要區(qū)別在于你要尋找放置新值的位置，而不是在樹(shù)中查找值：

BinarySearchTree.prototype = {

  //more code

  add: function(value){
    //create a new item object, place data in
    var node = {
        value: value,
        left: null,
        right: null
      },

      //used to traverse the structure
      current;

    //special case: no items in the tree yet
    if (this._root === null){
      this._root = node;
    } else {
      current = this._root;

      while(true){

        //if the new value is less than this node's value, go left
        if (value < current.value){

          //if there's no left, then the new node belongs there
          if (current.left === null){
            current.left = node;
            break;
          } else {
            current = current.left;
          }

        //if the new value is greater than this node's value, go right
        } else if (value > current.value){

          //if there's no right, then the new node belongs there
          if (current.right === null){
            current.right = node;
            break;
          } else {
            current = current.right;
          }   

        //if the new value is equal to the current one, just ignore
        } else {
          break;
        }
      }
    }
  },

  //more code

};

在二叉搜索樹(shù)中添加值時(shí)，特殊情況是在沒(méi)有根的情況。在這種情況下，只需將根設(shè)置為新值即可輕松完成工作。對(duì)于其他情況，基本算法與 contains() 中使用的基本算法完全相同：新值小于當(dāng)前節(jié)點(diǎn)向左，如果值更大則向右。主要區(qū)別在于，當(dāng)你無(wú)法繼續(xù)前進(jìn)時(shí)，這就是新值的位置。所以如果你需要向左移動(dòng)但沒(méi)有左側(cè)節(jié)點(diǎn)，則新值將成為左側(cè)節(jié)點(diǎn)（與右側(cè)節(jié)點(diǎn)相同）。由于不存在重復(fù)項(xiàng)，因此如果找到具有相同值的節(jié)點(diǎn)，則操作將停止。

在繼續(xù)討論 size() 方法之前，我想深入討論樹(shù)遍歷。為了計(jì)算二叉搜索樹(shù)的大小，必須要訪問(wèn)樹(shù)中的每個(gè)節(jié)點(diǎn)。二叉搜索樹(shù)通常會(huì)有不同類型的遍歷方法，最常用的是有序遍歷。通過(guò)處理左子樹(shù)，然后是節(jié)點(diǎn)本身，然后是右子樹(shù)，在每個(gè)節(jié)點(diǎn)上執(zhí)行有序遍歷。由于二叉搜索樹(shù)以這種方式排序，從左到右，結(jié)果是節(jié)點(diǎn)以正確的排序順序處理。對(duì)于 size() 方法，節(jié)點(diǎn)遍歷的順序?qū)嶋H上并不重要，但它對(duì) toArray() 方法很重要。由于兩種方法都需要執(zhí)行遍歷，我決定添加一個(gè)可以通用的 traverse() 方法：

BinarySearchTree.prototype = {

  //more code

  traverse: function(process){

    //helper function
    function inOrder(node){
      if (node){

        //traverse the left subtree
        if (node.left !== null){
          inOrder(node.left);
        }      

        //call the process method on this node
        process.call(this, node);

        //traverse the right subtree
        if (node.right !== null){
          inOrder(node.right);
        }
      }
    }

    //start with the root
    inOrder(this._root);
  },

  //more code

};

此方法接受一個(gè)參數(shù) process，這是一個(gè)應(yīng)該在樹(shù)中的每個(gè)節(jié)點(diǎn)上運(yùn)行的函數(shù)。該方法定義了一個(gè)名為 inOrder() 的輔助函數(shù)用于遞歸遍歷樹(shù)。注意，如果當(dāng)前節(jié)點(diǎn)存在，則遞歸僅左右移動(dòng)（以避免多次處理 null ）。然后 traverse() 方法從根節(jié)點(diǎn)開(kāi)始按順序遍歷，process() 函數(shù)處理每個(gè)節(jié)點(diǎn)。然后可以使用此方法實(shí)現(xiàn)size()、toArray()、toString()：

BinarySearchTree.prototype = {

  //more code

  size: function(){
    var length = 0;

    this.traverse(function(node){
      length++;
    });

    return length;
  },

  toArray: function(){
    var result = [];

    this.traverse(function(node){
      result.push(node.value);
    });

    return result;
  },

  toString: function(){
    return this.toArray().toString();
  },

  //more code

};

size() 和 toArray() 都調(diào)用 traverse() 方法并傳入一個(gè)函數(shù)來(lái)在每個(gè)節(jié)點(diǎn)上運(yùn)行。在使用 size()的情況下，函數(shù)只是遞增長(zhǎng)度變量，而 toArray() 使用函數(shù)將節(jié)點(diǎn)的值添加到數(shù)組中。toString()方法在調(diào)用 toArray() 之前把返回的數(shù)組轉(zhuǎn)換為字符串，并返回  。

刪除節(jié)點(diǎn)時(shí)，你需要確定它是否為根節(jié)點(diǎn)。根節(jié)點(diǎn)的處理方式與其他節(jié)點(diǎn)類似，但明顯的例外是根節(jié)點(diǎn)需要在結(jié)尾處設(shè)置為不同的值。為簡(jiǎn)單起見(jiàn)，這將被視為 JavaScript 代碼中的一個(gè)特例。

刪除節(jié)點(diǎn)的第一步是確定節(jié)點(diǎn)是否存在：

BinarySearchTree.prototype = {

  //more code here

  remove: function(value){

    var found    = false,
      parent   = null,
      current   = this._root,
      childCount,
      replacement,
      replacementParent;

    //make sure there's a node to search
    while(!found && current){

      //if the value is less than the current node's, go left
      if (value < current.value){
        parent = current;
        current = current.left;

      //if the value is greater than the current node's, go right
      } else if (value > current.value){
        parent = current;
        current = current.right;

      //values are equal, found it!
      } else {
        found = true;
      }
    }

    //only proceed if the node was found
    if (found){
      //continue
    }

  },
  //more code here

};

remove()方法的第一部分是用二叉搜索定位要被刪除的節(jié)點(diǎn)，如果值小于當(dāng)前節(jié)點(diǎn)的話則向左移動(dòng)，如果值大于當(dāng)前節(jié)點(diǎn)則向右移動(dòng)。當(dāng)遍歷時(shí)還會(huì)跟蹤 parent 節(jié)點(diǎn)，因?yàn)槟阕罱K需要從其父節(jié)點(diǎn)中刪除該節(jié)點(diǎn)。當(dāng) found 等于 true 時(shí)，current 的值是要?jiǎng)h除的節(jié)點(diǎn)。

刪除節(jié)點(diǎn)時(shí)需要注意三個(gè)條件：

1. 葉子節(jié)點(diǎn)

2. 只有一個(gè)孩子的節(jié)點(diǎn)

3. 有兩個(gè)孩子的節(jié)點(diǎn)
   

從二叉搜索樹(shù)中刪除除了葉節(jié)點(diǎn)之外的內(nèi)容意味著必須移動(dòng)值來(lái)對(duì)樹(shù)正確的排序。前兩個(gè)實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，只刪除了一個(gè)葉子節(jié)點(diǎn)，刪除了一個(gè)帶有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)并用其子節(jié)點(diǎn)替換。最后一種情況有點(diǎn)復(fù)雜，以便稍后訪問(wèn)。

在了解如何刪除節(jié)點(diǎn)之前，你需要知道節(jié)點(diǎn)上究竟存在多少個(gè)子節(jié)點(diǎn)。一旦知道了，你必須確定節(jié)點(diǎn)是否為根節(jié)點(diǎn)，留下一個(gè)相當(dāng)簡(jiǎn)單的決策樹(shù)：

BinarySearchTree.prototype = {

  //more code here

  remove: function(value){

    var found    = false,
      parent   = null,
      current   = this._root,
      childCount,
      replacement,
      replacementParent;

    //find the node (removed for space)

    //only proceed if the node was found
    if (found){

      //figure out how many children
      childCount = (current.left !== null ? 1 : 0) + 
             (current.right !== null ? 1 : 0);

      //special case: the value is at the root
      if (current === this._root){
        switch(childCount){

          //no children, just erase the root
          case 0:
            this._root = null;
            break;

          //one child, use one as the root
          case 1:
            this._root = (current.right === null ? 
                   current.left : current.right);
            break;

          //two children, little work to do
          case 2:

            //TODO

          //no default

        }    

      //non-root values
      } else {

        switch (childCount){

          //no children, just remove it from the parent
          case 0:
            //if the current value is less than its 
            //parent's, null out the left pointer
            if (current.value < parent.value){
              parent.left = null;

            //if the current value is greater than its
            //parent's, null out the right pointer
            } else {
              parent.right = null;
            }
            break;

          //one child, just reassign to parent
          case 1:
            //if the current value is less than its 
            //parent's, reset the left pointer
            if (current.value < parent.value){
              parent.left = (current.left === null ? 
                      current.right : current.left);

            //if the current value is greater than its 
            //parent's, reset the right pointer
            } else {
              parent.right = (current.left === null ? 
                      current.right : current.left);
            }
            break;  

          //two children, a bit more complicated
          case 2:

            //TODO     

          //no default

        }

      }

    }

  },

  //more code here

};

處理根節(jié)點(diǎn)時(shí)，這是一個(gè)覆蓋它的簡(jiǎn)單過(guò)程。對(duì)于非根節(jié)點(diǎn)，必須根據(jù)要?jiǎng)h除的節(jié)點(diǎn)的值設(shè)置 parent 上的相應(yīng)指針：如果刪除的值小于父節(jié)點(diǎn)，則 left 指針必須重置為 null（對(duì)于沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)）或刪除節(jié)點(diǎn)的 left 指針；如果刪除的值大于父級(jí)，則必須將 right 指針重置為 null 或刪除的節(jié)點(diǎn)的 right指針。

如前所述，刪除具有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)是最復(fù)雜的操作。下圖是兒茶搜索樹(shù)的一種表示。

根為 8，左子為 3，如果 3 被刪除會(huì)發(fā)生什么？有兩種可能性：1（3 左邊的孩子，稱為有序前身）或4（右子樹(shù)的最左邊的孩子，稱為有序繼承者）都可以取代 3。

這兩個(gè)選項(xiàng)中的任何一個(gè)都是合適的。要查找有序前驅(qū)，即刪除值之前的值，請(qǐng)檢查要?jiǎng)h除的節(jié)點(diǎn)的左子樹(shù)，并選擇最右側(cè)的子節(jié)點(diǎn)；找到有序后繼，在刪除值后立即出現(xiàn)的值，反轉(zhuǎn)進(jìn)程并檢查最左側(cè)的右子樹(shù)。其中每個(gè)都需要另一次遍歷樹(shù)來(lái)完成操作：

BinarySearchTree.prototype = {

  //more code here

  remove: function(value){

    var found    = false,
      parent   = null,
      current   = this._root,
      childCount,
      replacement,
      replacementParent;

    //find the node (removed for space)

    //only proceed if the node was found
    if (found){

      //figure out how many children
      childCount = (current.left !== null ? 1 : 0) + 
             (current.right !== null ? 1 : 0);

      //special case: the value is at the root
      if (current === this._root){
        switch(childCount){

          //other cases removed to save space

          //two children, little work to do
          case 2:

            //new root will be the old root's left child
            //...maybe
            replacement = this._root.left;

            //find the right-most leaf node to be 
            //the real new root
            while (replacement.right !== null){
              replacementParent = replacement;
              replacement = replacement.right;
            }

            //it's not the first node on the left
            if (replacementParent !== null){

              //remove the new root from it's 
              //previous position
              replacementParent.right = replacement.left;

              //give the new root all of the old 
              //root's children
              replacement.right = this._root.right;
              replacement.left = this._root.left;
            } else {

              //just assign the children
              replacement.right = this._root.right;
            }

            //officially assign new root
            this._root = replacement;

          //no default

        }    

      //non-root values
      } else {

        switch (childCount){

          //other cases removed to save space

          //two children, a bit more complicated
          case 2:

            //reset pointers for new traversal
            replacement = current.left;
            replacementParent = current;

            //find the right-most node
            while(replacement.right !== null){
              replacementParent = replacement;
              replacement = replacement.right;
            }

            replacementParent.right = replacement.left;

            //assign children to the replacement
            replacement.right = current.right;
            replacement.left = current.left;

            //place the replacement in the right spot
            if (current.value < parent.value){
              parent.left = replacement;
            } else {
              parent.right = replacement;
            }     

          //no default

        }

      }

    }

  },

  //more code here

};

具有兩個(gè)子節(jié)點(diǎn)的根節(jié)點(diǎn)和非根節(jié)點(diǎn)的代碼幾乎相同。此實(shí)現(xiàn)始終通過(guò)查看左子樹(shù)并查找最右側(cè)子節(jié)點(diǎn)來(lái)查找有序前驅(qū)。遍歷是使用 while 循環(huán)中的 replacement 和 replacementParent 變量完成的。replacement中的節(jié)點(diǎn)最終成為替換 current 的節(jié)點(diǎn)，因此通過(guò)將其父級(jí)的 right 指針設(shè)置為替換的 left 指針，將其從當(dāng)前位置移除。對(duì)于根節(jié)點(diǎn)，當(dāng) replacement 是根節(jié)點(diǎn)的直接子節(jié)點(diǎn)時(shí)，replacementParent 將為 null，因此 replacement 的 right 指針只是設(shè)置為 root 的 right 指針。最后一步是將替換節(jié)點(diǎn)分配到正確的位置。對(duì)于根節(jié)點(diǎn)，替換設(shè)置為新根；對(duì)于非根節(jié)點(diǎn)，替換被分配到原始 parent 上的適當(dāng)位置。

說(shuō)明：始終用有序前驅(qū)替換節(jié)點(diǎn)可能導(dǎo)致不平衡樹(shù)，其中大多數(shù)值會(huì)位于樹(shù)的一側(cè)。不平衡樹(shù)意味著搜索效率較低，因此在實(shí)際場(chǎng)景中應(yīng)該引起關(guān)注。在二叉搜索樹(shù)實(shí)現(xiàn)中，要確定是用有序前驅(qū)還是有序后繼以使樹(shù)保持適當(dāng)平衡（通常稱為自平衡二叉搜索樹(shù)）。

感謝各位的閱讀！關(guān)于“怎么利用JavaScript實(shí)現(xiàn)二叉搜索樹(shù)”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！