Java | ツリー構造の探索アルゴリズム

Java Java
スポンサーリンク

Javaで学ぶ「ツリー構造の探索アルゴリズム」（前半）

ツリー構造は、プログラミングの世界で非常に重要なデータ構造です。 フォルダ階層、組織図、JSON、DOM、抽象構文木など、現場で触れるものの多くがツリーとして表現できます。 前半では、ツリーとは何か、Javaでどう表現するか、そして基本的な探索アルゴリズムである「深さ優先探索（DFS）」を中心に、初心者向けにかみ砕いて解説していきます。 後半では、幅優先探索（BFS）や応用的な探索、セキュリティ・パフォーマンスの観点まで踏み込みます。

ツリー構造とは何か（イメージを固める）

ツリー構造は、「親」と「子」の関係を持つノードが階層的につながったデータ構造です。 一番上に「根（root）」があり、その下に子ノードがぶら下がり、さらにその子が孫を持つ――という入れ子の形をしています。

重要なのは、ツリーには「ループ（閉じた輪）」がないことです。 つまり、あるノードから子をたどっていって、同じノードに戻ってくることはありません。 この性質のおかげで、探索アルゴリズムがシンプルに書けます。

Javaでツリー構造を表現する基本クラス

まずは、最もシンプルな「汎用ツリー」を表現するクラスを用意します。 ここでは、各ノードが「名前」と「子ノードのリスト」を持つ形にします。

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

class Node {
    String name;
    List<Node> children;

    Node(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }

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

この Node クラスは、次のようなツリーを表現できます。

  • root
    • child1
    • child2
      • grandchild1
      • grandchild2

実際にツリーを作るコードは次のようになります。

Node root = new Node("root");
Node child1 = new Node("child1");
Node child2 = new Node("child2");
Node grandchild1 = new Node("grandchild1");
Node grandchild2 = new Node("grandchild2");

child2.addChild(grandchild1);
child2.addChild(grandchild2);
root.addChild(child1);
root.addChild(child2);
Java

このように、「ノードが自分と同じ型の子を持つ」という自己相似的な構造が、ツリーの本質です。

深さ優先探索（DFS）の基本アイデア

ツリー探索の代表的なアルゴリズムが「深さ優先探索（Depth-First Search, DFS）」です。 DFS は、「一つの枝をできるところまで深くたどってから、次の枝に移る」探索方法です。

イメージとしては、フォルダ階層をたどるときに「一つのフォルダの中を全部見てから、次のフォルダに移る」感じです。

Javaでは、DFSは再帰と非常に相性が良いです。 ツリー構造そのものが「再帰的」なので、コードも自然に再帰的な形になります。

前順（pre-order）DFS：ノードを「訪れた瞬間」に処理する

DFSにはいくつかのバリエーションがありますが、まずは最も基本的な「前順（pre-order）」を扱います。 前順DFSでは、「ノードを訪れた瞬間に処理し、その後で子をたどる」という順番で探索します。

Javaコードは次のようになります。

public static void dfsPreOrder(Node node) {
    System.out.println(node.name);  // ここでノードを処理

    for (Node child : node.children) {
        dfsPreOrder(child);        // 子を再帰的に探索
    }
}
Java

このメソッドを dfsPreOrder(root); と呼び出すと、 root → child1 → child2 → grandchild1 → grandchild2 のような順番でノード名が表示されます。

深掘り：この再帰DFSの流れを頭の中で追う

初心者にとって重要なのは、「再帰DFSがどう動いているか」をイメージできることです。

dfsPreOrder(root) が呼ばれると、まず root の名前が表示されます。 次に、root.children の各要素に対して dfsPreOrder(child) が呼ばれます。

最初の子 child1 に対して dfsPreOrder(child1) が呼ばれ、 child1 の名前が表示されます。 child1 には子がいないので、そこで再帰は終了し、呼び出し元に戻ります。

次に child2 に対して dfsPreOrder(child2) が呼ばれ、 child2 の名前が表示されます。 その後、grandchild1 と grandchild2 に対して同じように再帰が行われます。

このように、「ノードを処理してから子に降りていく」という流れが、前順DFSの基本です。

中順（in-order）・後順（post-order）という考え方（木の種類による）

一般的なツリーでは「前順」がよく使われますが、 二分木（子が最大2つの木）では「中順（in-order）」や「後順（post-order）」も重要です。

二分木の例として、次のようなクラスを考えます。

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}
Java

この二分木に対して、三種類のDFSを定義できます。

前順（pre-order） ノード → 左 → 右

中順（in-order） 左 → ノード → 右

後順（post-order） 左 → 右 → ノード

コードで見ると次のようになります。

public static void preOrder(TreeNode node) {
    if (node == null) return;
    System.out.println(node.value);
    preOrder(node.left);
    preOrder(node.right);
}

public static void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.println(node.value);
    inOrder(node.right);
}

public static void postOrder(TreeNode node) {
    if (node == null) return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.value);
}
Java

深掘り：なぜ中順DFSが重要なのか（特に二分探索木）

中順DFSは、特に「二分探索木（Binary Search Tree, BST）」で重要です。 BSTでは、「左の子は親より小さい」「右の子は親より大きい」というルールがあります。

この性質のおかげで、中順DFSを行うと「値が昇順に並ぶ」ことが保証されます。

つまり、BST に対して inOrder を実行すると、 ソートされた順番で値を取り出すことができます。

これは、探索アルゴリズムとして非常に強力な性質であり、 ツリー構造の中でも特に二分探索木がよく使われる理由の一つです。

再帰DFSのメリットと注意点

再帰を使ったDFSは、コードが非常にシンプルで読みやすいという大きなメリットがあります。 ツリー構造そのものが再帰的なので、 「ノードを処理して、子に対して同じことをする」という形が自然に書けます。

しかし、注意点もあります。

ツリーが非常に深い場合（例えば、何千階層もの入れ子構造）には、 再帰の深さがスタックの限界を超え、StackOverflowError が発生する可能性があります。

セキュリティの観点から言えば、 ユーザー入力から生成されたツリーをそのまま再帰で探索すると、 攻撃者が「異常に深い構造」を送り込んで、サービスを落とすことが理論上可能です。

そのため、実務では

深さに上限を設ける ループとスタック（自前のデータ構造）でDFSを書く 入力を検証してから探索する

といった工夫が必要になります。 これについては後半で詳しく扱います。

前半のまとめと後半への予告

前半では、ツリー構造の基本と、 Javaでの表現方法、そして深さ優先探索（DFS）の基本形を中心に解説しました。

ツリーとは「親と子の階層構造」であり、 Javaではノードが自分と同じ型の子を持つクラスで表現できること。 DFSは「一つの枝を深くたどってから次に行く」探索であり、 前順・中順・後順という三つのバリエーションがあること。 再帰DFSは美しく書けるが、深さによってはスタックオーバーフローのリスクがあること。

後半では、より実務寄りのテーマとして

幅優先探索（BFS）と DFS の違い 自前スタック・キューを使った非再帰DFS/BFS ツリー探索の応用（検索、集計、フィルタリング） セキュリティ・パフォーマンスの観点から見たツリー探索

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

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