js实现二叉查找树
2024-10-08 15:54:36
二叉树的特点：
像一颗树一样，从顶端往下延伸，最顶端的为根节点，每个节点下面子节点的数不超过两个，没有任何子节点的节点被称为叶子节点， 除了根节点和叶子节点的被称为中间节点。
二叉查找树：
每个节点的左子节点比 自身的值小， 又子节点比自身的值大。
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinaryTree{
constructor() {
this.root = null;
}
insert(key) { // 插入数据
var newNode = new Node(key);
if (this.root == null) {
this.root = newNode;
} else {
var current = this.root;
while( true) {
if (key < current.key) {
if (current.left) {
current = current.left;
} else {
current.left = newNode;
break;
}
} else if (key > current.key) {
if (current.right) {
current = current.right;
} else {
current.right = newNode;
break;
}
}
}
}
}
centerSort(node,arr = []) { // 中序排列
if (node) {
this.centerSort(node.left, arr);
arr.push(node.key);
this.centerSort(node.right,arr);
}
return arr;
}
prevSort(node, arr= []) { // 前序排列
if (node) {
arr.push(node.key);
this.prevSort(node.left, arr);
this.prevSort(node.right, arr);
}
return arr;
}
nextSort(node, arr = []) { // 后续排列
if (node) {
this.nextSort(node.left, arr);
this.nextSort(node.right, arr);
arr.push(node.key);
}
return arr;
}
getMin(node) { // 获取二叉树的最小值
node = node || this.root;
while (node.left != null) {
node = node.left;
}
return node.key;
}
getMax(node) { //获取二叉树最大值
node = node || this.root;
while (node.right != null) {
node = node.right;
}
return node.key;
}
find(key) { // 查找 给定的值
var node = this.root;
while ( node != null) {
if (key < node.key) {
node = node.left;
} else if (key > node.key) {
node = node.right;
} else {
return node;
}
}
return null;
}
remove(key) { // 删除给定的值
this.root = this.removeNode(this.root, key);
}
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) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
var minNode = this.getMin(node.right);
node.key = minNode.key;
node.count = minNode.count;
node.right = this.removeNode(node.right, minNode.key);
return node;
}
}
}
}
最新文章
- Kafka简介
- 【CC评网】2013.第38周 要阅读 要有好工具
- 【故障处理】ORA-12162: TNS:net service name is incorrectly specified
- Item2 + zsh
- 【整理】Visual Studio快捷键
- Sql2008中使用DataTable作为存储过程的参数
- Qt for Windows：Qt 5.4.0 MinGW 静态编译版本制作 (转)
- Ajax中参数带有html格式的 传入后台保存【二】
- C#字典转换成where条件
- 如何编写轻量级 CSS 框架
- 关于HTML应用中的实操细节
- 安装PyCharm开发工具
- IDEA永久激活方法
- tomcat 启动时遇到org.apache.jasper.servlet.TldScanner.scanJars At least one JAR was scanned for TLDs yet contained no TLDs
- Golang两种执行流程以及区别
- 【大数据系列】FileSystem Shell官方文档翻译
- 编码gbk ajax的提交
- win32调试工具原理OutputDebugString以及如何获取输出信息
- 理解Java中字符流与字节流
- 【学习】JennyHui学英语 - 生词积累