使用javascript在實現一個二叉搜索樹算法

這篇文章將為大家詳細講解有關使用javascript在實現一個二叉搜索樹算法，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

什么是二叉樹

二叉樹就是樹的每個節點最多只能有兩個子節點

什么是二叉搜索樹

二叉搜索樹在二叉樹的基礎上，多了一個條件，就是二叉樹在插入值時，若插入值比當前節點小，就插入到左節點，否則插入到右節點；若插入過程中，左節點或右節點已經存在，那么繼續按如上規則比較，直到遇到一個新的節點。

二叉搜索樹的特性

二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是O(h)，h為二叉樹的高度。因此二叉樹應該盡量的矮，即左右節點盡量平衡。

二叉搜索樹的構造

要構造二叉搜索樹，首先要構造二叉樹的節點類。由二叉樹的特點可知，每個節點類都有一個左節點，右節點以及值本身，因此節點類如下：

class Node {
 constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

接著構造二叉搜索樹

class Tree{
 constructor(param = null) {
  if (param) {
   this.root = new Node(param);
  } else {
   this.root = null;
  }
 }
}

這里this.root就是當前對象的樹。

二叉搜索樹的新增

由二叉搜索樹左子樹比節點小，右子樹別節點大的特點，可以很簡單的寫出二叉搜索樹新增的算法，如下：

insert(key) {
 if (this.root === null) {
  this.root = new Node(key);
 } else {
  this._insertNode(this.root, key);
 }
}
_insertNode(node, key) {
 if (key < node.key) {
  if (node.left === null) {
   node.left = new Node(key);{1}
  } else {
   this._insertNode(node.left, key);{2}
  }
 } else if (key > node.key) {
  if (node.right === null) {
   node.right = new Node(key);{3}
  } else {
   this._insertNode(node.right, key);{4}
  }
 }
}

如上代碼先判斷新增的key與當前節點的key大小，如果小，就遞歸遍歷左子節點，直到找到一個為null的左子節點；如果比當前節點大同理。如上代碼{1}{2}{3}{4}之所以能改變this.root的值，是由于JavaScript函數是按值傳遞，而當參數是非基本類型時，例如這里的對象，其對象的值為內存，因此每次都會直接改變this.root的內容。

二叉搜索樹的遍歷

二叉搜索樹分為先序、中序、后序三種遍歷方式。

inOrderTraverse(callback) {
 this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
 if (node) {
  this._inOrderTraverse(node.left, callback);
  callback(node.key);
  this._inOrderTraverse(node.right, callback);
 }
}

如上是中序遍歷。

這里需要理解的一點是遞歸。要知道，函數的執行可以抽象為一種數據結構——棧。針對函數的執行，會維護一個棧，來存儲函數的執行。函數在每一次遞歸時，都會將當前的執行環境入棧并記錄執行的位置。以上述代碼為例，有如下一個數據

其會從11開始，執行{1}入棧，然后進入7，接著執行{1}入棧，然后到5，執行{1}入棧，再到3，執行{1}入棧，此時發現節點3的左子節點為null，因此開始出棧，此時彈出節點3的執行環境，執行{2}，{3}，發現3的右側子節點也為null，{3}的遞歸執行完畢，接著彈出節點5，執行{2}{3}，接著彈出7，執行{2}{3}入棧，執行{3}時，發現節點7有右節點，因此繼續執行{1}，到節點8，再執行{1}，8沒有左子節點，{1}執行完畢，執行{2}{3}，以此類推。

而前序與中序的不同點在于其先訪問節點本身，也就是代碼的執行順序為 2 1 3。

后序同理，執行順序為1 3 2

不難發現，無論前中后序，永遠都是先遞歸左節點，當左節點遍歷完畢時再彈出棧，遍歷有節點。他們唯一不同的點在與訪問該節點本身的時機。

二叉搜索樹的查找

查找很簡單，根據左子節點比該節點小，右子節點比該節點大的原則進行循環判斷即可。

search(value) {
 if (this.root) {
  if (value === this.root.key) {
   return true;
  } else {
   return this._searchNode(value, this.root);
  }
 }
 throw new Error('this.root 不存在');
}
_searchNode(value, node) {
 if (!node) {
  return false;
 }
 if (value === node.key) {
  return true;
 }
 if (value > node.key) {
  return this._searchNode(value, node.right);
 } else if (value < node.key) {
  return this._searchNode(value, node.left);
 }
}

二叉搜索樹的刪除

刪除較為復雜，需要根據不同情況判斷

首先判斷該節點是否有左子樹，如果沒有左子節樹，則直接將右子樹的根節點替換被刪除節點；

如果有，則將右子樹的最小節點替換被刪除節點；

remove(key) {
 this._removeNode(this.root, key);
}
_removeNode(node, value) {
 if (!node) {
  return null;
 }
 if (value > node.key) {
  node.right = this._removeNode(node.right, value);
 } else if (value < node.key) {
  node.left = this._removeNode(node.left, value);
 } else {
  // 如果沒有左子樹，那么將右子樹根節點作為替換節點
  if (!node.left) {
   return node.right;
   // 如果存在左子樹，那么取右子樹最小節點作為替換節點
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}

關于使用javascript在實現一個二叉搜索樹算法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。