数据结构(js实现)——图解二叉搜索树_二叉搜索树怎么画-程序员宅基地
文章目录
1.概念
二叉搜索树（BST），又称二叉排序树和二叉查找树。
二叉搜索树是一颗二叉树，可以为空，如果不为空，则满足以下三个条件：
- 非空左子树的所有键值小于根节点的键值
- 非空右子树的所有键值大于根节点的键值
- 左右子树本身也是二叉搜索树
下图就是一个二叉搜索树：
二叉搜索树的特点：
- 相对较小的值总是保存在根节点的左侧，反之在右侧
- 查找效率非常高
例如我们在上图的二叉搜索书中要查找10这个元素，那我们的路径就是9-13-11-10
2.二叉搜索树的封装以及常见操作
首先我们想一下二叉树的结构。有一个根节点，其次就是每一个结点，而每一个节点上又包括data，与指向左右结点的指针。如图：
因此我们可以写出它的结构：
function BinarySerachTree() {
// 结点类
function Node(key) {
this.key=key;
this.left=null;
this.right=null;
}
// 属性
this.root=null;
// 方法
//insert(key)：向树中插入一个一个新的键
//search(key)：在树中查找一个键，如果结点存在
//move(key):移除某个键
//OrderTravers:中序遍历
//preOrderTravers:先序遍历
//posstOrderTravers:后序遍历
//min：返回树中的最小值
//max：返回树中的最大值
}
接下来让我们一起来实现这些方法吧
3.插入操作的封装
步骤：
1.创建key结点
2.判断根节点是否有值
2.1 若无值则将结点赋给根节点
2.2 若有值则递归调用以此判断插入或继续递归
3.递推实现
3.1： 判断路径方向
3.2：往下走后再判断是否有值，若有值，则继续递归，若无值，则赋值
实现代码：
BinarySerachTree.prototype.insert = function (key) {
// 1.创建key结点
var newnode = new Node(key);
// 2.判断根节点是否有值
if (this.root == null) {
// 2.1 若无值则将结点赋给根节点
this.root = newnode
} else {
// 2.2 若有值则递归调用以此判断插入或继续递归
this.insertNode(this.root, newnode)
}
}
// 插入函数的递归函数
BinarySerachTree.prototype.insertNode = function (node, newnode) {
/*
判断路径方向
判断是否有值，若有值，则继续递归，若无值，则赋值
*/
if (newnode.key < node.key) {
// 如果新节点小于根节点，则向左走
if (node.left == null) {
node.left = newnode
} else {
this.insertNode(node.left, newnode)
}
} else {
// 如果新节点大于根节点，则向右走
if (node.right == null) {
node.right = newnode
} else {
this.insertNode(node.right, newnode)
}
}
}
我们可以测试一组数据：
11-7-15-5-3-9-8-10-13-12-14-20-18-25
结果如图下所绘：
验证一下我们代码也是没有问题的：
4.三种遍历方式封装
二叉搜索树的遍历有三种方式：先序遍历、中序遍历、后序遍历。
这里需要慢慢理解，最好自己画一个图再去结合代码一步一步推导
遍历树的三种方式代码实现我们都可以使用递归的方式来实现。
4.1 先序遍历
先序遍历在每一次递归操作时先访问根节点（11），然后递归访问左子树知道为null是开始回溯，每回溯一次再进入右子树递归。
/* 先序遍历 */
BinarySerachTree.prototype.preOrderTravers = function (callback) {
this.preOrderTraversNode(this.root, callback)
}
BinarySerachTree.prototype.preOrderTraversNode = function (nownode, callback) {
if (nownode != null) {
callback(nownode.key);
// 递归调用左子树
this.preOrderTraversNode(nownode.left, callback)
// 左子树调用结束后直接右子树
this.preOrderTraversNode(nownode.right, callback)
}
}
结果：
4.2 中序遍历
中序遍历每次先开始递归左节点，左节点完后开始回溯时访问目标结点，接着再去递归访问目标结点的右节点。
/* 中序遍历 */
BinarySerachTree.prototype.middleOrderTravers = function (callback) {
this.middleOrderTraversNode(this.root, callback)
}
BinarySerachTree.prototype.middleOrderTraversNode = function (nownode, callback) {
if (nownode != null) {
this.middleOrderTraversNode(nownode.left, callback)
callback(nownode.key);
this.middleOrderTraversNode(nownode.right, callback)
}
}
4.3 后序遍历
后续遍历先一次递归左侧结点，再去递归右侧结点，再去访问目标结点，依次进行
/* 后序遍历 */
BinarySerachTree.prototype.postOrderTravers = function (callback) {
this.postOrderTraversNode(this.root, callback)
}
BinarySerachTree.prototype.postOrderTraversNode = function (nownode, callback) {
if (nownode != null) {
this.postOrderTraversNode(nownode.left, callback)
this.postOrderTraversNode(nownode.right, callback)
callback(nownode.key);
}
}
5.获取最大值和最小值
根据二叉搜索树的结构我们分析以下它的最小值于最大值分布。首先我们知道bst树左子树永远存储比根节点小的树，而右子树永远存储比根节点大的数。所以我们是否就可以得出结论，最深层的左子树就是最小值，反之，最深层的右子树就是最大值。
那么我们的代码如何实现呢？往下看：
实现的原理很简单，我们就拿最大值来说，我们从根节点开始遍历（若没有元素则返回-1），一直遍历当前结点的右子树，知道为空则结束。
左右操作相同，不在赘述。
BinarySerachTree.prototype.getmaxNode = function () {
let node=this.root;
while (node.right!=null) {
node=node.right
}
return node.key
}
BinarySerachTree.prototype.getminNode = function () {
let node=this.root;
while (node.left!=null) {
node=node.left
}
return node.key
}
6.搜索特定的值
其实这个问题我们上面已经讨论过了，这和我们插入值的操作时一样的，都是先找到这个特定的值应该出现的位置，再去判断此位置是否有值存在，如果没有则返回false，如果有则为true。
下面我们来使用代码来实现它吧。
递归实现：
/*搜索特定的值 */
BinarySerachTree.prototype.searchThekey = function (key) {
// 首先判断是否有值存在
if (this.root == null) {
return false;
}
// 递归操作
return this.searchThekeyNode(this.root, key);
}
// 搜索特定的值的递归操作
BinarySerachTree.prototype.searchThekeyNode = function (node, key) {
if (node === null) {
return false
}
if (key > node.key) {
return this.searchThekeyNode(node.right, key);
} else if (key < node.key) {
return this.searchThekeyNode(node.left, key);
} else {
return true
}
}
非递归实现：
/*搜索特定的值(非递归实现)*/
BinarySerachTree.prototype.searchThekeybywhile = function (key) {
var node = this.root;
if (node === null) {
return false;
}
while (node!=null) {
if (key>node.key) {
node = node.right
}else if(key<node.key){
node = node.left
}else{
return true
}
}
return false
}
7.删除操作
删除操作这里由三种情况需要被考虑。
- 删除的结点是叶子节点（没有子节点）
- 删除的结点有一个子节点
- 删除的结点有两个子节点
在开始之前我们先做一下准备工作：
首先我们需要找到我们要删除的目标结点，这里的操作其实和我们上面搜索特定的值的操作是十分相似的。
这里需要定义三个变量：
-
是用于储存当前结点的current
-
用于储存当前结点的父节点的的parent（这是因为如果此时删除的结构为第二三种时current的子节点需指向parent）
-
用于记录当前的current是在父节点的parent的左侧还是右侧的isLeftChild
/* 移除节点 */
BinarySerachTree.prototype.remove = function (key) {
var current=this.root;
var parent=this.root;
var isLeftChild=true;
// 查找
while (current.key!=key) {
parent=current;
if (key>current.key) {
isLeftChild=false;
current=current.right
} else {
isLeftChild=true;
current=current.left
}
if (current==null) {
return false;
}
}
return true
}
7.1 结点是叶子节点（没有子节点）
当结点时叶子节点时我们直接将其删除即可。如果结点为根节点则直接将其置空。
如图所示两种情况：
if (current.left==null&¤t.right==null) {
if (current==this.root) {
this.root=null
}else if(isLeftChild){
parent.left=null
}else{
parent.right=null
}
}
7.2 删除的结点有一个子节点
当删除的结点有一个子结点时。我们需要考虑几种情况。
首先我们应该先判断唯一的子树是左边还是右边。
其次再使用我们上文提到的isLeftChild 来判断当前结点时父节点的左子树还是右子树。然后我们再进行操作即可。
首先当current是parent的左子树时有以下两种情况：
其次当current是parent的右子树时有以下两种情况：
最后我们还需要考虑当current为跟结点时的情况。
具体实现代码如下：
else if (current.left == null) {
if (current == this.root) {
this.root = current.right
} else if (isLeftChild) {
parent.left = current.right
} else {
parent.right = current.right
}
} else if (current.right == null) {
if (current == this.root) {
this.root = current.left
} else if (isLeftChild) {
parent.left = current.left
} else {
parent.right = current.left
}
}
7.3 删除的结点有两个子节点
这种情况是最复杂的一种情况。我们不得不考虑以下几个问题：
- 若current只有左右结点时我们删除current后应该使用左结点还是右节点来代替current的位置。
- 如果current的两个子节点下面还有结点我们应该选择哪一个结点来替代我们current的位置。
首先回答第一个问题♀ ，如果只有两个字节点时我们我们随便选左右都是可以的，因为你可以想象以下删除以后它的结构是不会改变的。
第二个问题 : 如果子节点的下面还是右子节点我们这个时候就应该找current的前驱后继结点。那么什么是前驱后继呢？
首先你可以想象一下在这些结点中你使用哪个结点替换其位置使得树结构变动最小。这里我们就用15这个结点来举例。假如我们要使用其左子树部分，那么我想没有哪个结点能比14再合适不过了。相同如果使用右子树的话18可能是最好的选择。为什么？
因为选择14刚好小于其右边分支，且大于左边的分支。18也是相反的道理。
所以我们由以上的例子可以看出前驱结点就是比current小一点点的结点，相反后继就是比其大一点点的结点。这让我想起来高数上的夹逼准则。
所以照着这个道理我们来实现以下它的代码。
我们代码实现就使用后继的方式，也就是使用右节点的方式来实现。
首先我们可能需要一个寻找后继的方法。然后再直接通过当前的状态直接删除就可以。
寻找后继的具体实现的方法（所有情况）。
BinarySerachTree.prototype.getSuccssor = function (delnode) {
// 定义变量，保存后继
var successor = delnode;
// 向右走
var current = delnode.right;
// 后继结点的父节点
var parentsuccessor=delnode;
while (current != null) {
parentsuccessor=successor;
successor = current;
current = current.left;
}
// 如果current的子节点还有子节点时
if (successor!=delnode.right) {
parentsuccessor.left=successor.right;
successor.right=delnode.right
}
return successor;
}
接着我们直接进行删除
// 第三种情况(有两个子结点时)
else {
var successor=this.getSuccssor(current);
if (current==this.root) {
this.root=successor;
}else if(isLeftChild){
parent.left=successor;
}else{
parent.right=successor;
}
// 将删除结点的左子树指向当前的左子树
successor.left=current.left
}
8.结语
到了这里我们的二叉搜索树就算是实现完成了，如果有什么不懂的地方，多看看图，再加深以下理解
这里附上源码。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
</body>
<script>
function BinarySerachTree() {
// 结点类
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
// 属性
this.root = null;
// 方法
/* 插入操作的封装 */
BinarySerachTree.prototype.insert = function (key) {
// 1.创建key结点
var newnode = new Node(key);
// 2.判断根节点是否有值
if (this.root == null) {
// 2.1 若无值则将结点赋给根节点
this.root = newnode
} else {
// 2.2 若有值则递归调用以此判断插入或继续递归
this.insertNode(this.root, newnode)
}
}
// 插入函数的递归函数
BinarySerachTree.prototype.insertNode = function (node, newnode) {
/*
判断路径方向
判断是否有值，若有值，则继续递归，若无值，则赋值
*/
if (newnode.key < node.key) {
// 如果新节点小于根节点，则向左走
if (node.left == null) {
node.left = newnode
} else {
this.insertNode(node.left, newnode)
}
} else {
// 如果新节点大于根节点，则向右走
if (node.right == null) {
node.right = newnode
} else {
this.insertNode(node.right, newnode)
}
}
}
/* 遍历方式 */
/* 先序遍历 */
BinarySerachTree.prototype.preOrderTravers = function (callback) {
this.preOrderTraversNode(this.root, callback)
}
BinarySerachTree.prototype.preOrderTraversNode = function (nownode, callback) {
if (nownode != null) {
callback(nownode.key);
// 递归调用左子树
this.preOrderTraversNode(nownode.left, callback)
// 左子树调用结束后直接右子树
this.preOrderTraversNode(nownode.right, callback)
}
}
/* 中序遍历 */
BinarySerachTree.prototype.middleOrderTravers = function (callback) {
this.middleOrderTraversNode(this.root, callback)
}
BinarySerachTree.prototype.middleOrderTraversNode = function (nownode, callback) {
if (nownode != null) {
this.middleOrderTraversNode(nownode.left, callback)
callback(nownode.key);
this.middleOrderTraversNode(nownode.right, callback)
}
}
/* 后序遍历 */
BinarySerachTree.prototype.postOrderTravers = function (callback) {
this.postOrderTraversNode(this.root, callback)
}
BinarySerachTree.prototype.postOrderTraversNode = function (nownode, callback) {
if (nownode != null) {
this.postOrderTraversNode(nownode.left, callback)
this.postOrderTraversNode(nownode.right, callback)
callback(nownode.key);
}
}
/*最大值*/
BinarySerachTree.prototype.getmaxNode = function () {
let node = this.root;
while (node.right != null) {
node = node.right
}
return node.key
}
/* 最小值 */
BinarySerachTree.prototype.getminNode = function () {
let node = this.root;
while (node.left != null) {
node = node.left
}
return node.key
}
/*搜索特定的值(递归实现)*/
BinarySerachTree.prototype.searchThekey = function (key) {
// 首先判断是否有值存在
if (this.root == null) {
return false;
}
// 递归操作
return this.searchThekeyNode(this.root, key);
}
// 搜索特定的值的递归操作
BinarySerachTree.prototype.searchThekeyNode = function (node, key) {
if (node === null) {
return false
}
if (key > node.key) {
return this.searchThekeyNode(node.right, key);
} else if (key < node.key) {
return this.searchThekeyNode(node.left, key);
} else {
return true
}
}
/*搜索特定的值(非递归实现)*/
BinarySerachTree.prototype.searchThekeybywhile = function (key) {
var node = this.root;
if (node === null) {
return false;
}
while (node != null) {
if (key > node.key) {
node = node.right
} else if (key < node.key) {
node = node.left
} else {
return true
}
}
return false
}
/* 移除节点 */
BinarySerachTree.prototype.remove = function (key) {
var current = this.root;
var parent = this.root;
var isLeftChild = true;
// 查找(有则操作current，没有则返回false)
while (current.key != key) {
parent = current;
if (key > current.key) {
isLeftChild=false
current = current.right
} else {
isLeftChild=true
current = current.left
}
if (current == null) {
return false;
}
}
// 第一种情况(只有一个叶子节点时)
if (current.left == null && current.right == null) {
if (current == this.root) {
this.root = null
} else if (isLeftChild) {
parent.left = null
} else {
parent.right = null
}
// 第二种情况(有一个子节点时)
} else if (current.left == null) {
if (current == this.root) {
this.root = current.right
} else if (isLeftChild) {
parent.left = current.right
} else {
parent.right = current.right
}
} else if (current.right == null) {
if (current == this.root) {
this.root = current.left
} else if (isLeftChild) {
parent.left = current.left
} else {
parent.right = current.left
}
}
// 第三种情况(有两个子结点时)
else {
var successor=this.getSuccssor(current);
if (current==this.root) {
this.root=successor;
}else if(isLeftChild){
parent.left=successor;
}else{
parent.right=successor;
}
// 将删除结点的左子树指向当前的左子树
successor.left=current.left
}
return true
}
BinarySerachTree.prototype.getSuccssor = function (delnode) {
// 定义变量，保存后继
var successor = delnode;
// 向右走
var current = delnode.right;
// 后继结点的父节点
var parentsuccessor=delnode;
while (current != null) {
parentsuccessor=successor;
successor = current;
current = current.left;
}
// 如果current的子节点还有子节点时
if (successor!=delnode.right) {
parentsuccessor.left=successor.right;
successor.right=delnode.right
}
return successor;
}
}
var bst = new BinarySerachTree();
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
console.log(bst);
var str = ''
bst.preOrderTravers(function (key) {
str += key + ' '
})
console.log('先序遍历', str);
var str2 = ''
bst.middleOrderTravers(function (key) {
str2 += key + ' '
})
console.log('中序遍历', str2);
var str3 = ''
bst.postOrderTravers(function (key) {
str3 += key + ' '
})
console.log('后序遍历', str3);
// 获取最大值
console.log(bst.getmaxNode());
console.log(bst.getminNode());
console.log(bst.searchThekey(23) + "结果");
console.log(bst.searchThekeybywhile(23) + "结果");
bst.remove(9);
bst.remove(7);
bst.remove(15);
var str3 = ''
bst.postOrderTravers(function (key) {
str3 += key + ' '
})
console.log('后序遍历', str3);
</script>
</html>
智能推荐
在Google使用Borg进行大规模集群的管理 7-8-程序员宅基地
文章浏览阅读606次。为什么80%的码农都做不了架构师？>>> ..._google trace batch job
python加密字符串小写字母循环后错两位_python学习：实现将字符串进行加密-程序员宅基地
文章浏览阅读2.6k次，点赞3次，收藏3次。'''题目描述1、对输入的字符串进行加解密，并输出。2加密方法为：当内容是英文字母时则用该英文字母的后一个字母替换，同时字母变换大小写,如字母a时则替换为B；字母Z时则替换为a；当内容是数字时则把该数字加1，如0替换1，1替换2，9替换0；其他字符不做变化。s'''#-*-coding:utf-8-*-importre#判断是否是字母defisLetter(letter):iflen..._编写函数fun2实现字符串加密,加密规则为:如果是字母,将其进行大小写转换;如果
【Java容器源码】集合应用总结：迭代器&批量操作&线程安全问题_迭代器是否可以保证容器删除和修改安全操作-程序员宅基地
文章浏览阅读4.4k次，点赞6次，收藏8次。下面列出了所有集合的类图：每个接口做的事情非常明确，比如 Serializable，只负责序列化，Cloneable 只负责拷贝，Map 只负责定义 Map 的接口，整个图看起来虽然接口众多，但职责都很清晰；复杂功能通过接口的继承来实现，比如 ArrayList 通过实现了 Serializable、Cloneable、RandomAccess、AbstractList、List 等接口，从而拥有了序列化、拷贝、对数组各种操作定义等各种功能；上述类图只能看见继承的关系，组合的关系还看不出来，比如说_迭代器是否可以保证容器删除和修改安全操作
养老金融：编织中国老龄社会的金色安全网
在科技金融、绿色金融、普惠金融、养老金融、数字金融这“五篇大文章”中，养老金融以其独特的社会价值和深远影响，占据着不可或缺的地位。通过政策引导与市场机制的双重驱动，激发金融机构创新养老服务产品，如推出更多针对不同年龄层、风险偏好的个性化养老金融产品，不仅能提高金融服务的可获得性，还能增强民众对养老规划的主动参与度，从而逐步建立起适应中国国情、满足人民期待的养老金融服务体系。在人口老龄化的全球趋势下，中国养老金融的发展不仅仅是经济议题，更关乎社会的稳定与进步。养老金融：民生之需，国计之重。
iOS 创建开源库时如何使用图片和xib资源
在需要使用图片的地方使用下面的代码，注意xib可以直接设置图片。将相应的图片资源文件放到bundle文件中。
R语言学习笔记9_多元统计分析介绍_r语言多元统计分析-程序员宅基地
文章浏览阅读3.6k次，点赞4次，收藏66次。目录九、多元统计分析介绍九、多元统计分析介绍_r语言多元统计分析
随便推点
基于psk和dpsk的matlab仿真,MATLAB课程设计-基于PSK和DPSK的matlab仿真-程序员宅基地
文章浏览阅读623次。MATLAB课程设计-基于PSK和DPSK的matlab仿真 (41页) 本资源提供全文预览，点击全文预览即可全文预览,如果喜欢文档就下载吧，查找使用更方便哦！9.90 积分武汉理工大学MATLAB课程设计.目录摘要 1Abstract 21.设计目的与要求 32.方案的选择 42.1调制部分 42.2解调部分 43.单元电路原理和设计 63.1PCM编码原理及设计 63.1.1PCM编码原理 ..._通信原理课程设计(基于matlab的psk,dpsk仿真)(五篇模版)
腾讯微搭小程序获取微信用户信息_微搭 用微信号登录-程序员宅基地
文章浏览阅读3.5k次，点赞6次，收藏28次。腾讯微搭小程序获取微信用户信息无论你对低代码开发的爱与恨, 微信生态的强大毋庸置疑. 因此熟悉微搭技术还是很有必要的! 在大多数应用中, 都需要获取和跟踪用户信息. 本文就微搭中如何获取和存储用户信息进行详细演示, 因为用户信息的获取和存储是应用的基础.一. 微搭每个微搭平台都宣称使用微搭平台可以简单拖拽即可生成一个应用, 这种说法我认为是"夸大其词". 其实微搭优点大致来说, 前端定义了很多组件, 为开发人员封装组件节省了大量的时间,这是其一; 其二对后端开发来说, 省去了服务器的部署(并没有省去后_微搭 用微信号登录
sql中索引的使用分析
sql中索引的使用分析
termux安装metasploit（）-程序员宅基地
文章浏览阅读8.9k次，点赞16次，收藏108次。因为呢，termux作者，不希望让termux变成脚本小子的黑客工具，于是把msf , sqlmap等包删了。至于如何安装metasploit呢。apt update -y && apt upgrade -y #更新升级更新升级之后要安装一个叫 git 的安装包apt install git -y然后我们就开始//这里的话建议把手机放到路由器旁边，保持网络的优良。或者科学上网。//git clone https://github.com/gushmazuko/metaspl_termux安装metasploit
armbian docker Chrome_一起学docker06-docker网络-程序员宅基地
文章浏览阅读141次。一、Docker支持4种网络模式Bridge(默认)--network默认网络，Docker启动后创建一个docker0网桥，默认创建的容器也是添加到这个网桥中；IP地址段是172.17.0.1/16 独立名称空间 docker0桥，虚拟网桥的工作方式和物理交换机类似，这样主机上的所有容器就通过交换机连在了一个二层网络中。host容器不会获得一个独立的network namespace，而是与宿主..._armbian 172.17.0.1
Ansible-Tower安装破解
Ansible-Tower安装破解。