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