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中文網其他相關文章！