Java でツリーを実装する

Rupam Yadav 2023年10月12日

Java Java Tree Java Binary Tree

再帰メソッドを使用してツリーを実装する
Java でジェネリックメソッドと ArrayList を使用してツリーを作成する

このチュートリアルでは、Java でツリー構造を作成する 2つの方法を紹介します。ツリー構造は、フォルダやファイル名のディレクトリを作成するなど、いくつかの点で役立ちます。

再帰メソッドを使用してツリーを実装する

この例では、最大で 2つの子を持つバイナリツリーを作成します。1つは左側に、もう 1つは右側にあります。ルートノードは、すべての子ノードの親です。各ノードは値を格納します。以下では、2つのクラスを受講します。1つはツリー内のノードを表す Node であり、もう 1つはノードで操作を実行する JavaTree クラスです。

Node クラスには 3つの変数があります。最初は、int データ型のノードに格納する値です。次に、左と右の子ノードの 2つの変数を取ります。両方の変数は Node タイプです。Node クラスのコンストラクターを作成し、パラメーターから value を初期化します。左右の変数は null として設定されます。

JavaTree クラスでは、タイプ Node の変数を取り、それを root と呼びます。次に、パラメータとして Node を受け取るメソッド traverseRecursionTree() を作成し、メソッド内で、Node が null であるかどうかを確認します。そうでない場合は、それ自体から traverseRecursionTree() メソッドを呼び出し、Node の左部分を渡します。その後、Node の value を出力し、それ自体からメソッドを再度呼び出して、右``Node を渡します。関数をそれ自体から呼び出すプロセスは、再帰と呼ばれます。

main() メソッドでは、javaTree のオブジェクトを作成してから、ルート、ルートの左の子、右の子などのすべての変数を初期化します。また、根の子の左子を作ります。すべての子を含む javaTree.root を使用してツリー全体を出力します。

class Node {
  int value;
  Node left;
  Node right;

  public Node(int value) {
    this.value = value;
    left = null;
    right = null;
  }
}

public class JavaTree {
  Node root;

  public void traverseRecursionTree(Node node) {
    if (node != null) {
      traverseRecursionTree(node.left);
      System.out.print(" " + node.value);
      traverseRecursionTree(node.right);
    }
  }

  public static void main(String[] args) {
    JavaTree javaTree = new JavaTree();

    javaTree.root = new Node(10);
    javaTree.root.left = new Node(6);
    javaTree.root.right = new Node(5);
    javaTree.root.left.left = new Node(3);

    System.out.print("Binary Tree: ");

    javaTree.traverseRecursionTree(javaTree.root);
  }
}

出力：

Binary Tree:  3 6 10 5

Java でジェネリックメソッドと `ArrayList` を使用してツリーを作成する

以前の方法では、int ノードの値として 1つのタイプのデータのみに制限されていました。このプログラムでは、選択した任意のデータ型を使用できるようにする汎用メソッドを使用します。クラス Node<T> があります。ここで <T> は、任意のデータ型を文字列として使用できることを示しています。クラスでは、3つの変数を宣言します。まず、T 型の root があり、次に Node<T> 型の parent があり、最後に children という名前の Node<T> の ArrayList があります。

Node のコンストラクターでは、T タイプの root を取得し、それをクラス変数 root に設定します。次に、children ArrayList を初期化します。ここで、親に子を追加するために、タイプ T の子を受け取る addChild() 関数を作成します。addChild() 関数では、Node<T>-childNode のオブジェクトを作成し、this キーワードを使用して、その親のコンテキストを現在のクラスのコンテキストとして設定します。次に、children ArrayList を取得し、childNode を追加して、childNode を返します。

Node<T> クラスには、root を返す getRoot() メソッドのような操作を実行するために使用できる複数のメソッドがあります。isRoot() 関数は、現在のノードが root であるかどうかをチェックします。ツリー内のノードのレベルを返す getLevel() 関数を作成します。最後に、toString() メソッドをオーバーライドして、null でない場合はツリー全体を返します。

次に、main() メソッドを持つ Javatree クラスを作成します。クラスで Node<String> の x と y を作成します。ここでは、タイプとして文字列を使用します。両方のコンストラクターで、各ツリーのルートを渡します。getRoot() を使用して root を出力し、child1 という名前の Node<String> のオブジェクトを作成し、x オブジェクトを使用して addChild() メソッドを呼び出します。ここでは、の値を渡します。引数としての child1。child1 のブロックで、そのオブジェクトを使用して child1 の 3つの子を作成し、addChild() を呼び出します。

同じプロセスを使用して、child2 という名前の別のツリーを作成します。

import java.util.ArrayList;

class Node<T> {
  private final T root;
  private Node<T> parent;
  private final ArrayList<Node<T>> children;

  public Node(T root) {
    this.root = root;
    children = new ArrayList<>();
  }

  public Node<T> addChild(T child) {
    Node<T> childNode = new Node<T>(child);
    childNode.parent = this;
    this.children.add(childNode);
    return childNode;
  }

  public T getRoot() {
    return root;
  }

  public boolean isRoot() {
    return parent == null;
  }

  public boolean isLeaf() {
    return children.size() == 0;
  }

  public int getLevel() {
    if (this.isRoot())
      return 0;
    else
      return parent.getLevel() + 1;
  }

  @Override
  public String toString() {
    return root != null ? root.toString() : "null";
  }
}

public class JavaTree {
  public static void main(String[] args) {
    Node<String> x = new Node<String>("parent1");
    Node<String> y = new Node<String>("parent2");

    System.out.println(x.getRoot());

    Node<String> child1 = x.addChild("child1");
    {
      Node<String> innerChild1 = child1.addChild("innerChild1OfChild1");
      Node<String> innerChild2 = child1.addChild("innerChild2OfChild1");
      Node<String> innerChild3 = child1.addChild("innerChild3OfChild1");

      System.out.println("-" + child1);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child1.getLevel());
      System.out.println("Level of innerChild2 in Child1: " + innerChild2.getLevel());
    }

    System.out.println();

    System.out.println(y.getRoot());

    Node<String> child2 = x.addChild("child2");
    {
      Node<String> innerChild1 = child2.addChild("innerChild2OfChild2");
      Node<String> innerChild2 = child2.addChild("innerChild3OfChild2");
      Node<String> innerChild3 = child2.addChild("innerChild4OfChild2");
      {
        Node<String> innerChild4 = innerChild3.addChild("innerChild4OfChild3");
        System.out.println(innerChild4.getLevel());
        System.out.println("\nIs inner Child4 Leaf? " + innerChild4.isLeaf());
      }

      System.out.println("-" + child2);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child2.getLevel());
      System.out.println("Level of innerChild2 in Child2: " + innerChild2.getLevel());
    }
  }
}

出力：

parent1
-child1
--innerChild1OfChild1
--innerChild2OfChild1
--innerChild3OfChild1
Level of child1: 1
Level of innerChild2 in Child1: 2

parent2
3

Is inner Child4 Leaf? true
-child2
--innerChild2OfChild2
--innerChild3OfChild2
--innerChild4OfChild2
Level of child1: 1
Level of innerChild2 in Child2: 2

著者： Rupam Yadav

Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.

再帰メソッドを使用してツリーを実装する

Java でジェネリックメソッドと ArrayList を使用してツリーを作成する

関連記事 - Java Binary Tree

Java でジェネリックメソッドと `ArrayList` を使用してツリーを作成する