Javascriptの二分探索木

JavaScript での二分探索ツリーの実装

この投稿では、JavaScript で基本的な二分探索ツリー (BST) を実装する方法を検討します。ノードの挿入と、順序、事前順序、事後順序などのさまざまなツリー走査方法の実行について説明します。

ノードクラス
まず、ツリー内の各ノードを表す Node クラスを定義しましょう:

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

各 Node オブジェクトには 3 つのプロパティがあります:

• 値: ノードに保存されているデータ。
• 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): ツリーに新しい値を挿入する便利なメソッドです。

ツリートラバーサルメソッド

ツリーを作成したら、多くの場合、それを横断する必要があります。以下に 3 つの一般的な走査方法を示します:

順番トラバーサル

インオーダートラバーサルは、左、ルート、右の順序でノードを訪問します。

inOrder(root) {
    if(root) {
        this.inOrder(root.left);
        console.log(root.value);
        this.inOrder(root.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 中国語 Web サイトの他の関連記事を参照してください。