JavaScript算法之二叉搜索樹

khlbat 發(fā)布于2019-08-21 16:26 / 1128人閱讀

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

什么是二叉樹

二叉樹就是樹的每個節(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) {
  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;
  }
}

二叉搜索樹的刪除

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

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

總結

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

云服務器 GPU云服務器二叉樹算法最優(yōu)二叉樹算法圖二叉樹排序樹規(guī)則二叉查找樹

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

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/88548.html

學習數(shù)據(jù)結構與算法之二叉搜索樹

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

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

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

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

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

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

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

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

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

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