C++のn-aryツリーのすべてのノードのサブツリーにあるリーフノードの数

このチュートリアルでは、n-aryツリー内のすべてのノードのリーフノードの数を見つけるプログラムを作成します。

n-aryツリーが与えられた場合、すべてのサブツリーのリーフノードの数を見つける必要があります。例を見てみましょう。

入力

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

アルゴリズム

• 好きなツリーでn-aryツリーを初期化します。

• DFSを使用してツリーをトラバースします。

• 各ノードリーフノード数の数を格納する配列を維持します。

• DFSへの再帰呼び出しの後にリーフノードのカウントをインクリメントします。

• リーフノード数ですべてのノードを印刷します。

実装

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