在 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 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 中创建二叉搜索树并与之交互。理解树结构和遍历方法对于许多算法问题至关重要，尤其是在搜索算法、解析表达式和管理分层数据等领域。
以上就是JavaScript 中的二叉搜索树的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1490117.html
微信扫一扫 
支付宝扫一扫 
