計(jì)算機(jī)科學(xué)中最常用和討論最多的數(shù)據(jù)結(jié)構(gòu)之一是二叉搜索樹。這通常是引入的第一個(gè)具有非線性插入算法的數(shù)據(jù)結(jié)構(gòu)。二叉搜索樹類似于雙鏈表，每個(gè)節(jié)點(diǎn)包含一些數(shù)據(jù)，以及兩個(gè)指向其他節(jié)點(diǎn)的指針；它們?cè)谶@些節(jié)點(diǎn)彼此相關(guān)聯(lián)的方式上有所不同。二叉搜索樹節(jié)點(diǎn)的指針通常被稱為“左”和“右”，用來(lái)指示與當(dāng)前值相關(guān)的子樹。這種節(jié)點(diǎn)的簡(jiǎn)單 javascript 實(shí)現(xiàn)如下：
var node = { value: 125, left: null, right: null};從名稱中可以看出，二叉搜索樹被組織成分層的樹狀結(jié)構(gòu)。第一個(gè)項(xiàng)目成為根節(jié)點(diǎn)，每個(gè)附加值作為該根的祖先添加到樹中。但是，二叉搜索樹節(jié)點(diǎn)上的值是唯一的，根據(jù)它們包含的值進(jìn)行排序：作為節(jié)點(diǎn)左子樹的值總是小于節(jié)點(diǎn)的值，右子樹中的值都是大于節(jié)點(diǎn)的值。通過(guò)這種方式，在二叉搜索樹中查找值變得非常簡(jiǎn)單，只要你要查找的值小于正在處理的節(jié)點(diǎn)則向左，如果值更大，則向右移動(dòng)。二叉搜索樹中不能有重復(fù)項(xiàng)，因?yàn)橹貜?fù)會(huì)破壞這種關(guān)系。下圖表示一個(gè)簡(jiǎn)單的二叉搜索樹。
上圖表示一個(gè)二叉搜索樹，其根的值為 8。當(dāng)添加值 3 時(shí)，它成為根的左子節(jié)點(diǎn)，因?yàn)?3 小于 8。當(dāng)添加值 1 時(shí)，它成為 3 的左子節(jié)點(diǎn)，因?yàn)?1 小于 8（所以向左）然后 1 小于3（再向左）。當(dāng)添加值 10 時(shí)，它成為跟的右子節(jié)點(diǎn)，因?yàn)?10 大于 8。不斷用此過(guò)程繼續(xù)處理值 6，4，7，14 和 13。此二叉搜索樹的深度為 3，表示距離根最遠(yuǎn)的節(jié)點(diǎn)是三個(gè)節(jié)點(diǎn)。
二叉搜索樹以自然排序的順序結(jié)束，因此可用于快速查找數(shù)據(jù)，因?yàn)槟憧梢粤⒓聪總€(gè)步驟的可能性。通過(guò)限制需要查找的節(jié)點(diǎn)數(shù)量，可以更快地進(jìn)行搜索。假設(shè)你要在上面的樹中找到值 6。從根開始，確定 6 小于 8，因此前往根的左子節(jié)點(diǎn)。由于 6 大于 3，因此你將前往右側(cè)節(jié)點(diǎn)。你就能找到正確的值。所以你只需訪問(wèn)三個(gè)而不是九個(gè)節(jié)點(diǎn)來(lái)查找這個(gè)值。
要在 javascript 中實(shí)現(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ù)結(jié)構(gòu)類似，有添加和刪除值的方法。我還添加了一些方便的方法，size()，toarray()和tostring()，它們對(duì) javascript 很有用。
要掌握使用二叉搜索樹的方法，最好從 contains() 方法開始。 contains() 方法接受一個(gè)值作為參數(shù)，如果值存在于樹中則返回 true，否則返回 false。此方法遵循基本的二叉搜索算法來(lái)確定該值是否存在：
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ù)，則可能沒有根，所以必須要進(jìn)行檢查。遍歷樹遵循前面討論的簡(jiǎn)單算法：如果要查找的值小于當(dāng)前節(jié)點(diǎn)則向左移動(dòng)，如果值更大則向右移動(dòng)。每次都會(huì)覆蓋 current 指針，直到找到要找的值（在這種情況下 found 設(shè)置為 true）或者在那個(gè)方向上沒有更多的節(jié)點(diǎn)了（在這種情況下，值不在樹上）。
在 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};在二叉搜索樹中添加值時(shí)，特殊情況是在沒有根的情況。在這種情況下，只需將根設(shè)置為新值即可輕松完成工作。對(duì)于其他情況，基本算法與 contains() 中使用的基本算法完全相同：新值小于當(dāng)前節(jié)點(diǎn)向左，如果值更