一文了解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() 中使用的基本算法完全相同：新值小于当前节点向左，如果值更

U盘Exfat格式文件优点和缺点介绍
如何绕过阿里云服务器备案
神狐手机蜂巢营销系统，一种能够分批管理的体系
云服务器租ip
了解一下Node.js Casbin
服务器CPU超载-云服务器问题
云服务器怎么快捷键打开
云服务器网站迁移工具