JavaScript 中的二叉搜索树

在 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)：一种向树中插入新值的便捷方法。

树遍历方法

一旦我们有一棵树，我们经常需要遍历它。以下是三种常见的遍历方法：

中序遍历

中序遍历按照以下顺序访问节点：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);
    }
}

此遍历对于复制树结构很有用。

后序遍历

后序遍历按以下顺序访问节点：左、右、根。

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 中的二叉搜索树的详细内容。更多信息请关注PHP中文网其他相关文章！