Java | ツリー構造を「再帰」で処理する

Java Java
スポンサーリンク

Javaのツリー構造を「再帰」で処理するという発想（前半）

ツリー構造を扱うとき、再帰はほとんど「チート級」に相性が良いテクニックです。 フォルダ階層、メニュー構造、組織図、DOMツリー、JSONのネストなど、 現実世界の「階層」をコードで扱う場面はすべてツリー構造とみなせます。

前半では、 ツリー構造をどうJavaで表現するか なぜ再帰がツリーと相性抜群なのか 「全部をたどる」「集計する」といった基本処理を再帰で書く方法 を、初心者向けにかみ砕いて整理していきます。 後半では、より複雑な処理や安全性・パフォーマンスの観点まで踏み込みます。

ツリー構造をJavaでどう表現するか

まず、「ツリーをどうクラスで表すか」をはっきりさせます。 最もシンプルな形は「ノードが自分の子ノードの一覧を持つ」クラスです。

import java.util.ArrayList;
import java.util.List;

class Node {
    String name;
    List<Node> children = new ArrayList<>();

    Node(String name) {
        this.name = name;
    }

    void addChild(Node child) {
        children.add(child);
    }
}
Java

この Node クラスのポイントは、 自分自身の情報（ここでは name）と、 自分の子たちを表す children を持っていることです。

この形を使うと、フォルダ階層のようなツリーを簡単に作れます。

Node root = new Node("root");
Node docs = new Node("docs");
Node images = new Node("images");
root.addChild(docs);
root.addChild(images);

Node work = new Node("work");
Node privateDocs = new Node("private");
docs.addChild(work);
docs.addChild(privateDocs);
Java

これで、

  • root
    • docs
      • work
      • private
    • images

というツリーができあがります。

重要なのは、「どのノードも同じ Node 型」であり、 どこを切り取っても「それ自体がツリーになっている」ということです。 この「部分も全体も同じ形」という性質が、再帰と抜群に相性が良い理由です。

再帰とは何かをツリーの文脈で理解する

再帰は「メソッドが自分自身を呼び出す」書き方です。 ツリー構造では、 「親ノードに対してやりたい処理は、子ノードにも同じようにやりたい」 という場面が非常に多くあります。

例えば、「ツリーの全ノードの名前を表示したい」とします。 root を表示して、 その子（docs, images）も表示して、 さらにその子（work, private）も表示して… というように、階層を下に向かってたどっていく必要があります。

この「親にも子にも同じ処理をしたい」という構造が、 再帰の得意分野です。

再帰の基本構造は次の二つです。

  1. 終了条件（これ以上深く行かない条件）
  2. 「少し小さくした問題」を自分自身に渡す

ツリーの場合、 「子がいないノード（葉）に来たら終わり」 「子に対して同じ処理をする」 という形で、この二つが自然に現れます。

例題1：ツリーの全ノードを再帰でたどって表示する

先ほどの Node クラスを使って、 「ツリーの全ノードの名前を表示する」処理を再帰で書いてみます。

public class TreePrintExample {

    public static void printTree(Node node) {
        System.out.println(node.name);

        for (Node child : node.children) {
            printTree(child); // 子に対して同じ処理をする
        }
    }

    public static void main(String[] args) {
        Node root = new Node("root");
        Node docs = new Node("docs");
        Node images = new Node("images");
        root.addChild(docs);
        root.addChild(images);

        Node work = new Node("work");
        Node privateDocs = new Node("private");
        docs.addChild(work);
        docs.addChild(privateDocs);

        printTree(root);
    }
}
Java

この printTree メソッドの動きを丁寧に追ってみます。

まず、渡された node の name を表示します。 次に、その node.children をすべてループし、 各 child に対して printTree(child) を呼びます。

ここで重要なのは、 「親ノードに対してやっていること（名前を表示して、子に同じことをさせる）」を そのまま子ノードにも繰り返している点です。

葉ノード（子がいないノード）に来たとき、 children は空なので、for ループは一度も回らず、 そのままメソッドが終わります。

