Javaを使用して二分探索木アルゴリズムを実装する方法

Java を使用して二分探索ツリー アルゴリズムを実装する方法

二分探索ツリー (BST と呼ばれる) は、一般的に使用されるデータ構造です。挿入、削除、検索などの操作を効率的に実装できます。この記事では、Java を使用して二分探索ツリーを実装する方法を紹介し、対応するコード例を示します。

1. 二分探索ツリーの定義

二分探索ツリーは次の特徴を持つ順序付きツリーです:

1. 各ノードは一意のキー値を持ちます。
2. 左側のサブツリーのキー値はノードのキー値より小さく、右側のサブツリーのキー値はノードのキー値より大きくなります。
3. 左側のサブツリーと右側のサブツリーも二分探索ツリーです。

2. 二分探索木のノード クラスの実装

まず、キー値と左と左の参照を含む二分探索木のノード クラスを定義します。右側の子ノード。コードは次のとおりです。

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

このノード クラスでは、data フィールド、left および を通じてノードのキー値を保存します。 right フィールドはそれぞれ保存され、左と右の子ノードへの参照。

3. 二分探索木の挿入演算の実装

次に、二分探索木の挿入演算を実装します。挿入操作では、ノードのキー値の大きさを比較してノードの挿入位置を決定し、キー値が現在のノードより小さい場合は左側のサブツリーに挿入し、そうでない場合は右側のサブツリーに挿入します。

class BinarySearchTree {
    Node root;

    // 插入操作
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        // 如果树为空，创建一个新的节点
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // 否则，递归地插入节点到左子树或右子树
        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);

        return root;
    }
}

挿入操作では、まずツリーが空かどうかを判断し、空の場合はルート ノードとして新しいノードを作成します。それ以外の場合は、キー値と現在のノードの大小関係を比較して、左のサブツリーまたは右のサブツリーに再帰的に挿入します。

4. 二分探索木の検索操作の実装

二分探索木の検索操作は比較的単純で、キー値とノードの大小関係を段階的に比較するだけです。一致または遭遇が見つかるまで、空のノードが見つかるまで。コードは次のとおりです。

class BinarySearchTree {
    ...

    // 查找操作
    public boolean contains(int key) {
        return containsRec(root, key);
    }

    private boolean containsRec(Node root, int key) {
        // 树为空或者找到匹配节点
        if (root == null || root.data == key)
            return (root != null);

        // 比较键值与当前节点
        if (key < root.data)
            return containsRec(root.left, key);
        else
            return containsRec(root.right, key);
    }
}

検索操作では、まずツリーが空かどうか、または現在のノードが一致するかどうかを判断します。一致する場合は true を返し、一致しない場合は、キー値のサイズと現在のノードを比較して、左または右のサブツリーを再帰的に検索します。

5. 二分探索ツリーをテストするコード

最後に、実装した二分探索ツリーをテストするコードを作成します。コードは次のとおりです:

public class Main {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println(tree.contains(30));
        System.out.println(tree.contains(90));
    }
}

実行結果は次のとおりです:

true
false

ここでは、挿入操作を呼び出して、いくつかのノードをツリーに挿入します。次に、検索操作を呼び出して、キー値 30 と 90 を持つノードをそれぞれ検索します。返される結果は、挿入操作が成功したかどうかです。

上記の手順により、Java を使用して二分探索ツリー アルゴリズムを実装し、挿入と検索操作を実装することができました。実際のアプリケーションでは、二分探索ツリーは、削除操作、事前順序、順序内および順序後の走査などの機能もサポートできます。読者は、特定のニーズに応じて実装をさらに拡張できます。

以上がJavaを使用して二分探索木アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。