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

二進(jìn)制搜索樹(shù)在二進(jìn)制樹(shù)的基礎(chǔ)上還有一個(gè)附加條件，即，當(dāng)二進(jìn)制樹(shù)插入一個(gè)值時(shí)，如果插入的值小于當(dāng)前節(jié)點(diǎn)，則將其插入左節(jié)點(diǎn)，否則它被插入右節(jié)點(diǎn)；如果插入過(guò)程中，如果已經(jīng)存在左節(jié)點(diǎn)或右節(jié)點(diǎn)，則繼續(xù)根據(jù)上述規(guī)則進(jìn)行比較，直到遇到新節(jié)點(diǎn)為止.

由于其唯一的數(shù)據(jù)結(jié)構(gòu)，因此二叉搜索樹(shù)的時(shí)間復(fù)雜度為O（h），無(wú)論是添加，刪除還是搜索，其中h是二叉樹(shù)的高度. 因此，二叉樹(shù)應(yīng)盡可能短，也就是說(shuō)，左右節(jié)點(diǎn)應(yīng)盡可能地平衡.

要構(gòu)建二叉搜索樹(shù)，請(qǐng)首先構(gòu)建二叉樹(shù)的節(jié)點(diǎn)類. 根據(jù)二叉樹(shù)的特性，每個(gè)節(jié)點(diǎn)類都有一個(gè)左節(jié)點(diǎn)，一個(gè)右節(jié)點(diǎn)和值本身，因此該節(jié)點(diǎn)類如下:

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

接下來(lái)，構(gòu)建一個(gè)二叉搜索樹(shù)

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

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

由于二分搜索樹(shù)的左側(cè)子樹(shù)小于節(jié)點(diǎn)，而右子樹(shù)具有更大的節(jié)點(diǎn)，因此可以輕松地為二分搜索樹(shù)編寫(xiě)新算法，如下所示:

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

上面的代碼首先確定新添加的密鑰和當(dāng)前節(jié)點(diǎn)的密鑰的大小. 如果它很小，它將遞歸遍歷左子節(jié)點(diǎn)，直到找到一個(gè)空的左子節(jié)點(diǎn)為止；否則，它將遍歷左子節(jié)點(diǎn). 如果它大于當(dāng)前節(jié)點(diǎn)，則相同. 上面的代碼{1} {2} {3} {4}可以更改this.root的值的原因是因?yàn)镴avaScript函數(shù)是按值傳遞的，并且參數(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);
  }
}

如上所述，它是中間順序遍歷.

這里要了解的一件事是遞歸. 請(qǐng)注意，函數(shù)的執(zhí)行可以抽象為數(shù)據(jù)結(jié)構(gòu)-堆棧. 為了執(zhí)行功能，維護(hù)堆棧以存儲(chǔ)功能的執(zhí)行. 每次函數(shù)遞歸時(shí)，它將當(dāng)前執(zhí)行環(huán)境放在堆棧上并記錄執(zhí)行位置. 以上面的代碼為例，有以下數(shù)據(jù)

它將從11開(kāi)始，對(duì)堆棧執(zhí)行{1}，然后轉(zhuǎn)到7，然后對(duì)堆棧執(zhí)行{1}，然后到5，對(duì)堆棧執(zhí)行{1}，然后到3，執(zhí)行{1 }到堆棧上，此時(shí)，發(fā)現(xiàn)節(jié)點(diǎn)3的左子節(jié)點(diǎn)為空，因此堆棧開(kāi)始彈出. 這時(shí)，彈出節(jié)點(diǎn)3的執(zhí)行環(huán)境，執(zhí)行{2}，{3}，還發(fā)現(xiàn)3的右子節(jié)點(diǎn)為空，{3}遞歸執(zhí)行完成后，彈出向上執(zhí)行節(jié)點(diǎn)5，執(zhí)行{2} {3}，然后彈出7，執(zhí)行{2} {3}到堆棧上，當(dāng)執(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)，執(zhí)行{1}二叉排序樹(shù)算法，執(zhí)行{2} {3}，依此類推.

預(yù)定順序和中間順序之間的區(qū)別在于，它首先訪問(wèn)節(jié)點(diǎn)本身，即代碼執(zhí)行的順序?yàn)? 1 3.

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

不難發(fā)現(xiàn)，無(wú)論中間順序如何，左節(jié)點(diǎn)始終都是遞歸的. 遍歷左側(cè)節(jié)點(diǎn)時(shí)，將再次彈出堆棧，遍歷這些節(jié)點(diǎn). 它們和訪問(wèn)節(jié)點(diǎn)本身的時(shí)間之間的唯一區(qū)別.

搜索非常簡(jiǎn)單. 您可以基于左子節(jié)點(diǎn)小于該節(jié)點(diǎn)，右子節(jié)點(diǎn)大于該節(jié)點(diǎ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ù)不同情況進(jìn)行判斷

首先確定節(jié)點(diǎn)是否具有左子樹(shù). 如果沒(méi)有左子樹(shù)，則直接用刪除的節(jié)點(diǎn)替換右子樹(shù)的根節(jié)點(diǎn)；

如果有，請(qǐng)用刪除的節(jié)點(diǎn)替換右子樹(shù)的最小節(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;
  }
}

通常，通過(guò)研究這個(gè)簡(jiǎn)單的二進(jìn)制搜索樹(shù)，我重新認(rèn)識(shí)了遞歸. 以前對(duì)遞歸的理解只是一些簡(jiǎn)單的理論概念. 這種深入的實(shí)踐使我再次了解了遞歸. 加深了很多.

這使我想起了數(shù)學(xué)的研究. 數(shù)學(xué)的理論公式易于記憶和掌握. 如果知識(shí)點(diǎn)的掌握程度很高二叉排序樹(shù)算法，那么在您實(shí)際練習(xí)它之前，請(qǐng)先看看公式的掌握程度. 可以是2分，因?yàn)楣�式非常�?jiǎn)單，只需幾句話和幾條原則，但是遇到的問(wèn)題是千變?nèi)f化的. 只有在將理論付諸實(shí)踐后，經(jīng)過(guò)各種實(shí)踐的磨合和破壞，它才能真正理解其奧秘.

本文來(lái)自本站，轉(zhuǎn)載請(qǐng)注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-248651-1.html