C++でn分木の各ノードのサブツリーに含まれる葉ノードの数を求める方法

このチュートリアルでは、n分木（n-ary tree）の各ノードについて、そのサブツリーに含まれる葉ノード（リーフノード）の数を求めるプログラムを作成します。

葉ノードとは、子を一切持たないノードのことです。n分木が与えられたとき、すべてのノードを根とみなしたサブツリーそれぞれに対して、含まれる葉ノードの数を計算します。まずは具体例を見てみましょう。

入力

N = 8
tree = [[2, 3], [], [4, 5, 6], [7, 8], [], [], [], []]

出力

1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1

この例では、ノード1を根とする木全体には5つの葉ノードがあり、ノード3を根とするサブツリーには4つの葉ノードが含まれていることがわかります。

アルゴリズム

• 任意のn分木を初期化します。

• DFS（深さ優先探索）を使って木を走査します。

• 各ノードの葉ノード数を格納するための配列を用意します。

• DFSの再帰呼び出しから戻るたびに、子ノードの葉ノード数を親ノードに加算します。

• すべてのノードとその葉ノード数を出力します。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
void insertNode(int x, int y, vector<int> tree[]) {
    tree[x].push_back(y);
}
void DFS(int node, int leaf[], int visited[], vector<int> tree[]) {
    leaf[node] = 0;
    visited[node] = 1;
    for (auto it : tree[node]) {
        if (!visited[it]) {
            DFS(it, leaf, visited, tree);
            leaf[node] += leaf[it];
        }
    }
    if (!tree[node].size()) {
        leaf[node] = 1;
    }
}
int main() {
    int N = 8;
    vector<int> tree[N + 1];
    insertNode(1, 2, tree);
    insertNode(1, 3, tree);
    insertNode(3, 4, tree);
    insertNode(3, 5, tree);
    insertNode(3, 6, tree);
    insertNode(4, 7, tree);
    insertNode(4, 8, tree);
    int leaf[N + 1];
    int visited[N + 1];
    for (int i = 0; i <= N; i++) {
        visited[i] = 0;
    }
    DFS(1, leaf, visited, tree);
    for (int i = 1; i <= N; i++) {
        cout << i << "->" << leaf[i] << endl;
    }
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

1->5
2->1
3->4
4->2
5->1
6->1
7->1
8->1

コードの解説

DFS関数では、まず現在のノードを訪問済みとしてマークし、葉ノード数を0で初期化します。続いて、隣接する各子ノードに対して再帰的にDFSを呼び出し、処理から戻ったタイミングでその子のサブツリーに含まれる葉ノード数を親ノードの値に加算していきます。最後に、子を一切持たないノード（つまり葉ノード自身）の場合には1を設定します。

このように「子の結果を親に集約する」ボトムアップ方式の再帰により、すべてのノードのサブツリーに含まれる葉ノードの数を一度の走査で求められます。計算量はノード数をNとするとO(N)、各ノードをちょうど1回訪問するだけで済むため非常に効率的です。