什么是二叉樹

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

什么是二叉搜索樹

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

二叉搜索樹的特性

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

二叉搜索樹的構造

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

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就是當前對象的樹。

二叉搜索樹的新增

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

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與當前節(jié)點的key大小，如果小，就遞歸遍歷左子節(jié)點，直到找到一個為null的左子節(jié)點；如果比當前節(jié)點大同理。如上代碼{1}{2}{3}{4}之所以能改變this.root的值，是由于JavaScript函數(shù)是按值傳遞，而當參數(shù)是非基本類型時，例如這里的對象，其對象的值為內(nèi)存，因此每次都會直接改變this.root的內(nèi)容。

二叉搜索樹的遍歷

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

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

如上是中序遍歷。

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

其會從11開始，執(zhí)行{1}入棧，然后進入7，接著執(zhí)行{1}入棧，然后到5，執(zhí)行{1}入棧，再到3，執(zhí)行{1}入棧，此時發(fā)現(xiàn)節(jié)點3的左子節(jié)點為null，因此開始出棧，此時彈出節(jié)點3的執(zhí)行環(huán)境，執(zhí)行{2}，{3}，發(fā)現(xiàn)3的右側子節(jié)點也為null，{3}的遞歸執(zhí)行完畢，接著彈出節(jié)點5，執(zhí)行{2}{3}，接著彈出7，執(zhí)行{2}{3}入棧，執(zhí)行{3}時，發(fā)現(xiàn)節(jié)點7有右節(jié)點，因此繼續(xù)執(zhí)行{1}，到節(jié)點8，再執(zhí)行{1}，8沒有左子節(jié)點，{1}執(zhí)行完畢，執(zhí)行{2}{3}，以此類推。

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

后序同理，執(zhí)行順序為1 3 2

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

二叉搜索樹的查找

查找很簡單，根據(jù)左子節(jié)點比該節(jié)點小，右子節(jié)點比該節(jié)點大的原則進行循環(huán)判斷即可。

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

二叉搜索樹的刪除

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

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

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

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 {
  // 如果沒有左子樹，那么將右子樹根節(jié)點作為替換節(jié)點
  if (!node.left) {
   return node.right;
   // 如果存在左子樹，那么取右子樹最小節(jié)點作為替換節(jié)點
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}

總結

總的來說，通過這次簡單的二叉搜索樹的學習，讓我重新認識了遞歸，以前對于遞歸的理解只是一些簡單的理論概念，這次深入實踐讓我對遞歸的理解又加深了許多。

這讓我想到了數(shù)學的學習，數(shù)學的理論公式是很容易記住掌握的，如果說對一個知識點的掌握滿分是十分，那么直到真正去實踐它之前，只看公式的掌握只能是2分，因為公式很簡單，就幾句話幾個原則，但是遇到的問題是千變?nèi)f化的，只有真正將理論付諸實踐，經(jīng)過各種實踐的打磨蹂躪，才能真正理解它其中的奧秘。

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論