已知一颗树的节点间关系,请编程实现该树的先根遍历。
输入
若干行,每行描述了一组双亲节点和children节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且树的度小于5。
输出
该树的先根遍历序列,序列中每个字母用空格隔开。
样例输入 复制
B E
B F
A B
A C
样例输出 复制
A B E F C
#include<iostream>
using namespace std;
struct Node {
char val;
vector<Node*> children;
Node(char c) : val(c) {}
};
Node* build_tree(const vector<pair<char, char>>& pairs) {
unordered_map<char, Node*> nodes;
for (const auto& pair : pairs) {
char parent = pair.first;
char child = pair.second;
if (nodes.find(parent) == nodes.end()) {
nodes[parent] = new Node(parent);
}
if (nodes.find(child) == nodes.end()) {
nodes[child] = new Node(child);
}
nodes[parent]->children.push_back(nodes[child]);
}
return nodes.begin()->second; // 返回根节点
}
void preorder_traversal(Node* root, vector<char>& result) {
if (root == nullptr) {
return;
}
result.push_back(root->val);
for (Node* child : root->children) {
preorder_traversal(child, result);
}
}
int main() {
vector<pair<char, char>> pairs;
char parent, child;
while (cin >> parent >> child) {
pairs.emplace_back(parent, child);
}
Node* root = build_tree(pairs);
vector<char> result;
preorder_traversal(root, result);
for (char c : result) {
cout << c << " ";
}
cout << endl;
return 0;