数据结构之二叉搜索树（BST）--JavaScript实现
2024-09-03 21:23:36
原理：
叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).
JavaScript实现：
var BinarySearchTree = function(){
this.root = null;
}
BinarySearchTree.prototype = {
insert: function(key){//插入
var newNode = new this.Node(key);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode)
}
console.log(this.root)
},
inOrderTraverse: function(callback){//中序查找
this.inOrderTraverseNode(this.root, callback);
},
preOrderTraverse: function(callback){//先序查找
this.preOrderTraverseNode(this.root, callback);
},
postOrderTraverse: function(callback){//后序查找
this.postOrderTraverseNode(this.root, callback);
},
min: function(){//最小值
return this.minNode(this.root)
},
max: function(){//最大值
return this.maxNode(this.root)
},
search: function(key){//查找
this.searchNode(this.root, key)
},
remove: function(key){//移除树节点
this.removeNode(this.root, key)
},
Node: function(key){
this.key = key;
this.left = null;
this.right = null;
},
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)
}
}
},
inOrderTraverseNode: function(node, callback){
if(node !== null){
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback);
}
},
preOrderTraverseNode: function(node, callback){
if(node !== null){
callback(node.key);
this.preOrderTraverseNode(node.left, callback);
this.preOrderTraverseNode(node.right, callback);
}
},
postOrderTraverseNode: function(node, callback){
if(node !== null){
this.postOrderTraverseNode(node.left, callback);
this.postOrderTraverseNode(node.right, callback);
callback(node.key);
}
},
minNode: function(node){
if(node){
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
},
maxNode: function(node){
if(node){
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
return null;
},
searchNode: function(node, key){
if(node === null)
return false;
if(key < node.key){
return this.searchNode(node.left, key);
}else if(key > node.key){
return this.searchNode(node.right, key);
}else{
return true;
}
},
removeNode(node, key){
if(node === null)
return null;
if(key < node.key){
node.left = this.removeNode(node.left, key);
return node;
}else if(key > node.key){
node.right = this.removeNode(node.right, key);
return node;
}else{
if(node.left === null && node.right === null){
node = null;
return node;
}else if(node.left === null){
node = node.right;
return node;
}else if(node.right === null){
node = node.left;
return node;
}
var aux = this.findMinNode(node.right);
node.key = aux.key;
node.right = this.removeNode(node.right, aux.key);
return node;
}
},
findMinNode: function(node){
if(node){
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
}
}
最新文章
- Logcat使用总结
- java中遍历map的两种方式
- nodejs中exports与module.exports的区别
- 面对对象之@classmethod、@staticmethod用法
- iOS autolayout 代码，自定义间距
- 状态开关按钮(ToggleButton)和开关(Switch)
- 关于mysql数据库行级锁的使用(一)
- VHDL 学习
- spring3.0+Atomikos 构建jta的分布式事务 -- NO
- JAVA·多线程：线程优先级
- rapid js framework
- VS2013编译OpenSSL
- mysql导出多个表数据为excel方法,substring函数查询
- Swift 版本历史记录（关注）
- 第12章 MySQL高级管理
- IPv6 VS IPv4，谈谈升级 IPv6 的必要性
- tornado框架设置
- Java之word导出下载
- Ch03 数组相关操作 - 练习
- mtr
热门文章
- Ubuntu16.04安装完成后首先更换源地址，加速下载
- linux下解决vim打开文件乱码现象
- <WP8开发学习笔记>ApplicationBar（任务栏）的切换以及“黑条问题”
- [转] 图解单片机下载程序电路原理之USB转串口线、CH340、PL2303、MAX232芯片的使用
- Android学习笔记数组资源文件
- 一篇文章教会你使用Python定时抓取微博评论
- 使用addEventListener绑定事件是关于this和event记录
- Andrew Ng - 深度学习工程师 - Part 1. 神经网络和深度学习（Week 2. 神经网络基础）
- swiper 实现滑动解锁
- js银行卡四个数字一个空格