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

Java Java
スポンサーリンク

Javaのツリー構造を再帰で処理する（後半）

前半では、 ツリー構造を Node クラスで表現する基本形 「全部をたどる」「ノード数を数える」といった処理を再帰で書く流れ 親にも子にも同じ処理をする、という再帰の本質 を整理しました。

後半では、そこから一歩進んで、 深さ・高さの計算、条件付きフィルタ、 再帰のスタックと安全性、 そして非再帰との比較まで含めて、 「実務で使えるツリー再帰」をもう少し本格的に掘り下げていきます。

ツリーの「深さ」と「高さ」を再帰で計算する

ツリーを扱うとき、よく登場するのが「深さ」と「高さ」です。 深さは「根からそのノードまでの距離」、 高さは「そのノードから一番深い葉までの距離」です。

深さは「上から下へ」、 高さは「下から上へ」 というイメージで捉えると分かりやすくなります。

深さを再帰で計算する

深さは、「親の深さに 1 を足す」ことで求められます。 根の深さを 0 として、子に向かって深さを伝えていく形です。

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

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

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

public class TreeDepth {

    public static void setDepth(Node node, int d) {
        node.depth = d;

        for (Node child : node.children) {
            setDepth(child, d + 1);
        }
    }

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

        setDepth(root, 0);

        System.out.println(root.name + " depth = " + root.depth);          // 0
        System.out.println(docs.name + " depth = " + docs.depth);          // 1
        System.out.println(work.name + " depth = " + work.depth);          // 2
    }
}
Java

ここで重要なのは、「情報が上から下へ流れている」ということです。 setDepth は、親から子へ「深さ d」を渡しながら進みます。 このように、「親から子へ伝えたい情報」があるとき、 再帰は非常に自然な形になります。

高さを再帰で計算する

高さは逆に、「子から親へ情報を集める」形になります。 葉の高さを 0 とし、 親の高さを「子の高さの最大値 + 1」として計算します。

class NodeH {
    String name;
    List<NodeH> children = new ArrayList<>();
    int height;

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

    void addChild(NodeH child) {
        children.add(child);
    }
}

public class TreeHeight {

    public static int computeHeight(NodeH node) {
        if (node.children.isEmpty()) {
            node.height = 0;
            return 0;
        }

        int maxChildHeight = 0;
        for (NodeH child : node.children) {
            int h = computeHeight(child);
            if (h > maxChildHeight) {
                maxChildHeight = h;
            }
        }

        node.height = maxChildHeight + 1;
        return node.height;
    }

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

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

        computeHeight(root);

        System.out.println(root.name + " height = " + root.height);        // 2
        System.out.println(docs.name + " height = " + docs.height);        // 1
        System.out.println(images.name + " height = " + images.height);    // 0
    }
}
Java

ここでは、「情報が下から上へ集まっている」ことがポイントです。 子の高さを先に計算し、それを使って親の高さを決めています。

深さと高さは、 「情報の流れの向き」が逆になっているだけで、 どちらも再帰と非常に相性が良い構造です。

条件付きでノードをフィルタする再帰処理

ツリーを実務で扱うとき、 「特定の条件を満たすノードだけを数えたい・集めたい」 という場面がよくあります。

例えば、 「名前に ‘work’ を含むノードだけを数えたい」 「特定の権限を持つノードだけを抽出したい」 といったケースです。

条件付きカウントの例

次のコードは、「名前に ‘w’ を含むノードの数」を数える例です。

public class TreeFilterCount {

