回復 1# may
//#include <iostream>
//#include <queue>
#include <bits/stdc++.h>
using namespace std;
// 節點結構
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 插入節點到 BST
TreeNode* insert(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
// 階層（Level-Order）走訪
void levelOrder(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
cout << "Level-order:";
bool first = true;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (first) {
cout << node->val;
first = false;
} else {
cout << " " << node->val;
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << endl;
}
// 前序（Preorder）走訪
void preorder(TreeNode* root, bool isFirst) {
if (!root) return;
if (isFirst)
cout << root->val;
else
cout << " " << root->val;
preorder(root->left, false);
preorder(root->right, false);
}
int main() {
int N;
cin >> N;
TreeNode* root = nullptr;
for (int i = 0; i < N; ++i) {
int val;
cin >> val;
root = insert(root, val);
}
levelOrder(root);
cout << "Preorder:";
preorder(root, true);
cout << endl;
return 0;
}
---------------------------------------------------------------
程式碼說明：
節點結構 (TreeNode)：
定義一個 TreeNode 結構，包含 val（節點值）、left（左子樹）和 right（右子樹）。
插入節點 (insert)：
遞迴插入節點到 BST，若 val 小於根節點，則插入左子樹，否則插入右子樹。
階層走訪 (levelOrder)：
使用 queue 來進行 BFS（廣度優先搜尋）。
逐層輸出節點值。
前序走訪 (preorder)：
遞迴方式，按照「根 -> 左 -> 右」順序輸出節點值。
主程式 (main)：
讀取輸入數值並建立 BST。
執行階層走訪和前序走訪，並輸出結果。
這段程式碼可正確建立 BST 並依題目要求輸出走訪順序。
---------------------------------------------
測資:
測試資料00：
輸入：
5
7 9 2 5 10
預期輸出：
Level-order:7 2 9 5 10
Preorder:7 2 5 9 10
測試資料 01：
輸入：
8
25 31 5 9 18 26 51 99
預期輸出：
Level-order:25 5 31 9 26 51 18 99
Preorder:25 5 9 18 31 26 51 99
測試資料 02：
輸入：
6
50 30 70 20 40 60
預期輸出：
Level-order:50 30 70 20 40 60
Preorder:50 30 20 40 70 60
測試資料 03：
輸入：
7
15 10 20 8 12 17 25
預期輸出：
Level-order:15 10 20 8 12 17 25
Preorder:15 10 8 12 20 17 25
測試資料 04：
輸入：
10
45 30 60 20 35 50 70 10 25 40
預期輸出：
Level-order:45 30 60 20 35 50 70 10 25 40
Preorder:45 30 20 10 25 35 40 60 50 70
這些測試資料涵蓋了不同的樹形結構，包括左右子樹的不同排列，確保程式能正確處理各種情況！ |
