什么是二叉树

二叉树就是树的每个节点最多只能有两个子节点

什么是二叉搜索树

二叉搜索树在二叉树的基础上，多了一个条件，就是二叉树在插入值时，若插入值比当前节点小，就插入到左节点，否则插入到右节点；若插入过程中，左节点或右节点已经存在，那么继续按如上规则比较，直到遇到一个新的节点。

二叉搜索树的特性

二叉搜索树由于其独特的数据结构，使得其无论在增删，还是查找，时间复杂度都是O(h)，h为二叉树的高度。因此二叉树应该尽量的矮，即左右节点尽量平衡。

二叉搜索树的构造

要构造二叉搜索树，首先要构造二叉树的节点类。由二叉树的特点可知，每个节点类都有一个左节点，右节点以及值本身，因此节点类如下：

class Node {
 constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

接着构造二叉搜索树

class Tree{
 constructor(param = null) {
  if (param) {
   this.root = new Node(param);
  } else {
   this.root = null;
  }
 }
}

这里this.root就是当前对象的树。

二叉搜索树的新增

由二叉搜索树左子树比节点小，右子树别节点大的特点，可以很简单的写出二叉搜索树新增的算法，如下：

insert(key) {
 if (this.root === null) {
  this.root = new Node(key);
 } else {
  this._insertNode(this.root, key);
 }
}
_insertNode(node, key) {
 if (key < node.key) {
  if (node.left === null) {
   node.left = new Node(key);{1}
  } else {
   this._insertNode(node.left, key);{2}
  }
 } else if (key > node.key) {
  if (node.right === null) {
   node.right = new Node(key);{3}
  } else {
   this._insertNode(node.right, key);{4}
  }
 }
}

如上代码先判断新增的key与当前节点的key大小，如果小，就递归遍历左子节点，直到找到一个为null的左子节点；如果比当前节点大同理。如上代码{1}{2}{3}{4}之所以能改变this.root的值，是由于JavaScript函数是按值传递，而当参数是非基本类型时，例如这里的对象，其对象的值为内存，因此每次都会直接改变this.root的内容。

二叉搜索树的遍历

二叉搜索树分为先序、中序、后序三种遍历方式。

inOrderTraverse(callback) {
 this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
 if (node) {
  this._inOrderTraverse(node.left, callback);
  callback(node.key);
  this._inOrderTraverse(node.right, callback);
 }
}

如上是中序遍历。

这里需要理解的一点是递归。要知道，函数的执行可以抽象为一种数据结构——栈。针对函数的执行，会维护一个栈，来存储函数的执行。函数在每一次递归时，都会将当前的执行环境入栈并记录执行的位置。以上述代码为例，有如下一个数据

其会从11开始，执行{1}入栈，然后进入7，接着执行{1}入栈，然后到5，执行{1}入栈，再到3，执行{1}入栈，此时发现节点3的左子节点为null，因此开始出栈，此时弹出节点3的执行环境，执行{2}，{3}，发现3的右侧子节点也为null，{3}的递归执行完毕，接着弹出节点5，执行{2}{3}，接着弹出7，执行{2}{3}入栈，执行{3}时，发现节点7有右节点，因此继续执行{1}，到节点8，再执行{1}，8没有左子节点，{1}执行完毕，执行{2}{3}，以此类推。

而前序与中序的不同点在于其先访问节点本身，也就是代码的执行顺序为 2 1 3。

后序同理，执行顺序为1 3 2

不难发现，无论前中后序，永远都是先递归左节点，当左节点遍历完毕时再弹出栈，遍历有节点。他们唯一不同的点在与访问该节点本身的时机。

二叉搜索树的查找

查找很简单，根据左子节点比该节点小，右子节点比该节点大的原则进行循环判断即可。

search(value) {
 if (this.root) {
  if (value === this.root.key) {
   return true;
  } else {
   return this._searchNode(value, this.root);
  }
 }
 throw new Error('this.root 不存在');
}
_searchNode(value, node) {
 if (!node) {
  return false;
 }
 if (value === node.key) {
  return true;
 }
 if (value > node.key) {
  return this._searchNode(value, node.right);
 } else if (value < node.key) {
  return this._searchNode(value, node.left);
 }
}

二叉搜索树的删除

删除较为复杂，需要根据不同情况判断

首先判断该节点是否有左子树，如果没有左子节树，则直接将右子树的根节点替换被删除节点；

如果有，则将右子树的最小节点替换被删除节点；

remove(key) {
 this._removeNode(this.root, key);
}
_removeNode(node, value) {
 if (!node) {
  return null;
 }
 if (value > node.key) {
  node.right = this._removeNode(node.right, value);
 } else if (value < node.key) {
  node.left = this._removeNode(node.left, value);
 } else {
  // 如果没有左子树，那么将右子树根节点作为替换节点
  if (!node.left) {
   return node.right;
   // 如果存在左子树，那么取右子树最小节点作为替换节点
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}

总结

总的来说，通过这次简单的二叉搜索树的学习，让我重新认识了递归，以前对于递归的理解只是一些简单的理论概念，这次深入实践让我对递归的理解又加深了许多。

这让我想到了数学的学习，数学的理论公式是很容易记住掌握的，如果说对一个知识点的掌握满分是十分，那么直到真正去实践它之前，只看公式的掌握只能是2分，因为公式很简单，就几句话几个原则，但是遇到的问题是千变万化的，只有真正将理论付诸实践，经过各种实践的打磨蹂躏，才能真正理解它其中的奥秘。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# javascript  # 二叉搜索树  # 二叉树搜索算法  # 二叉树  # javascript数据结构之二叉搜索树实现方法  # Javascript实现从小到大的数组转换成二叉搜索树  # JavaScript实现二叉搜索树  # 如何利用JavaScript实现二叉搜索树  # 面向JavaScript入门初学者的二叉搜索树算法教程  # JavaScript二叉搜索树构建操作详解  # 子树  # 递归  # 遍历  # 弹出  # 很简单  # 数据结构  # 如果没有  # 其先  # 都是  # 我想  # 几个  # 让我  # 都有  # 基础上  # 我对  # 付诸实践  # 以此类推  # 很容易  # 不存在 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： Laravel如何创建自定义中间件？（Middleware代码示例）  Laravel如何发送系统通知_Laravel Notifications实现多渠道消息通知  Internet Explorer官网直接进入 IE浏览器在线体验版网址  php中::能调用final静态方法吗_final修饰静态方法调用规则【解答】  网站建设要注意的标准 促进网站用户好感度！  bing浏览器学术搜索入口_bing学术文献检索地址  Laravel如何优化应用性能？（缓存和优化命令）  Laravel表单请求验证类怎么用_Laravel Form Request分离验证逻辑教程  Android Socket接口实现即时通讯实例代码  如何用JavaScript实现文本编辑器_光标和选区怎么处理  微信推文制作网站有哪些,怎么做微信推文，急？  Laravel如何清理系统缓存命令_Laravel清除路由配置及视图缓存的方法【总结】  Laravel怎么创建控制器Controller_Laravel路由绑定与控制器逻辑编写【指南】  如何在万网自助建站中设置域名及备案？  如何获取上海专业网站定制建站电话？  详解Oracle修改字段类型方法总结  Win11怎么查看显卡温度 Win11任务管理器查看GPU温度【技巧】  如何为不同团队 ID 动态生成多个非值班状态按钮  制作ppt免费网站有哪些,有哪些比较好的ppt模板下载网站？  猪八戒网站制作视频,开发一个猪八戒网站，大约需要多少？或者自己请程序员，需要什么程序员，多少程序员能完成？  微博html5版本怎么弄发语音微博_语音录制入口及时长限制操作【教程】  Laravel Docker环境搭建教程_Laravel Sail使用指南  Java解压缩zip - 解压缩多个文件或文件夹实例  成都网站制作公司哪家好,四川省职工服务网是做什么用？  Laravel如何发送邮件_Laravel Mailables构建与发送邮件的简明教程  Laravel N+1查询问题如何解决_Eloquent预加载(Eager Loading)优化数据库查询  网站图片在线制作软件,怎么在图片上做链接？  如何快速选择适合个人网站的云服务器配置？  如何在宝塔面板中创建新站点？  详解ASP.NET 生成二维码实例（采用ThoughtWorks.QRCode和QrCode.Net两种方式）  如何生成腾讯云建站专用兑换码？  手机软键盘弹出时影响布局的解决方法  Windows10如何更改计算机工作组_Win10系统属性修改Workgroup  Swift中swift中的switch 语句  高端建站三要素：定制模板、企业官网与响应式设计优化  用v-html解决Vue.js渲染中html标签不被解析的问题  个人摄影网站制作流程,摄影爱好者都去什么网站？  Laravel如何实现多对多模型关联？（Eloquent教程）  JavaScript数据类型有哪些_如何准确判断一个变量的类型  WordPress 子目录安装中正确处理脚本路径的完整指南  如何快速配置高效服务器建站软件？  Laravel如何使用查询构建器？（Query Builder高级用法）  Laravel如何获取当前用户信息_Laravel Auth门面获取用户ID  深圳网站制作公司好吗,在深圳找工作哪个网站最好啊？  独立制作一个网站多少钱,建立网站需要花多少钱？  Java Adapter 适配器模式（类适配器，对象适配器）优缺点对比  Laravel如何发送系统通知？（Notification渠道示例）  Claude怎样写约束型提示词_Claude约束提示词写法【教程】  uc浏览器二维码扫描入口_uc浏览器扫码功能使用地址  Laravel策略(Policy)如何控制权限_Laravel Gates与Policies实现用户授权