使用 DFS 以 C++ 语言打印一个 n 叉树的所有叶节点

在这个题目中，我们给定一个二维数组，其中包含 n 叉树的边，边定义了 n 叉树的边缘。我们必须打印所创建的 a 叉树的所有叶节点。

n 叉树是一个有 n 个子节点的树，即一个节点可以有 1、2、...n 个子节点。

我们通过一个例子来理解题目 -

Input: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
Output: 1 4 7

说明 -让我们使用边数组创建一个树 -

这棵树的叶节点是 1、4、7。

要解决这个问题，我们将使用 DFS 遍历这棵树（它将找到每个子树的叶节点）。同时，数组的已访问节点被打上标记。如果节点有子节点（如果不是叶节点），我们将标记该值并打印没有子节点的节点。

示例

这个程序展示了我们解决方案的实现 -

 在线示例

#include <bits/stdc++.h>
using namespace std;
void DFS(list<int> t[], int node, int parent) {
   int flag = 0;
   for (auto ir : t[node]) {
      if (ir != parent) {
         flag = 1;
         DFS(t, ir, node);
      }
   }
   if (flag == 0)
      cout<<node<<"\t";
}
int main() {
   list<int> t[1005];
   pair<int, int> edges[] = {
      { 1, 2 },
      { 1, 3 },
      { 2, 4 },
      { 3, 5 },
      { 3, 6 },
      { 3, 7 },
      { 6, 8 }
   };
   int cnt = sizeof(edges) / sizeof(edges[0]);
   int node = cnt + 1;
   for (int i = 0; i < cnt; i++) {
      t[edges[i].first].push_back(edges[i].second);
      t[edges[i].second].push_back(edges[i].first);
   }
   cout<<"Leaf nodes of the tree are:\n";
   DFS(t, 1, 0);
   return 0;
}

输出

Leaf nodes of the tree are −
4 5 8 7

更新于: 2020-01-22

490 次浏览

启动您的 职业生涯

完成课程以获得认证

入门
广告