JavaScript算法之二叉搜索樹

khlbat 發布于2019-08-21 16:26 / 1075人閱讀

摘要：二叉搜索樹的特性二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是，為二叉樹的高度。二叉搜索樹的查找查找很簡單，根據左子節點比該節點小，右子節點比該節點大的原則進行循環判斷即可。

什么是二叉樹

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

什么是二叉搜索樹

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

二叉搜索樹的特性

二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是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) {
  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;
  }
}

二叉搜索樹的刪除

刪除較為復雜，需要根據不同情況判斷
首先判斷該節點是否有左子樹，如果沒有左子節樹，則直接將右子樹的根節點替換被刪除節點；
如果有，則將右子樹的最小節點替換被刪除節點；

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 {
    // 如果左右子節點都沒有
    if (!node.left && !node.right) {
      return null;
    }
    // 如果只有一個子節點
    if (node.left === null) {
      return node.right;
    }
    if (node.right === null) {
      return node.left;
    }
    // 如果同時擁有兩個節點，就取有子節點最小值來替換當前被刪除節點
    const minNode = this._minNode(node.right);
    node.value = minNode.value;
    node.right = this._removeNode(node.right, minNode.value);
    return node;
  }
}

總結

總的來說，通過這次簡單的二叉搜索樹的學習，讓我重新認識了遞歸，以前對于遞歸的理解只是一些簡單的理論概念，這次深入實踐讓我對遞歸的理解又加深了許多。
這讓我想到了數學的學習，數學的理論公式是很容易記住掌握的，如果說對一個知識點的掌握滿分是十分，那么直到真正去實踐它之前，只看公式的掌握只能是2分，因為公式很簡單，就幾句話幾個原則，但是遇到的問題是千變萬化的，只有真正將理論付諸實踐，經過各種實踐的打磨蹂躪，才能真正理解它其中的奧秘。

云服務器 GPU云服務器二叉樹算法最優二叉樹算法圖二叉樹排序樹規則二叉查找樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/88548.html

學習數據結構與算法之二叉搜索樹

摘要：二叉搜索樹是二叉樹的一種，其特征是左側子節點存儲比父節點小的值，右側子節點存儲比父節點大或等于父節點的值。實現和這個兩個方法其實挺簡單的，最小的節點就在二叉搜索樹的最左反之，最大的就在最右。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構...

denson 2019-08-21 11:54 評論0 收藏0
PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。操作給定的二叉樹，將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。最后下面的兩道題目分別運用了二叉樹先序中序遍歷算法。開篇以下內容可能偏應試但很好理解，所以大家一定要堅持看下去，因為我們變強的過程注定孤獨的，堅持下來就會看到明天的太陽。回顧 showImg(https://user-...

li21 2019-07-01 10:26 評論0 收藏0
算法基礎之二叉樹

摘要：本文主要包括樹相關的算法，二叉樹結點基本結構如下本文還會繼續更新。判斷是否平衡二叉樹判斷是否對稱二叉樹判斷是否完全二叉樹判斷是否滿二叉樹堆操作默認大根堆獲取堆大小查看堆頂元素添加一個元素打印堆取出對頂元素本文主要包括樹相關的算法，二叉樹結點基本結構如下 function TreeNode(x) { this.val = x; this.left = null; this....

趙連江 2019-08-23 11:52 評論0 收藏0
Java TreeMap 源碼解析

摘要：源碼剖析由于紅黑樹的操作我這里不說了，所以這里基本上也就沒什么源碼可以講了，因為這里面重要的算法都是，這里的是指，他們是算法導論的作者，也就是說里面算法都是參照算法導論的偽代碼。因為紅黑樹是平衡的二叉搜索樹，所以其包含操作的時間復雜度都為。本文章首發于個人博客，鑒于sf博客樣式具有賞心悅目的美感，遂發表于此，供大家學習、批評。本文還在不斷更新中，最新版可移至個人博客。? 繼上篇文章...

rubyshen 2019-08-14 12:28 評論0 收藏0
利用PHP實現常用的數據結構之二叉樹（小白系列文章五）

摘要：回來更新一波，最近刷劍指，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識，發現也用不上，我想說的是，讀一本書體現不了這本書回來更新一波，最近刷《劍指offer》，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...

developerworks 2019-06-27 16:27 評論0 收藏0