C++のn-aryツリーの次の大きな要素

n-aryツリーは、ノードごとにn個の子を持つツリーです。番号nが与えられ、n-aryツリーから次に大きい要素を見つける必要があります。

n-aryツリーをトラバースし、結果を維持することで解決策を見つけることができます。

アルゴリズム

• n-aryツリーを作成します。
• 結果を初期化します。
• 次に大きな要素を取得する関数を記述します。
  • 現在のノードがnullの場合に戻ります。
  • 現在のノードデータが予想される要素よりも大きいかどうかを確認してください。
  • 「はい」の場合、結果が空であるか、結果が現在のノードデータよりも大きいかどうかを確認します。
  • 上記の条件が満たされている場合は、結果を更新します。
  • 現在のノードの子を取得します。
  • 子供たちを繰り返します。
    • 再帰関数を呼び出します。

指定された数より大きく、結果よりも小さい要素が見つかるたびに、結果を更新しています。これにより、最終的に次に大きな要素を確実に取得できます。

実装

以下は、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