JavaScript实现二叉搜索树
JavaScript中的搜索二叉树实现，供大家参考，具体内容如下
二叉搜索树（BST，BinarySearchTree），也称二叉排序树或二叉查找树
二叉搜索树是一颗二叉树,可以为空；如果不为空，满足以下性质：
- 非空左子树的所有键值小于其根结点的键值
- 非空右子树的所有键值大于其根结点的键值
- 也就是左结点值想<根结点值<右节点值
- 左、右子树本身也都是二叉搜索树
二叉搜索树的操作
insert(key)：向树中插入一个新的键
search(key)：在树中查找一个键，如果结点存在，则返回true；如果不存在，则返回false
inOrderTraverse：通过中序遍历方式遍历所有结点
preOrderTraverse：通过先序遍历方式遍历所有结点
postOrderTraverse：通过后序遍历方式遍历所有结点
min：返回树中最小的值/键
max：返回树中最大的值/键
remove(key)：从树中移除某个键
先序遍历
- ①访问根结点
- ②先序遍历其左子树
- ③先序遍历其右子树
中序遍历
①中序遍历其左子树
②访问根结点
③中序遍历其右子树
后序遍历
①后序遍历其左子树
②后序遍历其右子树
③访问根结点
JavaScript代码实现队列结构
//创建BinarySearchTree
functionBinarySerachTree(){
//创建节点构造函数
functionNode(key){
this.key=key
this.left=null
this.right=null
}
//保存根的属性
this.root=null
//二叉搜索树相关的操作方法
//向树中插入数据
BinarySerachTree.prototype.insert=function(key){
//1.根据key创建对应的node
varnewNode=newNode(key)
//2.判断根节点是否有值
if(this.root===null){
this.root=newNode
}else{
this.insertNode(this.root,newNode)
}
}
BinarySerachTree.prototype.insertNode=function(node,newNode){
if(newNode.keykey){//2.1.传入的key较小,向左边继续查找
returnthis.searchNode(node.left,key)
}elseif(node.keykey){
node=node.left
}elseif(node.keykey){
parent=node
node=node.left
}elseif(node.keykey){
node.left=this.removeNode(node.left,key)
}
}
//删除结点
BinarySerachTree.prototype.remove=function(key){
//1.定义临时保存的变量
varcurrent=this.root
varparent=this.root
varisLeftChild=true
//2.开始查找节点
while(current.key!==key){
parent=current
if(key
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。