🧠 一、知識點解析

✅ 1. 二元搜尋樹（BST）

• 每個節點都有左子節點與右子節點。
• 若插入值 < 節點值 → 插入左子樹
• 若插入值 > 節點值 → 插入右子樹
• 若插入值 == 節點值 → 節點 count 數加一

---

✅ 2. 出現次數記錄

• 用 count 欄位記錄每個值的出現次數。

---

✅ 3. 層序遍歷（Level-order Traversal）

• 使用 Queue 資料結構。
• 從 root 開始，逐層輸出節點值與 count。

---

🧾 二、逐行程式碼講解

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

🔹 引入標準輸入輸出、動態陣列與隊列。

---

struct TreeNode{
    int val, count;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v): val(v),count(1), left(NULL), right(NULL){}
};

🔹 自定義節點結構，包含：

• val: 該節點值
• count: 此值在插入過程中出現的次數
• left, right: 指向左右子樹的指標

---

TreeNode* insert(TreeNode* root, int val){
    if(root == NULL){
        return new TreeNode(val);
    }else if(root->val == val){
        root->count+=1;
    }else if(val < root->val){
        root->left = insert(root->left, val);
    }else if(val > root->val){
        root->right = insert(root->right, val);
    }
    return root;
}

🔹 插入函式的遞迴定義：

• 若節點為空：創建新節點
• 若值重複：將 count 加一
• 否則遞迴插入到對應子樹

---

int main (){
    int n;
    cin >> n;
    TreeNode* root = NULL;
    int t;
    for(int i = 0; i < n; i++){
        cin >> t;
        root = insert(root, t);
    }

🔹 讀入數據並建構整棵 BST。

---

    queue<TreeNode*> qqq = {};
    qqq.push(root);

🔹 初始化 Queue，準備進行層序遍歷。

---

    while(!qqq.empty()){
        TreeNode* node = qqq.front();
        qqq.pop();

        cout << node->val << " " << node->count << endl;

🔹 每次取出 Queue 最前端節點，輸出其值與次數。

---

        if(node->left != NULL){
            qqq.push(node->left);
        }
        if(node->right != NULL){
            qqq.push(node->right);
        }
    }

    return 0;
}

🔹 將左右子節點加入 Queue，繼續處理下一層節點。

---

🌳 三、插入與層序遍歷示意圖

輸入：

8
5 7 2 5 7 7 3 3

🔨 插入過程圖解：

Step 1: 插入 5 → 根節點為 5
Step 2: 插入 7 → 右子為 7
Step 3: 插入 2 → 左子為 2
Step 4: 插入 5 → root.count = 2
Step 5: 插入 7 → 7.count = 2
Step 6: 插入 7 → 7.count = 3
Step 7: 插入 3 → 2 右子為 3
Step 8: 插入 3 → 3.count = 2

最終結構：

        5 (2)
       /     \
   2 (1)     7 (3)
     \
     3 (2)

🌀 層序輸出結果：

5 2
2 1
7 3
3 2

---

✅ 四、完整程式碼

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct TreeNode{
    int val, count;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v): val(v),count(1), left(NULL), right(NULL){}
};

TreeNode* insert(TreeNode* root, int val){
    if(root == NULL){
        return new TreeNode(val);
    }else if(root->val == val){
        root->count+=1;
    }else if(val < root->val){
        root->left = insert(root->left, val);
    }else if(val > root->val){
        root->right = insert(root->right, val);
    }
    return root;
}

int main (){
    int n;
    cin >> n;
    TreeNode* root = NULL;
    int t;
    for(int i = 0; i < n; i++){
        cin >> t;
        root = insert(root, t);
    }

    queue<TreeNode*> qqq = {};
    qqq.push(root);

    while(!qqq.empty()){
        TreeNode* node = qqq.front();
        qqq.pop();

        cout << node->val << " " << node->count << endl;

        if(node->left != NULL){
            qqq.push(node->left);
        }
        if(node->right != NULL){
            qqq.push(node->right);
        }
    }

    return 0;
}

---

🔁 五、流程圖（文字版本）

開始
 ↓
讀入 n
 ↓
for i in 1..n：
    插入值到 BST：
      - 若不存在 → 建節點
      - 若已存在 → 次數 +1
 ↓
初始化 queue，從 root 開始
 ↓
while queue 不空：
    彈出節點 → 輸出 val 和 count
    若有左子 → queue.push(左子)
    若有右子 → queue.push(右子)
 ↓
結束