本文通过实例描述了JS中数据结构的算法和二叉排序树。分享给大家参考，如下：

二叉查找树（Binary Sort Tree）

我们之前学过的列表和栈都是线性数据结构。今天，我们将学习一种在计算机中经常使用的非线性数据结构，——树。因为存储在其中的所有元素都具有明显的层次特征，所以它们通常用于存储具有层次关系的数据，例如文件系统中的文件。它还可以用来存储有序列表等。

在树结构中，每个节点只有一个前因，称为父节点，只有一个没有前因的节点，简称为树的根节点。每个节点可以有多个后置片段，这些后置片段称为节点的子节点。没有后缀的节点称为叶节点。一个节点所拥有的子节点数称为该节点的度，所有节点中最大的度称为树的度。一棵树的最大高度叫做树的深度。

二叉树

二叉树是一种不超过两个子节点的特殊树，分别称为该节点的左子树和右子树。二叉树常用作二叉查找树树、二进制堆或二进制排序树(BST)。

二叉树

按照一定的规则和顺序遍历二叉树的所有节点，使每个节点只被访问一次。这个操作叫做树遍历，是对树的一个基本操作。因为二叉树是一个非线性结构，所以树的遍历本质上是将二叉树的每个节点转换成一个线性序列来表示它。

根据根节点访问的顺序，树的遍历可以分为以下三种：前序遍历、中序遍历和后序遍历；

前言遍历：根节点-左子树-右子树

前序遍历

中间顺序遍历：左子树-根节点-右子树

有序遍历

后序遍历：左子树-右子树-根节点

后序遍历

因此，我们可以得到上述二叉树的遍历结果如下：前序遍历：ABDEFGC中序遍历：DEBGFAC后序遍历：EDGFBCA

二叉查找树（BST）

在实践中，树的每个节点都会有一个与之对应的值，这有时被称为键。因此，当我们构建二叉查找树时，确定子节点非常重要。通常情况下，相对较小的值存储在左节点，而较大的值存储在右节点，这使得搜索效率非常高，因此被广泛使用。

二叉查找树的实现

根据上面的知识，我们知道二叉树实际上是由多个节点组成的，所以我们必须首先定义一个Node类来存储树的节点，其结构类似于前面的链表。节点类的定义如下：

//node定义功能节点(数据，左，右){this。数据=数据；//data this . left=left；//左节点this.right=right//右节点this.show=show//显示节点数据}函数show(){ return this . data；} node对象不仅保存数据，还保存其左右节点之间的链接，其中show方法用于显示当前保存在节点中的数据。

现在我们可以创建一个类来表示二进制查找号(BST)。我们的初始化类只包含一个成员，一个代表二进制查找树根节点的Node对象，它被初始化为null，这意味着创建一个空节点。

//二叉查找树(bst)的类函数BST(){ this。root=null//根节点this.insert=insert//插入节点this.preOrder=preOrder//遍历this.inOrder=inOrder first//遍历this.postOrder=中间顺序的postOrder//遍历this.find=find//查找节点this.getMin=getMin//求最小值this.getMax=getMax//查找最大值this.remove=remove//删除节点}现在，我们需要向类中添加方法。

第一个是insert方法，它向树中添加一个新节点。我们一起来看看这个方法；

插入：向树中添加新节点

因为添加节点涉及到插入位置的问题，所以必须放在正确的位置才能保证树的正确性。整个过程很复杂。让我们一起来整理一下：

要先添加一个新节点，您需要创建一个节点对象并将数据传递到其中。

其次，检查当前的BST树是否有根节点，如果没有，那么表示有新的编号，这个节点就是树的根节点，那么插入过程就结束了；否则，有必要进行下一步。

如果要插入的节点不是根节点，必须遍历BST才能找到合适的位置。这个过程类似于遍历链表，用一个变量存储当前节点，逐层遍历BST。算法如下：

将当前节点设置为根节点。如果要插入的节点保存的数据小于当前节点，则新节点是原始节点的左节点。否则，执行步骤4。如果当前节点的左节点为空，将新节点放在此位置并退出循环。相反，继续执行下一个循环，将新节点设置为原节点的右节点。如果当前节点的右节点为空，将新节点放在该位置，退出循环；相反，继续执行下一个周期，以确保每次添加的新节点都能放在正确的位置，具体实现如下；

//插入新节点函数insert (data) {var n=新节点(data，null，null)；if(this . root==null){ this . root=n；} else { var current=this.rootvar父级；while(true){ parent=current；if(data current . data){ current=current . left；if(current==null){ parent . left=n；打破；} } else { current=current.rightif(current==null){ parent . right=n；打破；}}}}}现在BST类已经初步形成，但操作仅限于插入节点。我们需要有遍历BST的能力，我们也提到了有三种遍历模式。其中，中间顺序遍历最容易实现。我们需要按照升序访问树中的所有节点，首先访问左边的子树，然后访问根节点，最后访问右边的子树。我们用递归来实现它！

中间顺序遍历

//遍历函数inOrder (node) {if(！(node==null)){ Inorder(node . left)；console . debug(node . show()' ')；inoder(node . right)；}}怎么样？知道了原理，实现起来还是挺简单的~

让我们用一段代码来测试我们编写的中间顺序遍历：

var nums=new BST()；//插入数据nums . insert(23)；nums . insert(45)；nums . insert(16)；nums . insert(37)；nums . insert(3)；nums . insert(99)；nums . insert(22)；插入上述数据后，将形成以下二叉树

牛生长激素

中间顺序遍历结果如下：

