這次帶給大家JS二元搜尋樹使用詳解，JS二元搜尋樹使用的注意事項有哪些，下面就是實戰案例，一起來看一下。
什麼是二元樹
#
二元樹就是樹的每個節點最多只能有兩個子節點
什麼是二元搜尋樹
二元搜尋樹在二元樹的基礎上，多了一個條件，就是二叉樹在插入值時，若插入值比當前節點小，就插入到左節點，否則插入到右節點；若插入過程中，左節點或右節點已經存在，那麼繼續如上規則比較，直到遇到新的節點。
二元搜尋樹的特性
二元搜尋樹由於其獨特的資料結構，使得其無論在增刪，還是查找，時間複雜度都是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) {
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);
}
}登入後複製
二元搜尋樹的刪除
#
刪除較為複雜，需根據不同情況判斷
#
首先判斷該節點是否有左子樹，如果沒有左子節樹，則直接將右子樹的根節點替換被刪除節點；
如果有，則將右子樹的最小節點替換被刪除節點；
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 {
// 如果没有左子树，那么将右子树根节点作为替换节点
if (!node.left) {
return node.right;
// 如果存在左子树，那么取右子树最小节点作为替换节点
} else if (node.left) {
return this._minNode(node.right);
}
}
}登入後複製
总结
总的来说，通过这次简单的二叉搜索树的学习，让我重新认识了递归，以前对于递归的理解只是一些简单的理论概念，这次深入实践让我对递归的理解又加深了许多。
这让我想到了数学的学习，数学的理论公式是很容易记住掌握的，如果说对一个知识点的掌握满分是十分，那么直到真正去实践它之前，只看公式的掌握只能是2分，因为公式很简单，就几句话几个原则，但是遇到的问题是千变万化的，只有真正将理论付诸实践，经过各种实践的打磨蹂躏，才能真正理解它其中的奥秘。
相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！
推荐阅读：
react-native-fs插件使用案列详解
js实现字符限制中文汉字=两个字符
优化页面加载速度插件InstantClick
以上是JS二元搜尋樹使用詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！
