Trong bài toán này, chúng ta được cung cấp một mảng 2-D chứa cạnh của n-ary trong đó cạnh xác định cạnh của cây n-ary. Chúng tôi phải in tất cả các nút lá của cây a-ary đã tạo.
Cây n-ary là một cây có tối đa n nút con, tức là một nút có thể có 1, 2, ... n nút con.
Hãy xem một ví dụ để hiểu vấn đề -
Input: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
Output: 1 4 7 Giải thích - hãy tạo một cây bằng cách sử dụng mảng cạnh -
Các nút lá của cây này là 1, 4, 7.
Để giải quyết vấn đề này, chúng ta sẽ duyệt cây bằng DFS (nó sẽ tìm nút lá của mọi cây con). Ngoài ra, các nút đã thăm của mảng được đánh dấu. Nếu nút có con (nếu không phải là nút lá), chúng tôi sẽ gắn cờ giá trị và in các nút không có nút con.
Ví dụ
Chương trình này cho thấy việc triển khai giải pháp của chúng tôi -
#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;
} Đầu ra
Leaf nodes of the tree are − 4 5 8 7