//遍历console.log('按顺序遍历： ')；inOrder(nums . root)；//有序遍历：//3 16 22 23 37 45 99预排序：优先遍历

有了中序遍历的基础，相信你已经想通了一阶遍历的实现，怎么样？看看吧。

//遍历函数preOrder(node) {if(！(node==null)){ console . log(node . show()' ')；preOrder(node . left)；preOrder(node . right)；}}，是否类似于中序遍历？唯一的区别是if语句中代码的执行顺序。在中间顺序遍历中，show方法放在两个递归调用之间，而第一个顺序遍历放在递归调用之前。

顺序遍历的结果如下：

//先遍历console . log(' preorder遍历3360 ')；preOrder(nums . root)；//前序遍历：//23 16 3 22 45 37 99后序：后序遍历

后序遍历的实现与前一个基本相同，show方法可以在递归调用后执行

//遍历函数postOrder(节点){if(！(node==null)){ PostOrder(node . left)；posterorder(node . right)；console . log(node . show()' ')；}}遍历结果如下：

//遍历console.log('后序遍历： ')；post ORder(nums . root)；//PostOrder遍历：//3 22 16 37 99 45 23

二叉查找树的查找运算

BST通常有三种搜索类型：

寻找给定值、寻找最大值和寻找最小值，我们将一起讨论这三种搜索方法的实现。

在BST中求最小值和最大值非常简单。因为较小的值总是在左边的子节点上，所以如果想在BST中找到最小值，只需要遍历左边的子树，直到找到最后一个节点。同样，要找到最大值，您只需要遍历右子树，直到找到最后一个节点。

求最小值

遍历左子树，直到左子树中节点的左边为空，并且该节点保持最小值

//求最小值函数getmin(){ var current=this . root；while(！(current . left==null)){ current=current . left；}返回current . show()；}getMax:求最大值

遍历右子树，直到右子树中节点的右侧为空，并且该节点保持最大值

//求最大值函数getmax(){ var current=this . root；while(！(current . right==null)){ current=current . right；}返回current . show()；}我们仍然使用之前构建的树来测试：

//最小值为console . log(' min : ' nums . getmin())；//min : 3//max console . log(' max : ' nums . getmax())；//max : 99要在BST上找到给定值，需要将给定值与当前节点中存储的值进行比较。通过比较，可以确定给定值是否在当前节点。根据BST的特点，qu接下来会向左或向右遍历。

//查找给定值函数find(data){ var current=this . root；while(当前！=null){ if(current . data==data){ return current；} else if(current . data data){ current=current . right；} else { current=current.left} }返回null}如果找到给定值，则该方法返回持有该值的节点，否则返回null；

//查找不存在的值console . log(' find : ' nums . find(66))；//find : null//查找现有值console . log(' find : ' nums . find(99))；//find:【对象对象】

二叉查找树的删除运算

从BST中删除节点的操作最为复杂，其复杂程度取决于被删除节点的位置。如果要删除的节点没有子节点，那就很简单了。如果删除包含左子节点或右子节点的子节点，就会变得有点复杂。删除一个有两个节点的节点是最复杂的。

我们使用递归的方法来完成复杂的删除操作，我们定义了两种方法：remove()和removeNode()。算法思路如下：

首先，判断当前节点是否包含要删除的数据，如果包含，则删除该节点；如果不是，比较当前节点上的数据和要删除的树之间的大小关系。如果要删除的数据小于当前节点的数据，则移动到当前节点的左子节点继续比较；如果大于，则移动到当前节点的右子节点继续比较。如果要删除的节点是叶节点(没有子节点)，那么只有从父节点指向它的链接需要变为空；如果要删除的节点包含子节点，则需要调整原来指向它的节点指向它的子节点；最后，如果要删除的节点包含两个子节点，可以选择在要删除的节点的左侧子树上寻找最大值，或者在右侧子树上寻找最小值，这里我们选择后者。因此，我们需要一种方法，在树上找到最小值，然后用它找到最小值创建一个临时节点，将临时节点上的值复制到要删除的节点上，然后删除临时节点；

我们上面说过，我们将使用两种方法，其中remove方法只是接收要删除的数据，并调用removeNode将其删除。主要工作在removeNode中完成，定义如下：

//删除操作函数remove(数据){remove node(本。根，数据)；}//查找最小值函数getsmallst (node) {if (node。left==null){返回节点；} else { return getminist(node . left)；}}//delete node函数删除节点(node，data){ if(node==null){ return null；} if(data==node.data) {//一个没有子节点的节点if (node。left==null节点。right==null){ return null；}//node if不带左子节点(node。left==null){返回节点。右；}//node if (node。right==null)没有右子节点{return node。向左；}//有两个子节点的节点，vartempnode=getsmallst (node。右)；node . data=tempnode . data；node . right=remove node(node . right，tempnode . data)；返回节点；} else if(data node . data){ node . left=remove node(node . left，data)；返回节点；} else { node . right=remove node(node . right，data)；返回节点；}}现在让我们尝试删除该节点。

//删除根节点nums . remove(23)；inOrder(nums . root)；//3 16 22 37 45 99成功！现在，我们的BST完成了。

现在我们可以用js实现一个简单的BST。在实践中，树木将被广泛使用。希望大家多了解树的数据结构，多练习。相信你会收获很多！

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun来测试上述代码的运行效果。

更多对JavaScript相关内容感兴趣的读者可以查看本网站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript错误与调试技巧总结》和0103010

希望本文对JavaScript编程有所帮助。