ホームページ >Java >&#&チュートリアル >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 つずつ紹介します。
順番トラバーサルでは、ツリー内のノードを小さいノードから大きいノードの順にトラバースします。 Java コードでは、順序トラバーサルの実装は再帰を使用します。各ノードに対して、最初にそれ自体の左ノードを呼び出し、次にノード データを出力し、最後にそれ自体の右ノードを呼び出します。このようにして、ツリー内のすべてのノードを小さいノードから大きいノードまで順番にたどることができます。
プレオーダー トラバーサルでは、親ノード、左ノード、右ノードの順序でツリー内のノードを走査します。 Java コードでは、事前順序トラバーサルの実装でも再帰が使用されます。つまり、各ノードに対して、最初にノード データを出力し、次にそれ自体の左ノードを呼び出し、最後にそれ自体の右ノードを呼び出します。このようにして、ツリー内のすべてのノードを親ノード、左ノード、右ノードの順序でたどることができます。
事後走査では、ツリー内のノードを左ノード、右ノード、親ノードの順序で走査します。 Java コードでは、ポストオーダー トラバーサルの実装でも再帰が使用されます。各ノードに対して、最初にそのノード自体の左ノードを呼び出し、次に独自の右ノードを呼び出し、最後にノード データを出力します。このようにして、ツリー内のすべてのノードを、左ノード、右ノード、親ノードの順序でたどることができます。
4. 一般的に使用されるバイナリ ツリー アルゴリズム
バイナリ ツリーは柔軟で非常に便利なデータ構造であり、Java プログラミングではバイナリ ツリー アルゴリズムがよく使用されます。一般的に使用されるバイナリ ツリー アルゴリズムは次のとおりです。
検索はバイナリ ツリーの最も基本的な機能の 1 つであり、頻繁に使用される機能でもあります。 Java コードでは、検索の実装は非常に簡単です。ノードごとに、ノード値とターゲット値のサイズを比較することによって、ターゲット値が見つかるまで、またはツリー全体が走査されるまで、レイヤーごとに下方向に検索します。
挿入は、バイナリ ツリーに新しいノードを追加する機能です。同時に、挿入された新しいノードもバイナリのソート順に従います。木。 Java コードでは、挿入の実装も比較的単純です。挿入されるノードと現在のノードのサイズを比較し、適切な位置が見つかったら新しいノードを挿入します。
削除は、バイナリ ツリーからノードを削除する機能です。Java コードでは、削除の実装はより複雑であり、より多くの考慮事項が必要です。削除されたノードに子ノードがない場合は、直接削除します。子ノードが 1 つしかない場合は、その子ノードを削除したノードの位置に移動します。削除されたノードに 2 つの子ノードがある場合は、最小値を見つける必要があります。右側の子ノードの値を取得し、削除されたノードの場所に置き換えます。
5. 概要
この記事では、バイナリ ツリーの定義、ノードとバイナリ ツリー クラスの実装、3 つの異なるトラバーサル メソッド、および一般的な方法を含む、Java のバイナリ ツリー データ構造を詳細に紹介します。バイナリツリーアルゴリズムを使用しました。バイナリ ツリーは広く使用されているデータ構造であり、Java はバイナリ ツリーの実装を支援する多くの関数とクラス ライブラリを提供します。 Java でプログラミングする場合、バイナリ ツリーの使用と実装に習熟すると、プログラムの効率とデータ クエリの精度が向上します。
以上がJavaのバイナリツリー構造を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。