摘要：二叉搜索樹(shù)的特性二叉搜索樹(shù)由于其獨(dú)特的數(shù)據(jù)結(jié)構(gòu)，使得其無(wú)論在增刪，還是查找，時(shí)間復(fù)雜度都是，為二叉樹(shù)的高度。二叉搜索樹(shù)的查找查找很簡(jiǎn)單，根據(jù)左子節(jié)點(diǎn)比該節(jié)點(diǎn)小，右子節(jié)點(diǎn)比該節(jié)點(diǎn)大的原則進(jìn)行循環(huán)判斷即可。

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

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

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

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

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

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

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

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

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

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ù)是非基本類(lèi)型時(shí)，例如這里的對(duì)象，其對(duì)象的值為內(nèi)存，因此每次都會(huì)直接改變this.root的內(nèi)容。

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

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)——棧。針對(duì)函數(shù)的執(zhí)行，會(huì)維護(hù)一個(gè)棧，來(lái)存儲(chǔ)函數(shù)的執(zhí)行。函數(shù)在每一次遞歸時(shí)，都會(huì)將當(dāng)前的執(zhí)行環(huán)境入棧并記錄執(zhí)行的位置。以上述代碼為例，有如下一個(gè)數(shù)據(jù)

其會(huì)從11開(kāi)始，執(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，因此開(kāi)始出棧，此時(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沒(méi)有左子節(jié)點(diǎn)，{1}執(zhí)行完畢，執(zhí)行{2}{3}，以此類(lèi)推。
而前序與中序的不同點(diǎn)在于其先訪問(wèn)節(jié)點(diǎn)本身，也就是代碼的執(zhí)行順序?yàn)?2 1 3。
后序同理，執(zhí)行順序?yàn)? 3 2
不難發(fā)現(xiàn)，無(wú)論前中后序，永遠(yuǎn)都是先遞歸左節(jié)點(diǎn)，當(dāng)左節(jié)點(diǎn)遍歷完畢時(shí)再?gòu)棾鰲?，遍歷有節(jié)點(diǎn)。他們唯一不同的點(diǎn)在與訪問(wèn)該節(jié)點(diǎn)本身的時(shí)機(jī)。

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

search(value) {
  return this._search(value, this.root);
}
_search(value, node) {
  if (node === null) {
    return false;
  } else if (value > node.value) {
    return this._search(value, node.right);
  } else if (value < node.value) {
    return this._search(value, node.left);
  } else {
    return true;
  }
}

刪除較為復(fù)雜，需要根據(jù)不同情況判斷
首先判斷該節(jié)點(diǎn)是否有左子樹(shù)，如果沒(méi)有左子節(jié)樹(shù)，則直接將右子樹(shù)的根節(jié)點(diǎn)替換被刪除節(jié)點(diǎn)；
如果有，則將右子樹(shù)的最小節(jié)點(diǎn)替換被刪除節(jié)點(diǎn)；

remove(value) {
  this.root = this._removeNode(this.root, value);
}
_removeNode(node, value) {
  if (!node) {
    return null;
  }
  if (value > node.value) {
    node.right = this._removeNode(node.right, value);
    return node;
  } else if (value < node.value) {
    console.log(value);
    node.left = this._removeNode(node.left, value);
    return node;
  } else {
    // 如果左右子節(jié)點(diǎn)都沒(méi)有
    if (!node.left && !node.right) {
      return null;
    }
    // 如果只有一個(gè)子節(jié)點(diǎn)
    if (node.left === null) {
      return node.right;
    }
    if (node.right === null) {
      return node.left;
    }
    // 如果同時(shí)擁有兩個(gè)節(jié)點(diǎn)，就取有子節(jié)點(diǎn)最小值來(lái)替換當(dāng)前被刪除節(jié)點(diǎn)
    const minNode = this._minNode(node.right);
    node.value = minNode.value;
    node.right = this._removeNode(node.right, minNode.value);
    return node;
  }
}

總的來(lái)說(shuō)，通過(guò)這次簡(jiǎn)單的二叉搜索樹(shù)的學(xué)習(xí)，讓我重新認(rèn)識(shí)了遞歸，以前對(duì)于遞歸的理解只是一些簡(jiǎn)單的理論概念，這次深入實(shí)踐讓我對(duì)遞歸的理解又加深了許多。
這讓我想到了數(shù)學(xué)的學(xué)習(xí)，數(shù)學(xué)的理論公式是很容易記住掌握的，如果說(shuō)對(duì)一個(gè)知識(shí)點(diǎn)的掌握滿分是十分，那么直到真正去實(shí)踐它之前，只看公式的掌握只能是2分，因?yàn)楣胶芎?jiǎn)單，就幾句話幾個(gè)原則，但是遇到的問(wèn)題是千變?nèi)f化的，只有真正將理論付諸實(shí)踐，經(jīng)過(guò)各種實(shí)踐的打磨蹂躪，才能真正理解它其中的奧秘。