已知一颗树的节点间关系,请编程实现该树的先根遍历。 输入 若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且树的度小于5。 输出 该树的先根遍历序列,序列中每个字母用空格隔开。请用c++编写这个程序
时间: 2024-03-21 08:41:26 浏览: 19
以下是用C++实现树的先根遍历的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 26;
vector<int> edge[MAXN];
bool visited[MAXN];
void DFS(int u) {
visited[u] = true;
cout << (char)(u + 'A') << " ";
for (int i = 0; i < edge[u].size(); i++) {
int v = edge[u][i];
if (!visited[v]) {
DFS(v);
}
}
}
int main() {
int parent, child;
while (cin >> parent >> child) {
edge[parent].push_back(child);
}
DFS(0); // 从根节点 A 开始遍历
return 0;
}
```
输入格式为若干行,每行表示一组父子节点关系,例如:
```
0 1
0 2
1 3
1 4
2 5
```
表示根节点为 A,A 的两个子节点为 B 和 C,B 的两个子节点为 D 和 E,树的结构为:
```
A
/ \
B C
/ \
D E
```
输出为先根遍历序列,即 `A B D E C`。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)