📘 一、知識點解析

✅ 多叉樹（General Tree）

• 節點可以有多於兩個子節點的樹結構。
• 每個節點可以有 0 個或多個孩子，常用 vector<TreeNode*> 表示。

✅ 先序遍歷（Preorder Traversal）

• 順序為：根節點 → 所有子節點（從左到右）
• 遞歸方式容易實現，先印出自己，再對每個孩子呼叫 preorder(child)。

✅ 構建多叉樹

• 題目給的是一系列父子關係，需自己找出：

  • 誰是根節點：從沒被當作 child 的節點就是根。
  • 如何建立結構：用 map<string, TreeNode*> 建立名字與節點的對應。

---

📗 二、程式碼逐行解析

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;

🔹 引入必要的資料結構。unordered_map 用於節點查找，unordered_set 用於記錄哪些是子節點。

---

struct TreeNode {
    string val;
    vector<TreeNode*>* children;

    TreeNode(string v): val(v), children(new vector<TreeNode*>) {}
};

🔹 定義多叉樹節點。每個節點儲存自己的名字和一個指向子節點的 vector 指標。

---

void preorder(TreeNode* node){
    if(node == NULL) return;
    cout << node->val << " ";
    for(auto it = node->children->begin(); it != node->children->end(); it++){
        preorder(*it);
    }
}

🔹 遞迴先序遍歷：印出自己，再遞迴印出每個子節點。

---

int main(){
    int n;
    cin >> n;

🔹 讀取父子關係總數。

---

    unordered_map<string, TreeNode*> keyToNode = {};
    unordered_set<string> hasParentNodes = {};

🔹 keyToNode 負責將名字對應到節點，hasParentNodes 記錄所有曾經當作子節點出現過的名字。

---

    for(int i = 0; i < n; i++){
        string parent, child;
        cin >> parent >> child;

🔹 開始讀入每組關係。

---

        TreeNode* parentNode = NULL;

        if(keyToNode.find(parent) == keyToNode.end()){
            parentNode = new TreeNode(parent);
        }else{
            parentNode = keyToNode.find(parent)->second;
        }

🔹 若 parent 還沒建立節點，創建一個，否則取出原本節點。

---

        TreeNode* childNode = new TreeNode(child);

🔹 子節點直接建立（即使後續還會成為別人的 parent 也無妨，map 最後會統一記錄）。

---

        hasParentNodes.insert(child);
        keyToNode.insert({parent, parentNode});
        keyToNode.insert({child, childNode});
        parentNode->children->push_back(childNode);
    }

🔹 記下 child、更新 map 以及加進 parent 的子節點。

---

    TreeNode* root = NULL;
    for(auto it = keyToNode.begin(); it != keyToNode.end(); it++){
        if(hasParentNodes.find(it->first) == hasParentNodes.end()){
            root = it->second;
            break;
        }
    }

🔹 從所有節點中找出「從沒當過 child」的節點，即為根。

---

    preorder(root);
    return 0;
}

🔹 執行先序遍歷，並結束程式。

---

🌲 三、結構示意圖（以輸入範例為例）

           A
         /   \
        B     C
       / \   / \
      D   E F   G

• 先序遍歷：A → B → D → E → C → F → G

---

🔄 四、流程圖（文字版）

輸入所有 parent-child 關係
        ↓
建立 TreeNode 並建立關係
        ↓
記錄所有出現過的 child
        ↓
從未出現在 child 中的節點找出 root
        ↓
從 root 執行 preorder
        ↓
依序印出節點名稱

---

✅ 五、完整整理後的程式碼

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;

struct TreeNode {
    string val;
    vector<TreeNode*>* children;

    TreeNode(string v): val(v), children(new vector<TreeNode*>) {}
};

void preorder(TreeNode* node){
    if(node == NULL) return;
    cout << node->val << " ";
    for(auto child : *(node->children)){
        preorder(child);
    }
}

int main(){
    int n;
    cin >> n;

    unordered_map<string, TreeNode*> keyToNode;
    unordered_set<string> hasParentNodes;

    for(int i = 0; i < n; i++){
        string parent, child;
        cin >> parent >> child;

        if(keyToNode.find(parent) == keyToNode.end())
            keyToNode[parent] = new TreeNode(parent);

        if(keyToNode.find(child) == keyToNode.end())
            keyToNode[child] = new TreeNode(child);

        keyToNode[parent]->children->push_back(keyToNode[child]);
        hasParentNodes.insert(child);
    }

    TreeNode* root = nullptr;
    for(auto& [name, node] : keyToNode){
        if(hasParentNodes.find(name) == hasParentNodes.end()){
            root = node;
            break;
        }
    }

    preorder(root);
    return 0;
}