已知一颗树的节点间关系,请编程实现该树的先根遍历。要求:输入:若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且数的度小于5。输出:该树的先根遍历序列,序列中每个字母用空格隔开。
时间: 2024-03-09 09:49:01 浏览: 57
好的,这里给您提供一份 C++ 代码,可以实现树的先根遍历并输出遍历序列。该代码与上一问的代码类似,只需在遍历过程中输出每个节点的编号即可。
```c++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 26; // 最大节点数
vector<int> children[MAXN]; // 存储每个节点的孩子节点
bool visited[MAXN]; // 标记每个节点是否已经被访问
void preOrderTraversal(int root) {
cout << char(root + 'A') << " "; // 输出当前节点
visited[root] = true; // 标记当前节点已经被访问
// 遍历当前节点的所有孩子节点
for (int i = 0; i < children[root].size(); i++) {
int child = children[root][i];
if (!visited[child]) {
preOrderTraversal(child); // 递归遍历孩子节点
}
}
}
int main() {
string line;
while (getline(cin, line)) {
int parent = line[0] - 'A';
int child = line[1] - 'A';
children[parent].push_back(child); // 存储父节点和孩子节点的对应关系
}
// 从根节点开始遍历整棵树
for (int i = 0; i < MAXN; i++) {
if (!children[i].empty()) {
preOrderTraversal(i);
break;
}
}
return 0;
}
```
该代码与上一问的代码类似,只不过在遍历过程中输出了每个节点的编号,并在编号之间添加了空格,最终实现了先根遍历序列的输出。
阅读全文