数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究使用 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 次浏览
广告