如何利用JavaScript實現(xiàn)二叉搜索樹
計算機科學中最常用和討論最多的數(shù)據(jù)結構之一是二叉搜索樹。這通常是引入的第一個具有非線性插入算法的數(shù)據(jù)結構。二叉搜索樹類似于雙鏈表，每個節(jié)點包含一些數(shù)據(jù)，以及兩個指向其他節(jié)點的指針；它們在這些節(jié)點彼此相關聯(lián)的方式上有所不同。二叉搜索樹節(jié)點的指針通常被稱為“左”和“右”，用來指示與當前值相關的子樹。這種節(jié)點的簡單 JavaScript 實現(xiàn)如下：
var node = {
value: 125,
left: null,
right: null
};
從名稱中可以看出，二叉搜索樹被組織成分層的樹狀結構。第一個項目成為根節(jié)點，每個附加值作為該根的祖先添加到樹中。但是，二叉搜索樹節(jié)點上的值是唯一的，根據(jù)它們包含的值進行排序：作為節(jié)點左子樹的值總是小于節(jié)點的值，右子樹中的值都是大于節(jié)點的值。通過這種方式，在二叉搜索樹中查找值變得非常簡單，只要你要查找的值小于正在處理的節(jié)點則向左，如果值更大，則向右移動。二叉搜索樹中不能有重復項，因為重復會破壞這種關系。下圖表示一個簡單的二叉搜索樹。
上圖表示一個二叉搜索樹，其根的值為 8。當添加值 3 時，它成為根的左子節(jié)點，因為 3 小于 8。當添加值 1 時，它成為 3 的左子節(jié)點，因為 1 小于 8（所以向左）然后 1 小于3（再向左）。當添加值 10 時，它成為跟的右子節(jié)點，因為 10 大于 8。不斷用此過程繼續(xù)處理值 6，4，7，14 和 13。此二叉搜索樹的深度為 3，表示距離根最遠的節(jié)點是三個節(jié)點。
二叉搜索樹以自然排序的順序結束，因此可用于快速查找數(shù)據(jù)，因為你可以立即消除每個步驟的可能性。通過限制需要查找的節(jié)點數(shù)量，可以更快地進行搜索。假設你要在上面的樹中找到值 6。從根開始，確定 6 小于 8，因此前往根的左子節(jié)點。由于 6 大于 3，因此你將前往右側節(jié)點。你就能找到正確的值。所以你只需訪問三個而不是九個節(jié)點來查找這個值。
要在 JavaScript 中實現(xiàn)二叉搜索樹，第一步要先定義基本接口：
function BinarySearchTree() {
this._root = null;
}
BinarySearchTree.prototype = {
//restore constructor
constructor: BinarySearchTree,
add: function (value){
},
contains: function(value){
},
remove: function(value){
},
size: function(){
},
toArray: function(){
},
toString: function(){
}
};
基本接與其他數(shù)據(jù)結構類似，有添加和刪除值的方法。我還添加了一些方便的方法，size()，toArray()和toString()，它們對 JavaScript 很有用。
要掌握使用二叉搜索樹的方法，最好從 contains() 方法開始。contains() 方法接受一個值作為參數(shù)，如果值存在于樹中則返回 true，否則返回 false。此方法遵循基本的二叉搜索算法來確定該值是否存在：
BinarySearchTree.prototype = {
//more code
contains: function(value){
var found = false,
current = this._root
//make sure there's a node to search
while(!found && current){
//if the value is less than the current node's, go left
if (value < current.value){
current = current.left;
//if the value is greater than the current node's, go right
} else if (value > current.value){
current = current.right;
//values are equal, found it!
} else {
found = true;
}
}
//only proceed if the node was found
return found;
},
//more code
};
搜索從樹的根開始。如果沒有添加數(shù)據(jù)，則可能沒有根，所以必須要進行檢查。遍歷樹遵循前面討論的簡單算法：如果要查找的值小于當前節(jié)點則向左移動，如果值更大則向右移動。每次都會覆蓋 current 指針，直到找到要找的值（在這種情況下 found 設置為 true）或者在那個方向上沒有更多的節(jié)點了（在這種情況下，值不在樹上）。
在 contains() 中使用的方法也可用于在樹中插入新值。主要區(qū)別在于你要尋找放置新值的位置，而不是在樹中查找值：
BinarySearchTree.prototype = {
//more code
add: function(value){
//create a new item object, place data in
var node = {
value: value,
left: null,
right: null
},
//used to traverse the structure
current;
//special case: no items in the tree yet
if (this._root === null){
this._root = node;
} else {
current = this._root;
while(true){
//if the new value is less than this node's value, go left
if (value < current.value){
//if there's no left, then the new node belongs there
if (current.left === null){
current.left = node;
break;
} else {
current = current.left;
}
//if the new value is greater than this node's value, go right
} else if (value > current.value){
//if there's no right, then the new node belongs there
if (current.right === null){
current.right = node;
break;
} else {
current = current.right;
}
//if the new value is equal to the current one, just ignore
} else {
break;
}
}
}
},
//more code
};
在二叉搜索樹中添加值時，特殊情況是在沒有根的情況。在這種情況下，只需將根設置為新值即可輕松完成工作。對于其他情況，基本算法與 contains() 中使用的基本算法完全相同：新值小于當前節(jié)點向左，如果值更大則向右。主要區(qū)別在于，當你無法繼續(xù)前進時，這就是新值的位置。所以如果你需要向左移動但沒有左側節(jié)點，則新值將成為左側節(jié)點（與右側節(jié)點相同）。由于不存在重復項，因此如果找到具有相同值的節(jié)點，則操作將停止。
在繼續(xù)討論 size() 方法之前，我想深入討論樹遍歷。為了計算二叉搜索樹的大小，必須要訪問樹中的每個節(jié)點。二叉搜索樹通常會有不同類型的遍歷方法，最常用的是有序遍歷。通過處理左子樹，然后是節(jié)點本身，然后是右子樹，在每個節(jié)點上執(zhí)行有序遍歷。由于二叉搜索樹以這種方式排序，從左到右，結果是節(jié)點以正確的排序順序處理。對于 size() 方法，節(jié)點遍歷的順序實際上并不重要，但它對 toArray() 方法很重要。由于兩種方法都需要執(zhí)行遍歷，我決定添加一個可以通用的 traverse() 方法：
BinarySearchTree.prototype = {
//more code
traverse: function(process){
//helper function
function inOrder(node){
if (node){
//traverse the left subtree
if (node.left !== null){
inOrder(node.left);
}
//call the process method on this node
process.call(this, node);
//traverse the right subtree
if (node.right !== null){
inOrder(node.right);
}
}
}
//start with the root
inOrder(this._root);
},
//more code
};
此方法接受一個參數(shù) process，這是一個應該在樹中的每個節(jié)點上運行的函數(shù)。該方法定義了一個名為 inOrder() 的輔助函數(shù)用于遞歸遍歷樹。注意，如果當前節(jié)點存在，則遞歸僅左右移動（以避免多次處理 null ）。然后 traverse() 方法從根節(jié)點開始按順序遍歷，process() 函數(shù)處理每個節(jié)點。然后可以使用此方法實現(xiàn)size()、toArray()、toString()：
BinarySearchTree.prototype = {
//more code
size: function(){
var length = 0;
this.traverse(function(node){
length++;
});
return length;
},
toArray: function(){
var result = [];
this.traverse(function(node){
result.push(node.value);
});
return result;
},
toString: function(){
return this.toArray().toString();
},
//more code
};
size() 和 toArray() 都調用 traverse() 方法并傳入一個函數(shù)來在每個節(jié)點上運行。在使用 size()的情況下，函數(shù)只是遞增長度變量，而 toArray() 使用函數(shù)將節(jié)點的值添加到數(shù)組中。toString()方法在調用 toArray() 之前把返回的數(shù)組轉換為字符串，并返回 。
刪除節(jié)點時，你需要確定它是否為根節(jié)點。根節(jié)點的處理方式與其他節(jié)點類似，但明顯的例外是根節(jié)點需要在結尾處設置為不同的值。為簡單起見，這將被視為 JavaScript 代碼中的一個特例。
刪除節(jié)點的第一步是確定節(jié)點是否存在：
BinarySearchTree.prototype = {
//more code here
remove: function(value){
var found = false,
parent = null,
current = this._root,
childCount,
replacement,
replacementParent;
//make sure there's a node to search
while(!found && current){
//if the value is less than the current node's, go left
if (value < current.value){
parent = current;
current = current.left;
//if the value is greater than the current node's, go right
} else if (value > current.value){
parent = current;
current = current.right;
//values are equal, found it!
} else {
found = true;
}
}
//only proceed if the node was found
if (found){
//continue
}
},
//more code here
};
remove()方法的第一部分是用二叉搜索定位要被刪除的節(jié)點，如果值小于當前節(jié)點的話則向左移動，如果值大于當前節(jié)點則向右移動。當遍歷時還會跟蹤 parent 節(jié)點，因為你最終需要從其父節(jié)點中刪除該節(jié)點。當 found 等于 true 時，current 的值是要刪除的節(jié)點。
刪除節(jié)點時需要注意三個條件：
- 葉子節(jié)點
- 只有一個孩子的節(jié)點
- 有兩個孩子的節(jié)點
從二叉搜索樹中刪除除了葉節(jié)點之外的內容意味著必須移動值來對樹正確的排序。前兩個實現(xiàn)起來相對簡單，只刪除了一個葉子節(jié)點，刪除了一個帶有一個子節(jié)點的節(jié)點并用其子節(jié)點替換。最后一種情況有點復雜，以便稍后訪問。
在了解如何刪除節(jié)點之前，你需要知道節(jié)點上究竟存在多少個子節(jié)點。一旦知道了，你必須確定節(jié)點是否為根節(jié)點，留下一個相當簡單的決策樹：
BinarySearchTree.prototype = {
//more code here
remove: function(value){
var found = false,
parent = null,
current = this._root,
childCount,
replacement,
replacementParent;
//find the node (removed for space)
//only proceed if the node was found
if (found){
//figure out how many children
childCount = (current.left !== null ? 1 : 0) +
(current.right !== null ? 1 : 0);
//special case: the value is at the root
if (current === this._root){
switch(childCount){
//no children, just erase the root
case 0:
this._root = null;
break;
//one child, use one as the root
case 1:
this._root = (current.right === null ?
current.left : current.right);
break;
//two children, little work to do
case 2:
//TODO
//no default
}
//non-root values
} else {
switch (childCount){
//no children, just remove it from the parent
case 0:
//if the current value is less than its
//parent's, null out the left pointer
if (current.value < parent.value){
parent.left = null;
//if the current value is greater than its
//parent's, null out the right pointer
} else {
parent.right = null;
}
break;
//one child, just reassign to parent
case 1:
//if the current value is less than its
//parent's, reset the left pointer
if (current.value < parent.value){
parent.left = (current.left === null ?
current.right : current.left);
//if the current value is greater than its
//parent's, reset the right pointer
} else {
parent.right = (current.left === null ?
current.right : current.left);
}
break;
//two children, a bit more complicated
case 2:
//TODO
//no default
}
}
}
},
//more code here
};
處理根節(jié)點時，這是一個覆蓋它的簡單過程。對于非根節(jié)點，必須根據(jù)要刪除的節(jié)點的值設置 parent 上的相應指針：如果刪除的值小于父節(jié)點，則 left 指針必須重置為 null（對于沒有子節(jié)點的節(jié)點）或刪除節(jié)點的 left 指針；如果刪除的值大于父級，則必須將 right 指針重置為 null 或刪除的節(jié)點的 right指針。
如前所述，刪除具有兩個子節(jié)點的節(jié)點是最復雜的操作。下圖是兒茶搜索樹的一種表示。
根為 8，左子為 3，如果 3 被刪除會發(fā)生什么？有兩種可能性：1（3 左邊的孩子，稱為有序前身）或4（右子樹的最左邊的孩子，稱為有序繼承者）都可以取代 3。
這兩個選項中的任何一個都是合適的。要查找有序前驅，即刪除值之前的值，請檢查要刪除的節(jié)點的左子樹，并選擇最右側的子節(jié)點；找到有序后繼，在刪除值后立即出現(xiàn)的值，反轉進程并檢查最左側的右子樹。其中每個都需要另一次遍歷樹來完成操作：
BinarySearchTree.prototype = {
//more code here
remove: function(value){
var found = false,
parent = null,
current = this._root,
childCount,
replacement,
replacementParent;
//find the node (removed for space)
//only proceed if the node was found
if (found){
//figure out how many children
childCount = (current.left !== null ? 1 : 0) +
(current.right !== null ? 1 : 0);
//special case: the value is at the root
if (current === this._root){
switch(childCount){
//other cases removed to save space
//two children, little work to do
case 2:
//new root will be the old root's left child
//...maybe
replacement = this._root.left;
//find the right-most leaf node to be
//the real new root
while (replacement.right !== null){
replacementParent = replacement;
replacement = replacement.right;
}
//it's not the first node on the left
if (replacementParent !== null){
//remove the new root from it's
//previous position
replacementParent.right = replacement.left;
//give the new root all of the old
//root's children
replacement.right = this._root.right;
replacement.left = this._root.left;
} else {
//just assign the children
replacement.right = this._root.right;
}
//officially assign new root
this._root = replacement;
//no default
}
//non-root values
} else {
switch (childCount){
//other cases removed to save space
//two children, a bit more complicated
case 2:
//reset pointers for new traversal
replacement = current.left;
replacementParent = current;
//find the right-most node
while(replacement.right !== null){
replacementParent = replacement;
replacement = replacement.right;
}
replacementParent.right = replacement.left;
//assign children to the replacement
replacement.right = current.right;
replacement.left = current.left;
//place the replacement in the right spot
if (current.value < parent.value){
parent.left = replacement;
} else {
parent.right = replacement;
}
//no default
}
}
}
},
//more code here
};
具有兩個子節(jié)點的根節(jié)點和非根節(jié)點的代碼幾乎相同。此實現(xiàn)始終通過查看左子樹并查找最右側子節(jié)點來查找有序前驅。遍歷是使用 while 循環(huán)中的 replacement 和 replacementParent 變量完成的。replacement中的節(jié)點最終成為替換 current 的節(jié)點，因此通過將其父級的 right 指針設置為替換的 left 指針，將其從當前位置移除。對于根節(jié)點，當 replacement 是根節(jié)點的直接子節(jié)點時，replacementParent 將為 null，因此 replacement 的 right 指針只是設置為 root 的 right 指針。最后一步是將替換節(jié)點分配到正確的位置。對于根節(jié)點，替換設置為新根；對于非根節(jié)點，替換被分配到原始 parent 上的適當位置。
說明：始終用有序前驅替換節(jié)點可能導致不平衡樹，其中大多數(shù)值會位于樹的一側。不平衡樹意味著搜索效率較低，因此在實際場景中應該引起關注。在二叉搜索樹實現(xiàn)中，要確定是用有序前驅還是有序后繼以使樹保持適當平衡（通常稱為自平衡二叉搜索樹）。
總結
到此這篇關于如何利用JavaScript實現(xiàn)二叉搜索樹的文章就介紹到這了,更多相關JavaScript二叉搜索樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了Three.js中實現(xiàn)Bloom效果及完整示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
這篇文章主要介紹了微信小程序列表中item左滑刪除功能，本文分步驟給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2018-11-11
這篇文章主要帶領大家理解JavaScript表單的基礎知識，對javascript表單腳本進行深入學習，感興趣的小伙伴們可以參考一下2016-01-01
在做用戶實名驗證時,常會用到身份證號碼的正則表達式及校驗方案,下面這篇文章主要給大家介紹了關于JS正則表達式及身份證號碼驗證的相關資料,需要的朋友可以參考下2022-07-07
下面小編就為大家?guī)硪黄猨s控制按鈕,防止頻繁點擊響應的實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-02-02
這篇文章主要介紹了Javascript節(jié)點關系,實例分析了javascript操作父子節(jié)點及兄弟節(jié)點的相關技巧,需要的朋友可以參考下2015-05-05
JavaScript實現(xiàn)網(wǎng)頁端播放攝像頭實時畫面
這篇文章主要介紹了如何利用JavaScript實現(xiàn)在網(wǎng)頁端播放局域網(wǎng)（不能上云）或是廣域網(wǎng)的攝像頭的實時畫面，文中的示例代碼講解詳細，需要的可以參考一下2022-02-02
在某些情況下,我們會比TS更清楚一個數(shù)據(jù)的類型,這種時候我們就可以使用斷言來告訴TS相信我,我知道自己在干什么,下面這篇文章主要給大家介紹了關于TypeScript函數(shù)和類型斷言的相關資料,需要的朋友可以參考下2022-06-06
JavaScript中全局變量、函數(shù)內變量以及常量表達式的效率測試
直接用字符串常量要比利用全局變量快，但創(chuàng)建正則表達式就比起用全局變量要慢上很多了。2009-11-11
JS實現(xiàn)屏蔽shift，Ctrl，alt等功能鍵的方法
這篇文章主要介紹了JS實現(xiàn)屏蔽shift，Ctrl，alt等功能鍵的方法,涉及javascript針對鍵盤按鍵的獲取與操作技巧,需要的朋友可以參考下2015-06-06