C++でn分木（n-aryツリー）内の指定値より大きいノード数を数える方法

n分木（n-aryツリー）と1つの数値が与えられたとき、その数値より大きい値を持つノードの個数を数える問題を考えてみましょう。まずは具体例から見ていきます。

入力例

tree = [[4], [1, 2], [3, 5]]
n = 2

出力例

3

この例では、n（= 2）より大きい値を持つノードが3つ存在するため、答えは3となります。

アルゴリズム

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

• カウント用の変数を0で初期化します。

• 現在のノードの値がnより大きい場合は、カウントを1増やします。

• 現在のノードの子ノードをすべて取得します。

• 各子ノードに対して同じ関数を再帰的に呼び出し、条件を満たすノードを数えます。

• 最終的なカウントを返します。

この手法は深さ優先探索（DFS）に基づいており、木全体を一度だけ走査するため、計算量はO(N)（Nはノード総数）です。

C++での実装

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

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    vector<Node*> child;
};
Node* getNewNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    return temp;
}
int getGreaterElementsCount(Node* root, int n) {
    if (root == NULL)
        return 0;
    int count = 0;
    if (root->data > n) {
        count++;
    }
    int nodeChildrenCount = root->child.size();
    for (int i = 0; i < nodeChildrenCount; i++) {
        Node* child = root->child[i];
        count += getGreaterElementsCount(child, n);
    }
    return count;
}
int main() {
    Node* root = getNewNode(1);
    (root->child).push_back(getNewNode(2));
    (root->child).push_back(getNewNode(3));
    (root->child).push_back(getNewNode(4));
    (root->child[0]->child).push_back(getNewNode(5));
    (root->child[0]->child).push_back(getNewNode(5));
    (root->child[1]->child).push_back(getNewNode(6));
    (root->child[1]->child).push_back(getNewNode(6));
    (root->child[1]->child).push_back(getNewNode(7));
    (root->child[2]->child).push_back(getNewNode(8));
    (root->child[2]->child).push_back(getNewNode(8));
    (root->child[2]->child).push_back(getNewNode(9));
    int n = 2;
    cout << getGreaterElementsCount(root, n) << endl;
    return 0;
}

実行結果

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

10

このプログラムでは、ルートから葉まで木全体を再帰的に走査し、値が2より大きいノードをすべて数えています。結果として10という値が出力され、これは木の中で2より大きい値を持つノードの総数です。

このように、n分木に対する再帰的な走査は、二分木と同様の考え方でシンプルに実装できます。子ノードの数が可変である点だけ注意すれば、さまざまな木構造の問題に応用できる汎用的なパターンです。