在这篇文章中，我们将探索如何在 javascript 中实现基本的二叉搜索树 (bst)。我们将介绍插入节点和执行不同的树遍历方法 - 中序、前序和后序。
节点类
首先，我们定义一个 node 类来表示树中的每个节点：
class node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
每个 node 对象都有三个属性：
binarysearchtree 类
接下来，我们将定义一个 binarysearchtree 类，它将管理节点并提供与树交互的方法：
class binarysearchtree {
constructor() {
this.root = null;
}
isempty() {
return this.root === null;
}
insertnode(root, newnode) {
if(newnode.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);
}
}
}
关键方法：
树遍历方法
立即学习“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 中创建二叉搜索树并与之交互。理解树结构和遍历方法对于许多算法问题至关重要，尤其是在搜索算法、解析表达式和管理分层数据等领域。