これが、ツリーにおける「終了条件」です。 特別な if を書かなくても、 「子がいないなら何もしない」という自然な形で終了条件が実現されています。

再帰がツリーと相性抜群な理由をもう一歩深く見る

この例から分かるように、 ツリー構造では「親も子も同じ形をしている」ため、 「親に対してやりたい処理は、子にも同じようにやりたい」 という状況が自然に生まれます。

再帰はまさに、 「同じ処理を、少し小さくした対象に対して繰り返す」 ための仕組みです。

ツリーを「部分木」に分解して考えると、 どの部分木も「あるノードを根とし、その子たちがぶら下がっている」 という同じ構造をしています。

再帰は、 「この部分木に対して処理をする」 というメソッドを定義し、 その中で「子の部分木に対しても同じメソッドを呼ぶ」 という形で、ツリー全体を自然にたどることができます。

この「部分木」という考え方が、 ツリーと再帰を結びつけるキーワードです。

例題2：ツリーのノード数を再帰で数える

次に、「ツリーのノード数を数える」処理を再帰で書いてみます。 これは、ツリーのサイズを知りたいときの基本的な処理です。

public class TreeCountExample {

    public static int countNodes(Node node) {
        int count = 1; // 自分自身を1として数える

        for (Node child : node.children) {
            count += countNodes(child); // 子のノード数を足す
        }

        return count;
    }

    public static void main(String[] args) {
        Node root = new Node("root");
        Node docs = new Node("docs");
        Node images = new Node("images");
        root.addChild(docs);
        root.addChild(images);

        Node work = new Node("work");
        Node privateDocs = new Node("private");
        docs.addChild(work);
        docs.addChild(privateDocs);

        int total = countNodes(root);
        System.out.println("Total nodes: " + total); // 5
    }
}
Java

この countNodes メソッドの構造は、 先ほどの printTree とほぼ同じです。

違いは、「表示する」のではなく「数える」ことです。

まず、自分自身を 1 として数えます。 次に、すべての子 child に対して countNodes(child) を呼び、 その結果を count に足していきます。

葉ノードに来たとき、 children は空なので、 count は 1 のまま返されます。

親ノードは、 「自分自身の 1」と「子のノード数の合計」を足し合わせることで、 自分を根とする部分木のノード数を知ることができます。

この構造は、木DP（Tree Dynamic Programming）の基本パターンにもつながります。 「部分木ごとに何かを集計する」という処理は、 ほとんどこの形で書けます。

再帰の「終了条件」と「進み方」をツリーで意識する

ツリーを再帰で処理するときに、 必ず意識したいのが「終了条件」と「進み方」です。

終了条件は、「これ以上子がいないとき」です。 葉ノードに来たとき、 children が空であれば、 そのノードに対する処理をして終わりです。

進み方は、「子に対して同じ処理をする」ことです。 親ノードでやっていることを、 そのまま子ノードにも繰り返します。

この二つを意識してコードを読むと、 再帰が「魔法」ではなく「自然な繰り返し」に見えてきます。

ツリーの再帰処理は、 「自分の仕事をして、子にも同じ仕事を頼む」 というイメージで捉えると、 ぐっと理解しやすくなります。

前半のまとめと後半への橋渡し

前半では、Javaのツリー構造を再帰で処理するための土台として

ツリー構造を Node クラスと children で表現する基本形 ツリーが「部分も全体も同じ形」をしていること 再帰が「親にも子にも同じ処理をしたい」構造と相性抜群であること ツリーの全ノードを表示する再帰処理 ツリーのノード数を数える再帰処理 終了条件（葉ノード）と進み方（子に同じ処理をする）の意識

を整理しました。

後半では、ここから一歩進んで

深さや高さの計算 条件付きでノードをフィルタする処理 再帰のスタック・安全性・パフォーマンスの注意点 非再帰（スタック利用）との比較 実務でツリー再帰が登場する具体的な場面

を、さらに具体的なコードとともに深掘りしていきます。

次へ
12
スポンサーリンク
タイトルとURLをコピーしました