JavaScript 中的二叉搜索树

百变鹏仔 3天前 #JavaScript

文章标签 JavaScript

在 javascript 中实现二叉搜索树

在这篇文章中，我们将探索如何在 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 中创建二叉搜索树并与之交互。理解树结构和遍历方法对于许多算法问题至关重要，尤其是在搜索算法、解析表达式和管理分层数据等领域。

文章推荐

JavaScript 中的二叉搜索树

在 javascript 中实现二叉搜索树

JavaScript如何获取宏控件数据？

JavaScript怎样读取宏控件数据？

JavaScript获取宏控件数据的技巧

探究JavaScript与Java的联系和区别

javascript:void(o)如何解决？