Board logo

標題: 資料結構 202 二元樹的建立與走訪(難) [打印本頁]
作者: may    時間: 2025-3-23 21:46     標題: 資料結構 202 二元樹的建立與走訪(難)

二元樹的建立與走訪
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 撰寫程式讓使用者輸入一個以陣列（Array）表示完全二元樹（Complete Binary Tree）的字串，例如：「A,B,C,D,,E,F」，其中節點（Node）以大寫英文字母表示，且節點與節點間以半形逗號（,）隔開，轉換方式如下圖。
[attach]20820[/attach]

輸入字串轉換為二元樹

(2) 針對轉換後的二元樹，請以中序走訪（Inorder）依序輸出所有節點，並按照「字母順序」輸出此二元樹的所有葉節點（Leaf node）。

提示：節點數量小於 20 個。

3. 輸入輸出：
輸入說明
一個代表完全二元樹的字串，節點以大寫英文字母表示，且節點與節點間以半形逗號（,）間隔。

輸出說明
第 1 列：以中序走訪依序輸出所有節點。
第 2 列：依照「字母順序」輸出此二元樹的所有葉節點。

範例輸入1
A,B,C,D,,E,F
範例輸出1
DBAECF
DEF
範例輸入2
A,B,C,D,E,,,,,F,G
範例輸出2
DBFEGAC
CDFG
作者: may    時間: 2025-3-23 21:50

回復 1# may
  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <algorithm>
  4. #include <bits/stdc++.h>
  5. using namespace std;

  7. // 定義二元樹節點結構
  8. struct TreeNode {
  9.     char value;       // 節點的值
  10.     TreeNode* left;   // 左子節點
  11.     TreeNode* right;  // 右子節點
  12.    
  13.     TreeNode(char val) : value(val), left(nullptr), right(nullptr) {}
  14. };

  16. // 根據陣列建立二元樹
  17. TreeNode* buildTree(const vector<string>& nodes, int index) {
  18.     if (index >= nodes.size() || nodes[index] == "") {
  19.         return nullptr; // 如果超出範圍或是空節點，返回空
  20.     }
  21.    
  22.     TreeNode* node = new TreeNode(nodes[index][0]); // 創建節點
  23.     node->left = buildTree(nodes, 2 * index + 1);  // 左子節點
  24.     node->right = buildTree(nodes, 2 * index + 2); // 右子節點
  25.     return node;
  26. }

  28. // 中序走訪 (Inorder traversal)
  29. void inorderTraversal(TreeNode* root, string& result) {
  30.     if (root == nullptr) {
  31.         return;
  32.     }
  33.     inorderTraversal(root->left, result);  // 遍歷左子樹
  34.     result += root->value;                 // 訪問根節點
  35.     inorderTraversal(root->right, result); // 遍歷右子樹
  36. }

  38. // 尋找所有葉節點
  39. void findLeafNodes(TreeNode* root, vector<char>& leaves) {
  40.     if (root == nullptr) {
  41.         return;
  42.     }
  43.     if (root->left == nullptr && root->right == nullptr) {
  44.         leaves.push_back(root->value); // 如果是葉節點，加入葉節點列表
  45.     }
  46.     findLeafNodes(root->left, leaves);  // 查找左子樹
  47.     findLeafNodes(root->right, leaves); // 查找右子樹
  48. }

  50. int main() {
  51.     string input;
  52.     getline(cin, input); // 讀取整行輸入
  53.    
  54.     // 將字串根據逗號分割成陣列
  55.     vector<string> nodes;
  56.     size_t pos = 0;
  57.     while ((pos = input.find(',')) != string::npos) {
  58.         nodes.push_back(input.substr(0, pos));
  59.         input.erase(0, pos + 1);
  60.     }
  61.     nodes.push_back(input);  // 添加最後一個節點（可能是空的）

  63.     // 根據輸入的陣列建立二元樹
  64.     TreeNode* root = buildTree(nodes, 0);

  66.     // 1. 中序走訪並輸出結果
  67.     string inorderResult;
  68.     inorderTraversal(root, inorderResult);
  69.     cout << inorderResult << endl;

  71.     // 2. 找出葉節點並按照字母順序排序
  72.     vector<char> leafNodes;
  73.     findLeafNodes(root, leafNodes);
  74.     sort(leafNodes.begin(), leafNodes.end()); // 排序葉節點
  75.     for (char leaf : leafNodes) {
  76.         cout << leaf;
  77.     }
  78.     cout << endl;

  80.     return 0;
  81. }
複製代碼
-------------------------------------------------
程式解釋：
TreeNode結構：定義了二元樹的節點，每個節點包含value（節點值）、left（左子樹指標）和right（右子樹指標）。

buildTree函數：根據傳入的字串陣列來遞歸建立二元樹，使用完全二元樹的索引規則。

inorderTraversal函數：進行中序走訪（左-根-右），並將走訪的結果保存在字串中。

findLeafNodes函數：尋找葉節點，葉節點的定義是左右子樹均為nullptr的節點，並將這些葉節點存入leaves向量。

主程式：首先讀取並解析輸入的字串，建立二元樹，然後進行中序走訪並輸出所有節點，接著尋找葉節點並按字母順序輸出。

範例輸入 1：
mathematica
A,B,C,D,,E,F
範例輸出 1：
DBAECF
DEF
範例輸入 2：
mathematica
A,B,C,D,E,,,,,F,G
範例輸出 2：
DBFEGAC
CDFG
總結：
這段程式碼解決了二元樹的建立、走訪以及葉節點的排序輸出問題，並且利用遞歸進行樹的遍歷與操作。
--------------------------------------------
測資
測資00：
輸入：
A,B,C,D,,E,F
輸出：
DBAECF
DEF
測資 01：
輸入：
A,B,C,D,E,,,,,F,G
輸出：
DBFEGAC
CDFG
測資 02：
輸入：
A,B,C,D,E,F,G,H,I,J
輸出：
DBEAFCGHIJ
DEFGHIJ
測資 03：
輸入：
X,Y,Z,,A,B,,C,D
輸出：
YZXABCD
ABC
測資 04：
輸入：
M,N,O,P,Q,R,S,T,U
輸出：
PNMOQRSUT
PQR
這些測資涵蓋了各種情境，包括：

樹形結構中有空節點（例如空字串 ""）。

節點數量較多或較少的情況。

測試程式對不同排列組合的處理能力。



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2