Javaを使用して二分探索木アルゴリズムを実装する方法-＆＃＆チュートリアル-php.cn

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

WBOY

リリース： 2023-09-19 08:48:11

オリジナル

1162 人が閲覧しました

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

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

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

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

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

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

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));
    }
}

ログイン後にコピー

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