JavaScript 中的計算機科學：二叉搜索樹，第 1 部分

在計算機科學課程中，最常使用和討論的數據結構之一可能是二叉搜索樹。這通常是引入的第一個具有非線性插入算法的數據結構。二叉搜索樹類似於雙向鍊錶，每個節點都包含一些數據以及指向其他節點的兩個指針。它們在這些節點相互關聯的方式上有所不同。二叉搜索樹節點的指針通常稱為“左”和“右”，以指示與當前值相關的值的子樹。此類節點的簡單 JavaScript 實現如下：

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

從名稱可以看出，二叉搜索樹被組織成層次樹結構。第一項成為根節點，每個附加值都作為該根的祖先添加到樹中。然而，二叉搜索樹的獨特之處在於節點根據它們包含的值進行排序：作為節點左子樹一部分的任何值總是小於節點的值，而右子樹中的任何值總是大於節點的值。這樣，在二叉搜索樹中查找值變得非常簡單，只要您要查找的值小於您正在處理的節點，就向左走，如果該值更大，則向右走。二叉搜索樹中不能有重複項，因為重複項會破壞這種關係。下圖表示一個簡單的二叉搜索樹。

此圖表示一棵二叉搜索樹，其根值為 8。當添加值 3 時，它成為根的左孩子，因為 3 小於 8。當添加值 1 時，它成為 3 的左孩子，因為1 小於 8（所以向左走）然後 1 小於 3（再次向左走）。添加值 10 後，它成為根的右孩子，因為 10 大於 8。這個過程繼續使用值 6、4、7、14 和 13。這個二叉搜索樹的深度為 3，這意味著距離根最遠的值是三個節點。

二叉搜索樹自然會以排序順序結束，因此對於快速查找數據很有用，因為您可以立即消除每一步的可能性。通過限制需要調查的節點數量，可以更快地完成搜索。假設您想在上面的樹中找到值 6。從根開始，您確定 6 小於 8，因此前往根的左孩子。由於 6 大於 3，因此您前往正確的節點。這就是您正在尋找的價值。所以不用訪問九個節點來找到這個值，你只需要訪問三個。

要在 JavaScript 中構建二叉搜索樹實現，第一步是定義基本接口：

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(){
    }

};

基本接口類似於其他數據結構，具有添加和刪除值的方法。我還添加了一些方便的方法，size() , toArray() , 和 toString() ，這對 JavaScript 很有用。

要掌握使用二叉搜索樹，最好的方法是開始使用 contains() . contains() 方法接受一個值作為參數並返回 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

};

搜索從樹的根開始。如果沒有添加數據，則可能沒有根，因此必須對此進行檢查。遍歷樹遵循前面討論的簡單算法：如果要查找的值小於當前節點，則向左，如果值更大，則向右。 current 每次都覆蓋指針，直到找到值（在這種情況下 found 設置為 true ) 或者沒有更多的節點可以在那個方向搜索（在這種情況下，值不在樹中）。

contains()中使用的方法 也可用於向樹中插入新值。主要區別在於您將尋找放置新值的位置，而不是在樹中查找值：

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() 中使用的算法完全相同 :向左是新值小於當前節點，如果值更大則向右。主要區別在於，當您無法再進一步時，那就是新值的位置。因此，如果您需要向左但沒有左節點，則新值將成為左節點（與右節點相同）。由於不能重複，如果找到具有相同值的節點，則操作停止。

在轉到 size() 之前 方法，我想離題討論一下樹的遍歷。為了計算二叉搜索樹的大小，需要訪問樹中的每個節點。二叉搜索樹通常需要執行不同類型的遍歷來檢索信息，最常用的是中序遍歷。通過處理左子樹，然後是節點本身，然後是右子樹，對每個節點執行按順序遍歷。由於二叉搜索樹以這種方式排序，從左到右，結果是以正確的排序順序處理節點。對於 size() 方法，實際上遍歷節點的順序並不重要，但對於 toArray() 確實很重要 方法。由於這兩種方法都需要進行遍歷，所以我決定添加一個 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

};

此方法接受單個參數 process ，這是一個應該在樹中的每個節點上運行的函數。該方法定義了一個名為 inOrder() 的輔助函數 用於遞歸遍歷樹。請注意，如果該節點存在，遞歸只會左右移動（以避免處理 null 多次）。 traverse() 方法然後從根節點和 process() 開始按順序遍歷 函數處理處理每個節點。然後可以使用此方法來實現 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() 方法並傳入一個函數以在每個節點上運行。 size()的情況 ，該函數只是增加長度變量，而 toArray() 使用該函數將節點的值添加到數組中。 toString() 然後方法調用 toArray() 在將返回的數組轉換為字符串並返回之前。

在本文的第 2 部分中，將討論從二叉搜索樹中刪除節點。刪除是一個複雜的問題，需要考慮很多情況，因此需要自己編寫。同時，您可以在我的計算機科學中的 JavaScript GitHub 項目中獲得完整的源代碼。