用JavaScript实现二叉搜索树[每日前端夜话0xA8]

计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表，每个节点包含一些数据，以及两个指向其他节点的指针；它们在这些节点彼此相关联的方式上有所不同。二叉搜索树节点的指针通常被称为“左”和“右”，用来指示与当前值相关的子树。这种节点的简单 JavaScript 实现如下：

1var node = {2    value: 125,3    left: null,4    right: null5};

从名称中可以看出，二叉搜索树被组织成分层的树状结构。第一个项目成为根节点，每个附加值作为该根的祖先添加到树中。但是，二叉搜索树节点上的值是唯一的，根据它们包含的值进行排序：作为节点左子树的值总是小于节点的值，右子树中的值都是大于节点的值。通过这种方式，在二叉搜索树中查找值变得非常简单，只要你要查找的值小于正在处理的节点则向左，如果值更大，则向右移动。二叉搜索树中不能有重复项，因为重复会破坏这种关系。下图表示一个简单的二叉搜索树。

二叉搜索树
上图表示一个二叉搜索树，其根的值为 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 中实现二叉搜索树，第一步要先定义基本接口：

 1function BinarySearchTree() { 2    this._root = null; 3} 4 5BinarySearchTree.prototype = { 6 7    //restore constructor 8    constructor: BinarySearchTree, 910    add: function (value){11    },1213    contains: function(value){14    },1516    remove: function(value){17    },1819    size: function(){20    },2122    toArray: function(){23    },2425    toString: function(){26    }2728};

基本接与其他数据结构类似，有添加和删除值的方法。我还添加了一些方便的方法，size()，toArray()和toString()，它们对 JavaScript 很有用。

要掌握使用二叉搜索树的方法，最好从 contains() 方法开始。contains() 方法接受一个值作为参数，如果值存在于树中则返回 true，否则返回 false。此方法遵循基本的二叉搜索算法来确定该值是否存在：

 1BinarySearchTree.prototype = { 2 3    //more code 4 5    contains: function(value){ 6        var found       = false, 7            current     = this._root 8 9        //make sure there's a node to search10        while(!found && current){1112            //if the value is less than the current node's, go left13            if (value < current.value){14                current = current.left;1516            //if the value is greater than the current node's, go right17            } else if (value > current.value){18                current = current.right;1920            //values are equal, found it!21            } else {22                found = true;23            }24        }2526        //only proceed if the node was found27        return found;28    },2930    //more code3132};

搜索从树的根开始。如果没有添加数据，则可能没有根，所以必须要进行检查。遍历树遵循前面讨论的简单算法：如果要查找的值小于当前节点则向左移动，如果值更大则向右移动。每次都会覆盖 current 指针，直到找到要找的值（在这种情况下 found 设置为 true）或者在那个方向上没有更多的节点了（在这种情况下，值不在树上）。

在 contains() 中使用的方法也可用于在树中插入新值。主要区别在于你要寻找放置新值的位置，而不是在树中查找值：

 1BinarySearchTree.prototype = { 2 3    //more code 4 5    add: function(value){ 6        //create a new item object, place data in 7        var node = { 8                value: value, 9                left: null,10                right: null11            },1213            //used to traverse the structure14            current;1516        //special case: no items in the tree yet17        if (this._root === null){18            this._root = node;19        } else {20            current = this._root;2122            while(true){2324                //if the new value is less than this node's value, go left25                if (value < current.value){2627                    //if there's no left, then the new node belongs there28                    if (current.left === null){29                        current.left = node;30                        break;31                    } else {32                        current = current.left;33                    }3435                //if the new value is greater than this node's value, go right36                } else if (value > current.value){3738                    //if there's no right, then the new node belongs there39                    if (current.right === null){40                        current.right = node;41                        break;42                    } else {43                        current = current.right;44                    }       4546                //if the new value is equal to the current one, just ignore47                } else {48                    break;49                }50            }51        }52    },5354    //more code5556};

在二叉搜索树中添加值时，特殊情况是在没有根的情况。在这种情况下，只需将根设置为新值即可轻松完成工作。对于其他情况，基本算法与 contains() 中使用的基本算法完全相同：新值小于当前节点向左，如果值更大则向右。主要区别在于，当你无法继续前进时，这就是新值的位置。所以如果你需要向左移动但没有左侧节点，则新值将成为左侧节点（与右侧节点相同）。由于不存在重复项，因此如果找到具有相同值的节点，则操作将停止。

在继续讨论 size() 方法之前，我想深入讨论树遍历。为了计算二叉搜索树的大小，必须要访问树中的每个节点。二叉搜索树通常会有不同类型的遍历方法，最常用的是有序遍历。通过处理左子树，然后是节点本身，然后是右子树，在每个节点上执行有序遍历。由于二叉搜索树以这种方式排序，从左到右，结果是节点以正确的排序顺序处理。对于 size() 方法，节点遍历的顺序实际上并不重要，但它对 toArray() 方法很重要。由于两种方法都需要执行遍历，我决定添加一个可以通用的 traverse() 方法：

 1BinarySearchTree.prototype = { 2 3    //more code 4 5    traverse: function(process){ 6 7        //helper function 8        function inOrder(node){ 9            if (node){1011                //traverse the left subtree12                if (node.left !== null){13                    inOrder(node.left);14                }            1516                //call the process method on this node17                process.call(this, node);1819                //traverse the right subtree20                if (node.right !== null){21                    inOrder(node.right);22                }23            }24        }2526        //start with the root27        inOrder(this._root);28    },2930    //more code3132};

此方法接受一个参数 process，这是一个应该在树中的每个节点上运行的函数。该方法定义了一个名为 inOrder() 的辅助函数用于递归遍历树。注意，如果当前节点存在，则递归仅左右移动（以避免多次处理 null ）。然后 traverse() 方法从根节点开始按顺序遍历，process() 函数处理每个节点。然后可以使用此方法实现size()、toArray()、toString()：

 1BinarySearchTree.prototype = { 2 3    //more code 4 5    size: function(){ 6        var length = 0; 7 8        this.traverse(function(node){ 9            length++;10        });1112        return length;13    },1415    toArray: function(){16        var result = [];1718        this.traverse(function(node){19            result.push(node.value);20        });2122        return result;23    },2425    toString: function(){26        return this.toArray().toString();27    },2829    //more code3031};

size() 和 toArray() 都调用 traverse() 方法并传入一个函数来在每个节点上运行。在使用 size()的情况下，函数只是递增长度变量，而 toArray() 使用函数将节点的值添加到数组中。toString()方法在调用 toArray() 之前把返回的数组转换为字符串，并返回。

删除节点时，你需要确定它是否为根节点。根节点的处理方式与其他节点类似，但明显的例外是根节点需要在结尾处设置为不同的值。为简单起见，这将被视为 JavaScript 代码中的一个特例。

删除节点的第一步是确定节点是否存在：

 1BinarySearchTree.prototype = { 2 3    //more code here 4 5    remove: function(value){ 6 7        var found       = false, 8            parent      = null, 9            current     = this._root,10            childCount,11            replacement,12            replacementParent;1314        //make sure there's a node to search15        while(!found && current){1617            //if the value is less than the current node's, go left18            if (value < current.value){19                parent = current;20                current = current.left;2122            //if the value is greater than the current node's, go right23            } else if (value > current.value){24                parent = current;25                current = current.right;2627            //values are equal, found it!28            } else {29                found = true;30            }31        }3233        //only proceed if the node was found34        if (found){35            //continue36        }3738    },39    //more code here4041};

remove()方法的第一部分是用二叉搜索定位要被删除的节点，如果值小于当前节点的话则向左移动，如果值大于当前节点则向右移动。当遍历时还会跟踪 parent 节点，因为你最终需要从其父节点中删除该节点。当 found 等于 true 时，current 的值是要删除的节点。

删除节点时需要注意三个条件：

1.叶子节点

2.只有一个孩子的节点

3.有两个孩子的节点

从二叉搜索树中删除除了叶节点之外的内容意味着必须移动值来对树正确的排序。前两个实现起来相对简单，只删除了一个叶子节点，删除了一个带有一个子节点的节点并用其子节点替换。最后一种情况有点复杂，以便稍后访问。

在了解如何删除节点之前，你需要知道节点上究竟存在多少个子节点。一旦知道了，你必须确定节点是否为根节点，留下一个相当简单的决策树：

 1BinarySearchTree.prototype = { 2 3    //more code here 4 5    remove: function(value){ 6 7        var found       = false, 8            parent      = null, 9            current     = this._root,10            childCount,11            replacement,12            replacementParent;1314        //find the node (removed for space)1516        //only proceed if the node was found17        if (found){1819            //figure out how many children20            childCount = (current.left !== null ? 1 : 0) + 21                         (current.right !== null ? 1 : 0);2223            //special case: the value is at the root24            if (current === this._root){25                switch(childCount){2627                    //no children, just erase the root28                    case 0:29                        this._root = null;30                        break;3132                    //one child, use one as the root33                    case 1:34                        this._root = (current.right === null ? 35                                      current.left : current.right);36                        break;3738                    //two children, little work to do39                    case 2:4041                        //TODO4243                    //no default4445                }        4647            //non-root values48            } else {4950                switch (childCount){5152                    //no children, just remove it from the parent53                    case 0:54                        //if the current value is less than its 55                        //parent's, null out the left pointer56                        if (current.value < parent.value){57                            parent.left = null;5859                        //if the current value is greater than its60                        //parent's, null out the right pointer61                        } else {62                            parent.right = null;63                        }64                        break;6566                    //one child, just reassign to parent67                    case 1:68                        //if the current value is less than its 69                        //parent's, reset the left pointer70                        if (current.value < parent.value){71                            parent.left = (current.left === null ? 72                                           current.right : current.left);7374                        //if the current value is greater than its 75                        //parent's, reset the right pointer76                        } else {77                            parent.right = (current.left === null ? 78                                            current.right : current.left);79                        }80                        break;    8182                    //two children, a bit more complicated83                    case 2:8485                        //TODO          8687                    //no default8889                }9091            }9293        }9495    },9697    //more code here9899};

处理根节点时，这是一个覆盖它的简单过程。对于非根节点，必须根据要删除的节点的值设置 parent 上的相应指针：如果删除的值小于父节点，则 left 指针必须重置为 null（对于没有子节点的节点）或删除节点的 left 指针；如果删除的值大于父级，则必须将 right 指针重置为 null 或删除的节点的 right指针。

如前所述，删除具有两个子节点的节点是最复杂的操作。考虑二元搜索树的以下表示。

二叉搜索树
根为 8，左子为 3，如果 3 被删除会发生什么？有两种可能性：1（3 左边的孩子，称为有序前身）或4（右子树的最左边的孩子，称为有序继承者）都可以取代 3。

这两个选项中的任何一个都是合适的。要查找有序前驱，即删除值之前的值，请检查要删除的节点的左子树，并选择最右侧的子节点；找到有序后继，在删除值后立即出现的值，反转进程并检查最左侧的右子树。其中每个都需要另一次遍历树来完成操作：

1BinarySearchTree.prototype = {  2  3    //more code here  4  5    remove: function(value){  6  7        var found       = false,  8            parent      = null,  9            current     = this._root, 10            childCount, 11            replacement, 12            replacementParent; 13 14        //find the node (removed for space) 15 16        //only proceed if the node was found 17        if (found){ 18 19            //figure out how many children 20            childCount = (current.left !== null ? 1 : 0) +  21                         (current.right !== null ? 1 : 0); 22 23            //special case: the value is at the root 24            if (current === this._root){ 25                switch(childCount){ 26 27                    //other cases removed to save space 28 29                    //two children, little work to do 30                    case 2: 31 32                        //new root will be the old root's left child 33                        //...maybe 34                        replacement = this._root.left; 35 36                        //find the right-most leaf node to be  37                        //the real new root 38                        while (replacement.right !== null){ 39                            replacementParent = replacement; 40                            replacement = replacement.right; 41                        } 42 43                        //it's not the first node on the left 44                        if (replacementParent !== null){ 45 46                            //remove the new root from it's  47                            //previous position 48                            replacementParent.right = replacement.left; 49 50                            //give the new root all of the old  51                            //root's children 52                            replacement.right = this._root.right; 53                            replacement.left = this._root.left; 54                        } else { 55 56                            //just assign the children 57                            replacement.right = this._root.right; 58                        } 59 60                        //officially assign new root 61                        this._root = replacement; 62 63                    //no default 64 65                }         66 67            //non-root values 68            } else { 69 70                switch (childCount){ 71 72                    //other cases removed to save space  73 74                    //two children, a bit more complicated 75                    case 2: 76 77                        //reset pointers for new traversal 78                        replacement = current.left; 79                        replacementParent = current; 80 81                        //find the right-most node 82                        while(replacement.right !== null){ 83                            replacementParent = replacement; 84                            replacement = replacement.right; 85                        } 86 87                        replacementParent.right = replacement.left; 88 89                        //assign children to the replacement 90                        replacement.right = current.right; 91                        replacement.left = current.left; 92 93                        //place the replacement in the right spot 94                        if (current.value < parent.value){ 95                            parent.left = replacement; 96                        } else { 97                            parent.right = replacement; 98                        }           99100                    //no default101102                }103104            }105106        }107108    },109110    //more code here111112};

具有两个子节点的根节点和非根节点的代码几乎相同。此实现始终通过查看左子树并查找最右侧子节点来查找有序前驱。遍历是使用 while 循环中的 replacement 和 replacementParent 变量完成的。replacement中的节点最终成为替换 current 的节点，因此通过将其父级的 right 指针设置为替换的 left 指针，将其从当前位置移除。对于根节点，当 replacement 是根节点的直接子节点时，replacementParent 将为 null，因此 replacement 的 right 指针只是设置为 root 的 right 指针。最后一步是将替换节点分配到正确的位置。对于根节点，替换设置为新根；对于非根节点，替换被分配到原始 parent 上的适当位置。

关于此实现的说明：始终用有序前驱替换节点可能导致不平衡树，其中大多数值会位于树的一侧。不平衡树意味着搜索效率较低，因此在实际场景中应该引起关注。在二叉搜索树实现中，要确定是用有序前驱还是有序后继以使树保持适当平衡（通常称为自平衡二叉搜索树）。

这个二叉搜索树实现的完整源代码可以在我的GitHub 中【http://github.com/nzakas/computer-science-in-javascript/】中找到。对于替代实现，你还可以查看 Isaac Schlueter 的 GitHub fork【http://github.com/isaacs/computer-science-in-javascript】。

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

更多相关文章

随机推荐