什么是二叉樹

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

什么是二叉搜索樹

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

二叉搜索樹的特性

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

二叉搜索樹的構(gòu)造

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

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

接著構(gòu)造二叉搜索樹

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

這里this.root就是當(dāng)前對象的樹。

二叉搜索樹的新增

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

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

如上是中序遍歷。

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

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

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

后序同理，執(zhí)行順序?yàn)? 3 2

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

二叉搜索樹的查找

查找很簡單，根據(jù)左子節(jié)點(diǎn)比該節(jié)點(diǎn)小，右子節(jié)點(diǎn)比該節(jié)點(diǎn)大的原則進(jìn)行循環(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);
 }
}

二叉搜索樹的刪除

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

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

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

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

總結(jié)

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

這讓我想到了數(shù)學(xué)的學(xué)習(xí)，數(shù)學(xué)的理論公式是很容易記住掌握的，如果說對一個(gè)知識(shí)點(diǎn)的掌握滿分是十分，那么直到真正去實(shí)踐它之前，只看公式的掌握只能是2分，因?yàn)楣胶芎唵危蛶拙湓拵讉€(gè)原則，但是遇到的問題是千變?nèi)f化的，只有真正將理論付諸實(shí)踐，經(jīng)過各種實(shí)踐的打磨蹂躪，才能真正理解它其中的奧秘。

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

最新評論