計(jì)算機(jī)科學(xué)中最常用和討論最多的數(shù)據(jù)結(jié)構(gòu)之一是二叉搜索樹(shù)。這通常是引入的第一個(gè)具有非線性插入算法的數(shù)據(jù)結(jié)構(gòu)。二叉搜索樹(shù)類似于雙鏈表，每個(gè)節(jié)點(diǎn)包含一些數(shù)據(jù)，以及兩個(gè)指向其他節(jié)點(diǎn)的指針；它們?cè)谶@些節(jié)點(diǎn)彼此相關(guān)聯(lián)的方式上有所不同。二叉搜索樹(shù)節(jié)點(diǎn)的指針通常被稱為“左”和“右”，用來(lái)指示與當(dāng)前值相關(guān)的子樹(shù)。這種節(jié)點(diǎn)的簡(jiǎn)單 JavaScript 實(shí)現(xiàn)如下：

10多年的南潯網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。營(yíng)銷型網(wǎng)站的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整南潯建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)從事“南潯網(wǎng)站設(shè)計(jì)”,“南潯網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

var node = {
    value: 125,
    left: null,
    right: null
};

從名稱中可以看出，二叉搜索樹(shù)被組織成分層的樹(shù)狀結(jié)構(gòu)。第一個(gè)項(xiàng)目成為根節(jié)點(diǎn)，每個(gè)附加值作為該根的祖先添加到樹(shù)中。但是，二叉搜索樹(shù)節(jié)點(diǎn)上的值是唯一的，根據(jù)它們包含的值進(jìn)行排序：作為節(jié)點(diǎn)左子樹(shù)的值總是小于節(jié)點(diǎn)的值，右子樹(shù)中的值都是大于節(jié)點(diǎn)的值。通過(guò)這種方式，在二叉搜索樹(shù)中查找值變得非常簡(jiǎn)單，只要你要查找的值小于正在處理的節(jié)點(diǎn)則向左，如果值更大，則向右移動(dòng)。二叉搜索樹(shù)中不能有重復(fù)項(xiàng)，因?yàn)橹貜?fù)會(huì)破壞這種關(guān)系。下圖表示一個(gè)簡(jiǎn)單的二叉搜索樹(shù)。

上圖表示一個(gè)二叉搜索樹(shù)，其根的值為 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。此二叉搜索樹(shù)的深度為 3，表示距離根最遠(yuǎn)的節(jié)點(diǎn)是三個(gè)節(jié)點(diǎn)。

二叉搜索樹(shù)以自然排序的順序結(jié)束，因此可用于快速查找數(shù)據(jù)，因?yàn)槟憧梢粤⒓聪總€(gè)步驟的可能性。通過(guò)限制需要查找的節(jié)點(diǎn)數(shù)量，可以更快地進(jìn)行搜索。假設(shè)你要在上面的樹(shù)中找到值 6。從根開(kāi)始，確定 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)二叉搜索樹(shù)，第一步要先定義基本接口：

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 很有用。

要掌握使用二叉搜索樹(shù)的方法，最好從contains()方法開(kāi)始。contains()方法接受一個(gè)值作為參數(shù)，如果值存在于樹(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ù)的根開(kāi)始。如果沒(méi)有添加數(shù)據(jù)，則可能沒(méi)有根，所以必須要進(jìn)行檢查。遍歷樹(shù)遵循前面討論的簡(jiǎn)單算法：如果要查找的值小于當(dāng)前節(jié)點(diǎn)則向左移動(dòng)，如果值更大則向右移動(dòng)。每次都會(huì)覆蓋current指針，直到找到要找的值（在這種情況下found設(shè)置為true）或者在那個(gè)方向上沒(méi)有更多的節(jié)點(diǎn)了（在這種情況下，值不在樹(shù)上）。

在contains()中使用的方法也可用于在樹(shù)中插入新值。主要區(qū)別在于你要尋找放置新值的位置，而不是在樹(shù)中查找值：

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í)，特殊情況是在沒(méi)有根的情況。在這種情況下，只需將根設(shè)置為新值即可輕松完成工作。對(duì)于其他情況，基本算法與contains()中使用的基本算法完全相同：新值小于當(dāng)前節(jié)點(diǎn)向左，如果值更大則向右。主要區(qū)別在于，當(dāng)你無(wú)法繼續(xù)前進(jìn)時(shí)，這就是新值的位置。所以如果你需要向左移動(dòng)但沒(méi)有左側(cè)節(jié)點(diǎn)，則新值將成為左側(cè)節(jié)點(diǎn)（與右側(cè)節(jié)點(diǎn)相同）。由于不存在重復(fù)項(xiàng)，因此如果找到具有相同值的節(jié)點(diǎn)，則操作將停止。

