C ++中n元树的每个节点的子树中的叶节点数

  • Z时代
  • 2024-01-10
  • 分类：综合

在本教程中，我们将编写一个程序来查找 n 叉树中每个节点的叶节点数。

让我们看看解决问题的步骤。

  • 用你喜欢的树初始化 n 叉树。

  • 使用 DFS 遍历树。

  • 维护一个数组来存储每个节点的叶子节点计数。

  • 在递归调用 DFS 后增加叶节点的计数。

  • 打印所有带有叶节点计数的节点。

示例

让我们看看代码。

#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

结论

如果您对本教程有任何疑问，请在评论部分提及。

以上是 C ++中n元树的每个节点的子树中的叶节点数 的全部内容， 来源链接： utcz.com/z/327510.html

回到顶部