C++のn-aryツリーで指定された値より大きいノードの数

n-aryツリーと数が与えられた場合、与えられた数よりも大きいノードの数を数える必要があります。例を見てみましょう。

入力

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

出力

3

nより大きい値を持つノードが3つあります。

アルゴリズム

• n-aryツリーを初期化します。

• カウントを0に初期化します。

• 値がnより大きいノードを見つけたら、カウントを1つ増やします。

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

• すべての子を繰り返し処理し、同じ関数を再帰的に呼び出してノードをカウントします。

• カウントを返します。

実装

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