在繼續(xù)討論size()方法之前，我想深入討論樹(shù)遍歷。為了計(jì)算二叉搜索樹(shù)的大小，必須要訪問(wèn)樹(shù)中的每個(gè)節(jié)點(diǎn)。二叉搜索樹(shù)通常會(huì)有不同類型的遍歷方法，最常用的是有序遍歷。通過(guò)處理左子樹(shù)，然后是節(jié)點(diǎn)本身，然后是右子樹(shù)，在每個(gè)節(jié)點(diǎn)上執(zhí)行有序遍歷。由于二叉搜索樹(shù)以這種方式排序，從左到右，結(jié)果是節(jié)點(diǎn)以正確的排序順序處理。對(duì)于size()方法，節(jié)點(diǎn)遍歷的順序?qū)嶋H上并不重要，但它對(duì)toArray()方法很重要。由于兩種方法都需要執(zhí)行遍歷，我決定添加一個(gè)可以通用的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

};

此方法接受一個(gè)參數(shù)process，這是一個(gè)應(yīng)該在樹(shù)中的每個(gè)節(jié)點(diǎn)上運(yùn)行的函數(shù)。該方法定義了一個(gè)名為inOrder()的輔助函數(shù)用于遞歸遍歷樹(shù)。注意，如果當(dāng)前節(jié)點(diǎn)存在，則遞歸僅左右移動(dòng)（以避免多次處理null）。然后traverse()方法從根節(jié)點(diǎn)開(kāi)始按順序遍歷，process()函數(shù)處理每個(gè)節(jié)點(diǎn)。然后可以使用此方法實(shí)現(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()都調(diào)用traverse()方法并傳入一個(gè)函數(shù)來(lái)在每個(gè)節(jié)點(diǎn)上運(yùn)行。在使用size()的情況下，函數(shù)只是遞增長(zhǎng)度變量，而toArray()使用函數(shù)將節(jié)點(diǎn)的值添加到數(shù)組中。toString()方法在調(diào)用toArray()之前把返回的數(shù)組轉(zhuǎn)換為字符串，并返回 。

刪除節(jié)點(diǎn)時(shí)，你需要確定它是否為根節(jié)點(diǎn)。根節(jié)點(diǎn)的處理方式與其他節(jié)點(diǎn)類似，但明顯的例外是根節(jié)點(diǎn)需要在結(jié)尾處設(shè)置為不同的值。為簡(jiǎn)單起見(jiàn)，這將被視為 JavaScript 代碼中的一個(gè)特例。

刪除節(jié)點(diǎn)的第一步是確定節(jié)點(diǎn)是否存在：

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é)點(diǎn)，如果值小于當(dāng)前節(jié)點(diǎn)的話則向左移動(dòng)，如果值大于當(dāng)前節(jié)點(diǎn)則向右移動(dòng)。當(dāng)遍歷時(shí)還會(huì)跟蹤parent節(jié)點(diǎn)，因?yàn)槟阕罱K需要從其父節(jié)點(diǎn)中刪除該節(jié)點(diǎn)。當(dāng)found等于true時(shí)，current的值是要?jiǎng)h除的節(jié)點(diǎn)。

刪除節(jié)點(diǎn)時(shí)需要注意三個(gè)條件：

1、葉子節(jié)點(diǎn)

2、只有一個(gè)孩子的節(jié)點(diǎn)

3、有兩個(gè)孩子的節(jié)點(diǎn)

從二叉搜索樹(shù)中刪除除了葉節(jié)點(diǎn)之外的內(nèi)容意味著必須移動(dòng)值來(lái)對(duì)樹(shù)正確的排序。前兩個(gè)實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，只刪除了一個(gè)葉子節(jié)點(diǎn)，刪除了一個(gè)帶有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)并用其子節(jié)點(diǎn)替換。最后一種情況有點(diǎn)復(fù)雜，以便稍后訪問(wèn)。

