solution.cpp

#include <iostream>
#include <unordered_map>

using namespace std;

//定义结构体表示一个节点
struct Node {
    string name;
    Node* left;
    Node* right;
};

//建立二叉树的函数
Node* build_tree(int n) {
    // 建立根节点
    string line;
    getline(cin, line);
    stringstream ss(line);
    string name, is, the, father, s;
    ss >> name >> is >> the >> father >> s;
    Node* root = new Node{name, nullptr, nullptr};

    // 建立剩余的节点
    for (int i = 1; i < n; i++) {
        getline(cin, line);
        stringstream ss(line);
        string name, is, the, father, s;
        ss >> name >> is >> the >> father >> s;
        Node* cur = root;
        while (true) {
            if (father == cur->name && s == "son") {
                if (cur->left == nullptr) {
                    cur->left = new Node{name, nullptr, nullptr};
                    break;
                } else if (cur->right == nullptr) {
                    cur->right = new Node{name, nullptr, nullptr};
                    break;
                } else {
                    cur = cur->left;
                }
            } else {
                cur = cur->right;
            }
        }
    }
    return root;
}

//输出前序遍历的函数
void preorder(Node* root) {
    cout << root->name << " ";
    if (root->left != nullptr) preorder(root->left);
    if (root->right != nullptr) preorder(root->right);
}

int main() {
    int n;
    cin >> n;
    cin.ignore();
    Node* root = build_tree(n);
    preorder(root);
    return 0;
}