Java | ツリー構造の実践的な操作

Javaで学ぶ「ツリー構造の実践的な操作」（前半）

ツリー構造は、アルゴリズムの教科書だけの話ではなく、実務で頻繁に登場するデータ構造です。 フォルダ階層、メニュー構造、組織図、JSON、XML、DOM、設定ファイル、アクセス権限の階層など、 「親子関係」「階層構造」を持つものはほぼすべてツリーとして扱えます。

前半では、ツリー構造を Java でどう表現し、 実務でよく使う「探索」「検索」「追加・削除」「パスの取得」といった操作を、 初心者向けにかみ砕いて解説していきます。 後半では、より応用的な「フィルタリング」「集計」「権限チェック」「安全な操作設計」などに踏み込みます。

ツリー構造の基本クラスを「実務目線」で設計する

まずは、ツリー構造を表現するクラスを用意します。 ここでは「フォルダ階層」をイメージした、少し実務寄りの Node クラスを使います。

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

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

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

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

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

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

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

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

このクラスには、次のような意味があります。

名前（name） フォルダ名・メニュー名・組織名など、ノードを識別するラベル。

親（parent） 上位のノードへの参照。これがあることで「上に戻る」操作が簡単になります。

子リスト（children） 下位のノードの一覧。これがあることで「下に降りる」操作が簡単になります。

この「親も子も持つ」設計は、実務でツリーを扱うときに非常に便利です。

実例：フォルダ階層をツリーで表現する

この Node クラスを使って、簡単なフォルダ階層を作ってみます。

Node root = new Node("root");
Node docs = new Node("docs");
Node images = new Node("images");
Node reports = new Node("reports");

root.addChild(docs);
root.addChild(images);
docs.addChild(reports);

Node root = new Node("root");
Node docs = new Node("docs");
Node images = new Node("images");
Node reports = new Node("reports");

root.addChild(docs);
root.addChild(images);
docs.addChild(reports);

この構造は次のような階層を表しています。

root docs reports images

このように、ツリー構造は「現実世界の階層」をそのままコードに落とし込むための器です。

実践的な操作1：名前でノードを検索する（DFS）

ツリー構造で最もよく使う操作の一つが「検索」です。 例えば、「フォルダ名 ‘reports’ のノードを見つけたい」といった場面です。

まずは、深さ優先探索（DFS）で検索するメソッドを書いてみます。

public static Node findByName(Node root, String target) {
    if (root.name.equals(target)) {
        return root;
    }
    for (Node child : root.children) {
        Node result = findByName(child, target);
        if (result != null) {
            return result;
        }
    }
    return null;
}

public static Node findByName(Node root, String target) {
    if (root.name.equals(target)) {
        return root;
    }
    for (Node child : root.children) {
        Node result = findByName(child, target);
        if (result != null) {
            return result;
        }
    }
    return null;
}

このメソッドは、次のような流れで動きます。

根からスタートして、名前が一致していないか確認する 一致していなければ、子に対して同じ処理を再帰的に行う どこかで一致したら、そのノードを返す 最後まで見ても見つからなければ null を返す

実務では、「特定のフォルダ」「特定のメニュー」「特定の部署」などを探す処理が頻繁に登場します。 この findByName は、その基本形です。

深掘り：再帰検索の動きを頭の中で追う

例えば、先ほどのツリーで findByName(root, "reports") を呼び出したとします。

最初に root を見る root.name は “root” なので、一致しない 子である docs と images に対して再帰を行う

docs に対して findByName(docs, "reports") が呼ばれる docs.name は “docs” なので、一致しない 子である reports に対して再帰を行う

reports に対して findByName(reports, "reports") が呼ばれる ここで一致し、reports ノードが返される

このように、「上から下へ」「枝をたどりながら」検索が進んでいきます。 この流れをイメージできるようになると、ツリー操作の理解が一気に進みます。

実践的な操作2：ノードを追加する（親を指定して挿入）

ツリー構造では、「特定の場所にノードを追加する」操作もよく使います。 例えば、「docs の下に ‘drafts’ フォルダを追加したい」といった場面です。

まず、親ノードを検索し、その子として新しいノードを追加します。

public static void addChildByName(Node root, String parentName, String childName) {
    Node parent = findByName(root, parentName);
    if (parent == null) {
        System.out.println("Parent not found: " + parentName);
        return;
    }
    Node child = new Node(childName);
    parent.addChild(child);
}

