C++でn分木の「次に大きい要素」を求めるアルゴリズムと実装

n分木（n-ary tree）とは、各ノードが最大n個の子ノードを持つことができる木構造のことです。本記事では、n分木の中から指定した数値よりも大きい要素のうち最小のもの（いわゆる「次に大きい要素」）を、C++で求める方法を解説します。

解法の基本となる考え方はシンプルです。木全体を走査しながら、条件を満たす要素の中で最も小さい値を結果として保持し続けることで、最終的に「次に大きい要素」を確実に取得できます。

アルゴリズム

• n分木を作成する。
• 結果を格納する変数を初期化する。
• 次に大きい要素を取得する関数を実装する。
  • 現在のノードがNULLの場合は、その時点で処理を終了して返る。
  • 現在のノードの値が、指定した数値より大きいかどうかを判定する。
  • 大きい場合は、結果がまだ空であるか、または結果の値が現在のノードの値より大きいかを確認する。
  • 上記の条件を満たしていれば、結果を現在のノードで更新する。
  • 現在のノードが持つ子ノードをすべて取得する。
  • 各子ノードに対して反復処理を行う。
    • 再帰的に同じ関数を呼び出す。

このアルゴリズムでは、「指定した数値より大きく、かつ現在の結果より小さい」要素が見つかるたびに結果を更新しています。この仕組みにより、木の走査が完了した時点で、結果には必ず「次に大きい要素」が格納されることが保証されます。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    vector<Node*> child;
};
Node* newNode(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    return newNode;
}
void findNextGreaterElement(Node* root, int x, Node** result) {
    if (root == NULL) {
        return;
    }
    if (root->data > x) {
        if (!(*result) || (*result)->data > root->data) {
            *result = root;
        }
    }
    int childCount = root->child.size();
    for (int i = 0; i < childCount; i++) {
        findNextGreaterElement(root->child[i], x, result);
    }
    return;
}
int main() {
    Node* root = newNode(10);
    root->child.push_back(newNode(12));
    root->child.push_back(newNode(23));
    root->child.push_back(newNode(45));
    root->child[0]->child.push_back(newNode(40));
    root->child[1]->child.push_back(newNode(33));
    root->child[2]->child.push_back(newNode(12));
    Node* result = NULL;
    findNextGreaterElement(root, 20, &result);
    cout << result->data << endl;
    return 0;
}

実行結果

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

23

この例では、探索の基準となる数値として20を指定しています。木の中で20より大きい要素は23、33、40、45ですが、その中で最小のものは23であるため、出力は「23」となります。