在了解如何刪除節(jié)點(diǎn)之前，你需要知道節(jié)點(diǎn)上究竟存在多少個(gè)子節(jié)點(diǎn)。一旦知道了，你必須確定節(jié)點(diǎn)是否為根節(jié)點(diǎn)，留下一個(gè)相當(dāng)簡(jiǎn)單的決策樹(shù)：

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é)點(diǎn)時(shí)，這是一個(gè)覆蓋它的簡(jiǎn)單過(guò)程。對(duì)于非根節(jié)點(diǎn)，必須根據(jù)要?jiǎng)h除的節(jié)點(diǎn)的值設(shè)置parent上的相應(yīng)指針：如果刪除的值小于父節(jié)點(diǎn)，則left指針必須重置為null（對(duì)于沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)）或刪除節(jié)點(diǎn)的left指針；如果刪除的值大于父級(jí)，則必須將right指針重置為null或刪除的節(jié)點(diǎn)的right指針。

如前所述，刪除具有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)是最復(fù)雜的操作。考慮二元搜索樹(shù)的以下表示。

根為 8，左子為 3，如果 3 被刪除會(huì)發(fā)生什么？有兩種可能性：1（3 左邊的孩子，稱為有序前身）或4（右子樹(shù)的最左邊的孩子，稱為有序繼承者）都可以取代 3。

這兩個(gè)選項(xiàng)中的任何一個(gè)都是合適的。要查找有序前驅(qū)，即刪除值之前的值，請(qǐng)檢查要?jiǎng)h除的節(jié)點(diǎn)的左子樹(shù)，并選擇最右側(cè)的子節(jié)點(diǎn)；找到有序后繼，在刪除值后立即出現(xiàn)的值，反轉(zhuǎn)進(jìn)程并檢查最左側(cè)的右子樹(shù)。其中每個(gè)都需要另一次遍歷樹(shù)來(lái)完成操作：

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

};

具有兩個(gè)子節(jié)點(diǎn)的根節(jié)點(diǎn)和非根節(jié)點(diǎn)的代碼幾乎相同。此實(shí)現(xiàn)始終通過(guò)查看左子樹(shù)并查找最右側(cè)子節(jié)點(diǎn)來(lái)查找有序前驅(qū)。遍歷是使用while循環(huán)中的replacement和replacementParent變量完成的。

replacement中的節(jié)點(diǎn)最終成為替換current的節(jié)點(diǎn)，因此通過(guò)將其父級(jí)的right指針設(shè)置為替換的left指針，將其從當(dāng)前位置移除。

對(duì)于根節(jié)點(diǎn)，當(dāng)replacement是根節(jié)點(diǎn)的直接子節(jié)點(diǎn)時(shí)，replacementParent將為null，因此replacement的right指針只是設(shè)置為 root 的right指針。

最后一步是將替換節(jié)點(diǎn)分配到正確的位置。對(duì)于根節(jié)點(diǎn)，替換設(shè)置為新根；對(duì)于非根節(jié)點(diǎn)，替換被分配到原始parent上的適當(dāng)位置。

關(guān)于此實(shí)現(xiàn)的說(shuō)明：始終用有序前驅(qū)替換節(jié)點(diǎn)可能導(dǎo)致不平衡樹(shù)，其中大多數(shù)值會(huì)位于樹(shù)的一側(cè)。不平衡樹(shù)意味著搜索效率較低，因此在實(shí)際場(chǎng)景中應(yīng)該引起關(guān)注。在二叉搜索樹(shù)實(shí)現(xiàn)中，要確定是用有序前驅(qū)還是有序后繼以使樹(shù)保持適當(dāng)平衡（通常稱為自平衡二叉搜索樹(shù)）。

這個(gè)二叉搜索樹(shù)實(shí)現(xiàn)的完整源代碼可以在我的GitHub 中找到。對(duì)于替代實(shí)現(xiàn)，你還可以查看 Isaac Schlueter 的 GitHub fork。

本文轉(zhuǎn)載自：https://segmentfault.com/a/1190000020044659

英文原文地址：https://humanwhocodes.com/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/

作者：Nicholas C. Zakas

推薦教程：《JavaScript視頻教程》

分享名稱：一文了解JS實(shí)現(xiàn)二叉搜索樹(shù)的方法
文章位置：http://www.rwnh.cn/article12/cpijdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、虛擬主機(jī)、網(wǎng)站內(nèi)鏈、用戶體驗(yàn)、網(wǎng)頁(yè)設(shè)計(jì)公司、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)