在 javascript 中实现二叉搜索树
在这篇文章中，我们将探索如何在 javascript 中实现基本的二叉搜索树 (bst)。我们将介绍插入节点和执行不同的树遍历方法 - 中序、前序和后序。
节点类
首先，我们定义一个 node 类来表示树中的每个节点：
class node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
每个 node 对象都有三个属性：
- value：节点中存储的数据。
- left：指向左子节点的指针。
- right：指向右子节点的指针。
binarysearchtree 类
接下来，我们将定义一个 binarysearchtree 类，它将管理节点并提供与树交互的方法：
class binarysearchtree {
constructor() {
this.root = null;
}
isempty() {
return this.root === null;
}
insertnode(root, newnode) {
if(newnode.value < root.value) {
if(root.left === null) {
root.left = newnode;
} else {
this.insertnode(root.left, newnode);
}
} else {
if(root.right === null) {
root.right = newnode;
} else {
this.insertnode(root.right, newnode);
}
}
}
search(root, value) {
if(!root) {
return false;
}
if(root.value === value) {
return true;
} else if(root.value > value) {
return this.search(root.left, value);
} else {
return this.search(root.right, value);
}
}
insert(value) {
const newnode = new node(value);
if(this.isempty()) {
this.root = newnode;
} else {
this.insertnode(this.root, newnode);
}
}
}
关键方法：
- isempty()：检查树是否为空。
- insertnode(root, newnode)：向树中插入一个新节点，保持二叉搜索树属性。
- search(root, value)：递归搜索树中的值。
- insert(value)：一种向树中插入新值的便捷方法。
树遍历方法
立即学习“Java免费学习笔记（深入）”；
一旦我们有一棵树，我们经常需要遍历它。以下是三种常见的遍历方式：
中序遍历
中序遍历按照以下顺序访问节点：left、root、right。
inorder(root) {
if(root) {
this.inorder(root.left);
console.log(root.value);
this.inorder(root.right);
}
}
此遍历以非降序打印二叉搜索树的节点。
预购穿越
前序遍历按照以下顺序访问节点：root、left、right。
preorder(root) {
if(root) {
console.log(root.value);
this.preorder(root.left);
this.preorder(root.right);
}
}
这种遍历对于复制树结构很有用。
后序遍历
后序遍历按照以下顺序访问节点：left、right、root。
postorder(root) {
if(root) {
this.postorder(root.left);
this.postorder(root.right);
console.log(root.value);
}
}
这种遍历通常用于删除或释放节点。
用法示例
让我们看看这些方法如何协同工作：
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);
console.log('In-order Traversal:');
bst.inOrder(bst.root);
console.log('Pre-order Traversal:');
bst.preOrder(bst.root);
console.log('Post-order Traversal:');
bst.postOrder(bst.root);
结论
通过此实现，您现在可以在 javascript 中创建二叉搜索树并与之交互。理解树结构和遍历方法对于许多算法问题至关重要，尤其是在搜索算法、解析表达式和管理分层数据等领域。
