题目描述 已知一颗树的节点间关系,请编程实现该树的先根遍历。 输入 若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且树的度小于5。 输出 该树的先根遍历序列,序列中每个字母用空格隔开。
时间: 2024-03-17 22:41:20 浏览: 59
用C语言程实现树的遍历(算法)。分出先序,中序,后序
可以按照以下步骤解决该问题:
1. 构建树的数据结构。可以定义一个 `TreeNode` 结构体,其中包含当前节点的值和子节点的指针数组。
```c++
struct TreeNode {
char val;
vector<TreeNode*> children;
TreeNode(char c) : val(c) {}
};
```
2. 根据输入构建树。我们可以使用一个哈希表来保存每个节点对应的指针,并在构建树的过程中使用该哈希表来查找每个节点的指针。
```c++
map<char, TreeNode*> nodes;
while (cin >> parent >> child) {
// 根据节点值查找节点指针
TreeNode* parentNode = nullptr;
if (nodes.find(parent) != nodes.end()) {
parentNode = nodes[parent];
} else {
parentNode = new TreeNode(parent);
nodes[parent] = parentNode;
}
TreeNode* childNode = nullptr;
if (nodes.find(child) != nodes.end()) {
childNode = nodes[child];
} else {
childNode = new TreeNode(child);
nodes[child] = childNode;
}
// 将子节点添加到父节点的子节点数组中
parentNode->children.push_back(childNode);
}
```
3. 实现先根遍历。可以使用递归方式实现先根遍历,先遍历当前节点,然后递归遍历每个子节点。
```c++
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
for (auto child : root->children) {
preorderTraversal(child);
}
}
```
完整代码如下:
```c++
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct TreeNode {
char val;
vector<TreeNode*> children;
TreeNode(char c) : val(c) {}
};
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
for (auto child : root->children) {
preorderTraversal(child);
}
}
int main() {
map<char, TreeNode*> nodes;
char parent, child;
while (cin >> parent >> child) {
TreeNode* parentNode = nullptr;
if (nodes.find(parent) != nodes.end()) {
parentNode = nodes[parent];
} else {
parentNode = new TreeNode(parent);
nodes[parent] = parentNode;
}
TreeNode* childNode = nullptr;
if (nodes.find(child) != nodes.end()) {
childNode = nodes[child];
} else {
childNode = new TreeNode(child);
nodes[child] = childNode;
}
parentNode->children.push_back(childNode);
}
preorderTraversal(nodes.begin()->second);
return 0;
}
```
阅读全文