用c++编写程序:题目描述:已知一颗树的节点间关系,请编程实现该树的先根遍历。 输入:若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26 个)。且树的度小于5。 输出:该树的先根遍历序列,序列中每个字母用空格隔开。 样例输入: B E B F A B A C 样例输出复制A B E F C
时间: 2024-03-17 16:42:15 浏览: 70
好的,以下是C++的代码实现:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 30; // 最大节点数
vector<int> tree[MAXN]; // 存储树的关系
bool vis[MAXN]; // 标记节点是否被访问过
void preOrder(int root) {
cout << char(root + 'A'); // 输出当前节点
vis[root] = true; // 标记当前节点已被访问
for (int i = 0; i < tree[root].size(); i++) {
int child = tree[root][i]; // 获取当前节点的一个孩子
if (!vis[child]) { // 如果当前孩子节点未被访问过
preOrder(child); // 递归访问当前孩子节点
}
}
}
int main() {
string s;
while (cin >> s) {
int parent = s[0] - 'A'; // 获取父亲节点
int child = s[1] - 'A'; // 获取孩子节点
tree[parent].push_back(child); // 将孩子节点加入父亲节点的儿子列表中
}
memset(vis, false, sizeof(vis)); // 初始化所有节点未被访问过
preOrder(0); // 从根节点 A 开始先根遍历
return 0;
}
```
输入格式如题目描述所述,每次读入一对父子节点,将孩子节点加入父亲节点的儿子列表中。然后从根节点 A 开始进行先根遍历,具体实现方法就是递归地访问当前节点的每一个孩子节点。最后输出先根遍历序列即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)