public static void addChildByName(Node root, String parentName, String childName) {
    Node parent = findByName(root, parentName);
    if (parent == null) {
        System.out.println("Parent not found: " + parentName);
        return;
    }
    Node child = new Node(childName);
    parent.addChild(child);
}

このメソッドは、次のような実務的な操作を表現しています。

「docs というフォルダを探して、その中に drafts を作る」 「menu というノードを探して、その下に新しいサブメニューを追加する」 「部署Aを探して、その配下に新しいチームを作る」

ツリー構造の「追加」は、 「親を見つけて、その子リストに追加する」というシンプルなパターンに集約されます。

実践的な操作3：ノードを削除する（親から切り離す）

削除も実務でよく使う操作です。 例えば、「reports フォルダを削除したい」といった場面です。

削除は、「親の子リストから対象ノードを取り除く」という形で実装します。

public static boolean removeByName(Node root, String target) {
    for (Node child : root.children) {
        if (child.name.equals(target)) {
            root.children.remove(child);
            child.parent = null;
            return true;
        }
        if (removeByName(child, target)) {
            return true;
        }
    }
    return false;
}

public static boolean removeByName(Node root, String target) {
    for (Node child : root.children) {
        if (child.name.equals(target)) {
            root.children.remove(child);
            child.parent = null;
            return true;
        }
        if (removeByName(child, target)) {
            return true;
        }
    }
    return false;
}

このメソッドは、次のような動きをします。

根からスタートして、子リストを順番に見る 子の名前が一致したら、その子をリストから削除する 一致しなければ、子に対して再帰的に同じ処理を行う

ここで重要なのは、「削除は親側の操作である」という点です。 ツリー構造では、ノードを消すときは「親からのつながりを切る」ことで実現します。

実践的な操作4：ノードのパスを取得する（root からの道筋）

実務では、「このノードはどこにあるか」を人間に分かりやすく表示したい場面が多くあります。 例えば、「/root/docs/reports」のようなパス表現です。

親参照を持っているので、上に向かってたどることでパスを作ることができます。

public static String getPath(Node node) {
    StringBuilder sb = new StringBuilder();
    Node current = node;
    while (current != null) {
        sb.insert(0, "/" + current.name);
        current = current.parent;
    }
    return sb.toString();
}

public static String getPath(Node node) {
    StringBuilder sb = new StringBuilder();
    Node current = node;
    while (current != null) {
        sb.insert(0, "/" + current.name);
        current = current.parent;
    }
    return sb.toString();
}

例えば、reports ノードに対して getPath(reports) を呼ぶと、 /root/docs/reports という文字列が得られます。

この「パス取得」は、ログ出力、UI表示、エラーメッセージ、アクセス権限チェックなど、 実務で非常に頻繁に使われる操作です。

深掘り：親参照を持つ設計の強さ

前半で定義した Node クラスは、 子だけでなく親も持つ設計になっています。

この設計のおかげで、次のような操作が簡単になります。

特定ノードから root までの距離を計算する 特定ノードのパスを取得する 「親に戻る」ナビゲーションを実装する 権限チェックで「上位のノードの設定」を参照する

ツリー構造を実務で扱うとき、 「親参照を持つかどうか」は非常に重要な設計ポイントです。

セキュリティ・パフォーマンスの観点（前半の導入）

ツリー構造の操作は便利ですが、 セキュリティスペシャリストの視点では次の点に注意が必要です。

ツリーが極端に深くなると、再帰が危険になる ユーザー入力から生成されたツリーに対して再帰的な操作を行うと、 攻撃者が「異常に深い構造」を送り込んで StackOverflowError を誘発する可能性があります。

ノード数が極端に多いと、探索が重くなる 線形探索に近い形でツリーをたどると、 ノード数が増えたときに処理時間が急増します。

このあたりは後半で、 「非再帰の探索」「制限付き操作」「安全な設計」などとともに詳しく扱います。

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

前半では、ツリー構造の「実務的な操作」の基本を整理しました。

Javaでの実務寄りな Node クラス設計（親・子を持つ） 名前でノードを検索する（DFS） 親を指定してノードを追加する 親から切り離してノードを削除する ノードのパスを取得する（/root/docs/reports のような表現）

後半では、さらに一歩進んで

幅優先探索（BFS）を使った操作 フィルタリング・集計・権限チェックなどの応用 非再帰の探索による安全性向上 セキュリティ・パフォーマンスを意識したツリー操作設計

といったテーマを、具体的な Java コードとともに深掘りしていきます。