一文了解JS实现二叉搜索树的方法
计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表，每个节点包含一些数据，以及两个指向其他节点的指针；它们在这些节点彼此相关联的方式上有所不同。二叉搜索树节点的指针通常被称为“左”和“右”，用来指示与当前值相关的子树。这种节点的简单 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() 之前把返回的数组转换为字符串，并返回 。
删除节点时，你需要确定它是否为根节点。根节点的处理方式与其他节点类似，但明显的例外是根节点需要在结尾处设置为不同的值。为简单起见，这将被视为 JavaScript 代码中的一个特例。
删除节点的第一步是确定节点是否存在：
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()方法的第一部分是用二叉搜索定位要被删除的节点，如果值小于当前节点的话则向左移动，如果值大于当前节点则向右移动。当遍历时还会跟踪 parent 节点，因为你最终需要从其父节点中删除该节点。当 found 等于 true 时，current 的值是要删除的节点。
删除节点时需要注意三个条件：
1、叶子节点
2、只有一个孩子的节点
3、有两个孩子的节点
从二叉搜索树中删除除了叶节点之外的内容意味着必须移动值来对树正确的排序。前两个实现起来相对简单，只删除了一个叶子节点，删除了一个带有一个子节点的节点并用其子节点替换。最后一种情况有点复杂，以便稍后访问。
在了解如何删除节点之前，你需要知道节点上究竟存在多少个子节点。一旦知道了，你必须确定节点是否为根节点，留下一个相当简单的决策树：
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
};处理根节点时，这是一个覆盖它的简单过程。对于非根节点，必须根据要删除的节点的值设置 parent 上的相应指针：如果删除的值小于父节点，则 left 指针必须重置为 null （对于没有子节点的节点）或删除节点的 left 指针；如果删除的值大于父级，则必须将 right 指针重置为 null 或删除的节点的 right指针。
如前所述，删除具有两个子节点的节点是最复杂的操作。考虑二元搜索树的以下表示。
根为 8，左子为 3，如果 3 被删除会发生什么？有两种可能性：1（3 左边的孩子，称为有序前身）或4（右子树的最左边的孩子，称为有序继承者）都可以取代 3。
这两个选项中的任何一个都是合适的。要查找有序前驱，即删除值之前的值，请检查要删除的节点的左子树，并选择最右侧的子节点；找到有序后继，在删除值后立即出现的值，反转进程并检查最左侧的右子树。其中每个都需要另一次遍历树来完成操作：
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
};具有两个子节点的根节点和非根节点的代码几乎相同。此实现始终通过查看左子树并查找最右侧子节点来查找有序前驱。遍历是使用 while 循环中的 replacement 和 replacementParent 变量完成的。
replacement中的节点最终成为替换 current 的节点，因此通过将其父级的 right 指针设置为替换的 left 指针，将其从当前位置移除。
对于根节点，当 replacement 是根节点的直接子节点时，replacementParent 将为 null，因此 replacement 的 right 指针只是设置为 root 的 right 指针。
最后一步是将替换节点分配到正确的位置。对于根节点，替换设置为新根；对于非根节点，替换被分配到原始 parent 上的适当位置。
关于此实现的说明：始终用有序前驱替换节点可能导致不平衡树，其中大多数值会位于树的一侧。不平衡树意味着搜索效率较低，因此在实际场景中应该引起关注。在二叉搜索树实现中，要确定是用有序前驱还是有序后继以使树保持适当平衡（通常称为自平衡二叉搜索树）。
这个二叉搜索树实现的完整源代码可以在我的GitHub 中找到。对于替代实现，你还可以查看 Isaac Schlueter 的 GitHub fork。
本文转载自：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实现二叉搜索树的方法的详细内容。更多信息请关注PHP中文网其他相关文章！
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！
热门文章
热工具
记事本++7.3.1
好用且免费的代码编辑器
SublimeText3汉化版
中文版，非常好用
禅工作室 13.0.1
功能强大的PHP集成开发环境
Dreamweaver CS6
视觉化网页开发工具
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
如何使用WebSocket和JavaScript实现在线语音识别系统
Dec 17, 2023 pm 02:54 PM
如何使用WebSocket和JavaScript实现在线语音识别系统引言：随着科技的不断发展，语音识别技术已经成为了人工智能领域的重要组成部分。而基于WebSocket和JavaScript实现的在线语音识别系统，具备了低延迟、实时性和跨平台的特点，成为了一种被广泛应用的解决方案。本文将介绍如何使用WebSocket和JavaScript来实现在线语音识别系
WebSocket与JavaScript：实现实时监控系统的关键技术
Dec 17, 2023 pm 05:30 PM
WebSocket与JavaScript：实现实时监控系统的关键技术引言：随着互联网技术的快速发展，实时监控系统在各个领域中得到了广泛的应用。而实现实时监控的关键技术之一就是WebSocket与JavaScript的结合使用。本文将介绍WebSocket与JavaScript在实时监控系统中的应用，并给出代码示例，详细解释其实现原理。一、WebSocket技
如何利用JavaScript和WebSocket实现实时在线点餐系统
Dec 17, 2023 pm 12:09 PM
如何利用JavaScript和WebSocket实现实时在线点餐系统介绍：随着互联网的普及和技术的进步，越来越多的餐厅开始提供在线点餐服务。为了实现实时在线点餐系统，我们可以利用JavaScript和WebSocket技术。WebSocket是一种基于TCP协议的全双工通信协议，可以实现客户端与服务器的实时双向通信。在实时在线点餐系统中，当用户选择菜品并下单
如何使用WebSocket和JavaScript实现在线预约系统
Dec 17, 2023 am 09:39 AM
如何使用WebSocket和JavaScript实现在线预约系统在当今数字化的时代，越来越多的业务和服务都需要提供在线预约功能。而实现一个高效、实时的在线预约系统是至关重要的。本文将介绍如何使用WebSocket和JavaScript来实现一个在线预约系统，并提供具体的代码示例。一、什么是WebSocketWebSocket是一种在单个TCP连接上进行全双工
JavaScript和WebSocket：打造高效的实时天气预报系统
Dec 17, 2023 pm 05:13 PM
JavaScript和WebSocket：打造高效的实时天气预报系统引言：如今，天气预报的准确性对于日常生活以及决策制定具有重要意义。随着技术的发展，我们可以通过实时获取天气数据来提供更准确可靠的天气预报。在本文中，我们将学习如何使用JavaScript和WebSocket技术，来构建一个高效的实时天气预报系统。本文将通过具体的代码示例来展示实现的过程。We
简易JavaScript教程：获取HTTP状态码的方法
Jan 05, 2024 pm 06:08 PM
JavaScript教程：如何获取HTTP状态码，需要具体代码示例前言：在Web开发中，经常会涉及到与服务器进行数据交互的场景。在与服务器进行通信时，我们经常需要获取返回的HTTP状态码来判断操作是否成功，根据不同的状态码来进行相应的处理。本篇文章将教你如何使用JavaScript获取HTTP状态码，并提供一些实用的代码示例。使用XMLHttpRequest
javascript中如何使用insertBefore
Nov 24, 2023 am 11:56 AM
用法：在JavaScript中，insertBefore()方法用于在DOM树中插入一个新的节点。这个方法需要两个参数：要插入的新节点和参考节点（即新节点将要被插入的位置的节点）。
如何在JavaScript中获取HTTP状态码的简单方法
Jan 05, 2024 pm 01:37 PM
JavaScript中的HTTP状态码获取方法简介：在进行前端开发中，我们常常需要处理与后端接口的交互，而HTTP状态码就是其中非常重要的一部分。了解和获取HTTP状态码有助于我们更好地处理接口返回的数据。本文将介绍使用JavaScript获取HTTP状态码的方法，并提供具体代码示例。一、什么是HTTP状态码HTTP状态码是指当浏览器向服务器发起请求时，服务
