Javaのバイナリツリー構造を詳しく解説

バイナリ ツリーは、コンピュータ サイエンスにおける一般的なデータ構造であり、Java プログラミングでも一般的に使用されるデータ構造です。この記事ではJavaのバイナリツリー構造について詳しく紹介します。

1. 二分木とは何ですか?

コンピュータ サイエンスにおけるバイナリ ツリーは、各ノードが最大 2 つの子ノードを持つツリー構造です。このうち、左側の子ノードは親ノードより小さく、右側の子ノードは親ノードより大きい。 Java プログラミングでは、ソート、検索、およびデータ クエリの効率向上を表すためにバイナリ ツリーが一般的に使用されます。

2. Java でのバイナリ ツリーの実装

Java では、バイナリ ツリーの実装には通常、ノード クラス (Node Class) とバイナリ ツリー クラス (Binary Tree Class) が使用されます。ノード クラスはバイナリ ツリー内の各ノードを表し、データを格納するためのバイトと属性を持つことができます。二分木クラスは二分木のデータ構造全体を表し、ノードの挿入、ノードの削除、トラバースなどの機能を持ちます。以下は、単純な Java バイナリ ツリーの実装です。

public class Node {
    int key;
    String value;
    Node leftChild, rightChild;

    public Node(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

public class BinaryTree {
    Node root;

    public void insert(int key, String value) {
        Node newNode = new Node(key, value);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            while (true) {
                if (key < current.key) {
                    if (current.leftChild == null) {
                        current.leftChild = newNode;
                        return;
                    }
                    current = current.leftChild;
                } else {
                    if (current.rightChild == null) {
                        current.rightChild = newNode;
                        return;
                    }
                    current = current.rightChild;
                }
            }
        }
    }

    public Node find(int key) {
        Node current = root;
        while (current.key != key) {
            if (key < current.key) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    public void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(node.key + ": " + node.value);
            inOrderTraversal(node.rightChild);
        }
    }

    public void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.println(node.key + ": " + node.value);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }
    }

    public void postOrderTraversal(Node node) {
        if (node != null) {
            postOrderTraversal(node.leftChild);
            postOrderTraversal(node.rightChild);
            System.out.println(node.key + ": " + node.value);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.insert(50, "John");
        tree.insert(25, "Alice");
        tree.insert(75, "Bob");
        tree.insert(15, "Chris");
        tree.insert(33, "Diana");
        tree.insert(60, "Emily");
        tree.insert(90, "Fred");

        Node node = tree.find(33);
        System.out.println("Find key: " + node.key + ", value: " + node.value);

        System.out.println("In-order traversal:");
        tree.inOrderTraversal(tree.root);

        System.out.println("Pre-order traversal:");
        tree.preOrderTraversal(tree.root);

        System.out.println("Post-order traversal:");
        tree.postOrderTraversal(tree.root);
    }
}

上記のバイナリ ツリー コードには、ノードの挿入、ノードの検索、および 3 つの異なるトラバーサル メソッドという 3 つの主要な機能が含まれています。挿入ノードは while ループを使用してバイナリ ツリーの順序でデータを挿入します。検索ノードは while ループを使用してツリーを走査してターゲット データを検索します。3 つの走査メソッドはすべて再帰的に実装されます。

3. バイナリ ツリー トラバーサル メソッド

上記の Java コードでは、プログラムは 3 つの異なるバイナリ ツリー トラバーサル メソッド (順序トラバーサル、プレオーダー トラバーサル、ポストオーダー トラバーサル) を実装しています。このセクションでは、これら 3 つの走査方法を 1 つずつ紹介します。

1. 順番トラバーサル

順番トラバーサルでは、ツリー内のノードを小さいノードから大きいノードの順にトラバースします。 Java コードでは、順序トラバーサルの実装は再帰を使用します。各ノードに対して、最初にそれ自体の左ノードを呼び出し、次にノード データを出力し、最後にそれ自体の右ノードを呼び出します。このようにして、ツリー内のすべてのノードを小さいノードから大きいノードまで順番にたどることができます。

2. プレオーダー トラバーサル

プレオーダー トラバーサルでは、親ノード、左ノード、右ノードの順序でツリー内のノードを走査します。 Java コードでは、事前順序トラバーサルの実装でも再帰が使用されます。つまり、各ノードに対して、最初にノード データを出力し、次にそれ自体の左ノードを呼び出し、最後にそれ自体の右ノードを呼び出します。このようにして、ツリー内のすべてのノードを親ノード、左ノード、右ノードの順序でたどることができます。

3. 事後走査

事後走査では、ツリー内のノードを左ノード、右ノード、親ノードの順序で走査します。 Java コードでは、ポストオーダー トラバーサルの実装でも再帰が使用されます。各ノードに対して、最初にそのノード自体の左ノードを呼び出し、次に独自の右ノードを呼び出し、最後にノード データを出力します。このようにして、ツリー内のすべてのノードを、左ノード、右ノード、親ノードの順序でたどることができます。

4. 一般的に使用されるバイナリ ツリー アルゴリズム

バイナリ ツリーは柔軟で非常に便利なデータ構造であり、Java プログラミングではバイナリ ツリー アルゴリズムがよく使用されます。一般的に使用されるバイナリ ツリー アルゴリズムは次のとおりです。

1. Search

検索はバイナリ ツリーの最も基本的な機能の 1 つであり、頻繁に使用される機能でもあります。 Java コードでは、検索の実装は非常に簡単です。ノードごとに、ノード値とターゲット値のサイズを比較することによって、ターゲット値が見つかるまで、またはツリー全体が走査されるまで、レイヤーごとに下方向に検索します。

2. 挿入

挿入は、バイナリ ツリーに新しいノードを追加する機能です。同時に、挿入された新しいノードもバイナリのソート順に従います。木。 Java コードでは、挿入の実装も比較的単純です。挿入されるノードと現在のノードのサイズを比較し、適切な位置が見つかったら新しいノードを挿入します。

3. 削除

削除は、バイナリ ツリーからノードを削除する機能です。Java コードでは、削除の実装はより複雑であり、より多くの考慮事項が必要です。削除されたノードに子ノードがない場合は、直接削除します。子ノードが 1 つしかない場合は、その子ノードを削除したノードの位置に移動します。削除されたノードに 2 つの子ノードがある場合は、最小値を見つける必要があります。右側の子ノードの値を取得し、削除されたノードの場所に置き換えます。

5. 概要

この記事では、バイナリ ツリーの定義、ノードとバイナリ ツリー クラスの実装、3 つの異なるトラバーサル メソッド、および一般的な方法を含む、Java のバイナリ ツリー データ構造を詳細に紹介します。バイナリツリーアルゴリズムを使用しました。バイナリ ツリーは広く使用されているデータ構造であり、Java はバイナリ ツリーの実装を支援する多くの関数とクラス ライブラリを提供します。 Java でプログラミングする場合、バイナリ ツリーの使用と実装に習熟すると、プログラムの効率とデータ クエリの精度が向上します。

以上がJavaのバイナリツリー構造を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。