输入若干行,每行描述了一组双亲节点和孩子节点的关系序偶对,输出该树的先根遍历序列用c++写
时间: 2024-03-09 08:49:46 浏览: 24
假设输入的每行数据格式为:`parent child1 child2 ...`,其中 `parent` 表示双亲节点,`child1`、`child2` 等表示该节点的孩子节点。假设树的节点数据结构如下:
```cpp
struct TreeNode {
int val;
vector<TreeNode*> children;
};
```
其中 `val` 表示节点的值,`children` 表示该节点的子节点列表。
根据输入数据,可以先构建出一棵树。然后对该树进行先根遍历。
以下是完整的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct TreeNode {
int val;
vector<TreeNode*> children;
TreeNode(int val) {
this->val = val;
}
};
void preorderTraversal(TreeNode* root, vector<int>& result) {
if (root == nullptr) {
return;
}
result.push_back(root->val);
for (TreeNode* child : root->children) {
preorderTraversal(child, result);
}
}
int main() {
map<int, TreeNode*> map;
int parent, child;
while (cin >> parent) {
TreeNode* parentNode = map[parent];
if (parentNode == nullptr) {
parentNode = new TreeNode(parent);
map[parent] = parentNode;
}
while (cin.peek() != '\n') {
cin >> child;
TreeNode* childNode = map[child];
if (childNode == nullptr) {
childNode = new TreeNode(child);
map[child] = childNode;
}
parentNode->children.push_back(childNode);
}
cin.get(); // 读取换行符
}
// 先根遍历
vector<int> result;
preorderTraversal(map[1], result);
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}
```
输入数据示例:
```
1 2 3
2 4 5
3 6
5 7
```
输出结果为:`1 2 4 5 7 3 6`。