    public static int countNodesWithW(Node node) {
        int count = 0;

        if (node.name.contains("w")) {
            count++;
        }

        for (Node child : node.children) {
            count += countNodesWithW(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 result = countNodesWithW(root);
        System.out.println("nodes containing 'w': " + result); // "root", "work" → 2
    }
}
Java

この処理の構造は、 「自分に対して条件をチェックし、 子にも同じ処理をさせて結果を足し合わせる」 という形になっています。

条件が変わっても、 このパターンはほぼそのまま使えます。 条件付きフィルタや集計は、 ツリー再帰の典型的な応用です。

再帰のスタックと安全性を意識する

ここからは、再帰を「安全に使う」という視点を少し深掘りします。 ツリー再帰は美しく書けますが、 スタックの深さや入力の形によっては危険になることがあります。

スタックの深さと StackOverflowError

Javaの再帰は、呼び出しごとに「コールスタック」を消費します。 ツリーが非常に深い場合、 例えば「1万階層の一本鎖」のような構造だと、 再帰の深さも 1万になり、 StackOverflowError が発生する可能性があります。

攻撃者が外部入力として「極端に深いツリー」を送ってくると、 再帰処理がスタックを枯渇させ、 サービスが落ちることもあり得ます。

そのため、実務では次のような対策が重要になります。

ツリーの深さに上限を設ける 入力を検証し、異常に深い構造を拒否する 必要に応じて再帰ではなく「自前のスタック」を使った非再帰実装に切り替える

再帰は「読みやすさ」と「自然さ」に優れますが、 「どこまで深く潜るか」を制御しないと、 セキュリティリスクにもなり得ます。

無限再帰を防ぐ構造

ツリーは通常「親から子へ一方向」なので、 無限ループになりにくい構造です。

しかし、もし誤って「親を子に再度ぶら下げる」ようなコードを書いてしまうと、 ツリーではなく「循環グラフ」になり、 再帰が終わらなくなる可能性があります。

例えば、 child.addChild(parent); のようなコードが紛れ込むと、 親と子が互いに参照し合う構造になり、 printTree のような再帰が永遠に続いてしまいます。

そのため、 ツリー構造を設計するときは 「循環が入り込まないようにする」 という前提をきちんと守ることが重要です。

非再帰（スタック利用）との比較

再帰はツリーと相性抜群ですが、 スタックの制約や安全性を考えると、 「自前のスタックを使った非再帰実装」を知っておくことも価値があります。

非再帰でツリーをたどる例

次のコードは、 Stack<Node> を使ってツリーを非再帰でたどる例です。

import java.util.Stack;

public class TreeIterative {

    public static void printTreeIterative(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.println(node.name);

            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children.get(i));
            }
        }
    }

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

        printTreeIterative(root);
    }
}
Java

ここでは、 「再帰の代わりに自分でスタックを持つ」ことで、 処理の流れを明示的に制御しています。

この方法は、 スタックの深さを自分で管理したいときや、 再帰が禁止されている環境でツリーを扱いたいときに有効です。

再帰と非再帰のどちらを選ぶかは、 読みやすさ・安全性・環境の制約を踏まえて判断することになります。

実務でツリー再帰が登場する場面

ツリー再帰は、競技プログラミングだけの話ではありません。 実務でも、次のような場面で頻繁に登場します。

フォルダ階層のサイズ集計 メニュー構造の表示制御（特定条件で非表示にするなど） 組織図の人数集計や最大階層の計算 JSONやXMLのネスト構造の解析 権限の伝播の解析（どのノードまで権限が届くか）

こうした場面で、 「親にも子にも同じ処理をしたい」 「部分木ごとに何かを集計したい」 というニーズが出てきたとき、 ツリー再帰のパターンがそのまま役立ちます。

再帰を「怖いもの」ではなく、 「階層構造を自然に扱うための道具」として捉えられると、 設計の幅が一気に広がります。

後半のまとめ

後半では、Javaのツリー構造を再帰で処理するテーマを一段深く理解するために

深さ（根からの距離）を親から子へ伝える再帰 高さ（葉までの距離）を子から親へ集める再帰 条件付きでノードをフィルタ・カウントする再帰処理 スタックの深さと StackOverflowError のリスク 循環構造による無限再帰の危険性 自前のスタックを使った非再帰実装との比較 実務でツリー再帰が登場する具体的な場面

を整理しました。

ツリー構造と再帰をセットで理解できると、 フォルダ階層から権限構造、設定ツリーまで、 「階層を持つデータ」を自分の手で自在に扱えるようになります。

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