d526 - Binary Search Tree (BST)
題目描述
題目要求建立一個二元搜尋樹 (BST)，並輸出該樹的前序走訪結果。輸入包含多組測試案例，每組案例首先輸入一個整數 N，表示接下來要插入 N 個數字到 BST 中。然後，輸入 N 個整數，這些數字將被插入到 BST 中。輸出為建立好的 BST 的前序走訪序列。
解題思路
程式碼使用遞迴方式建立 BST。put 函數負責將輸入的數字插入到 BST 中。如果輸入的數字大於當前節點的值，則嘗試插入到右子樹；如果小於當前節點的值，則嘗試插入到左子樹。如果當前節點的左右子樹為空，則建立一個新的節點並將其插入到相應的子樹中。pt 函數使用遞迴方式執行 BST 的前序走訪，輸出節點的值。主函數讀取輸入，建立 BST，並輸出前序走訪結果。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是輸入的數字個數。在平均情況下，BST 的高度為 log N，插入和搜尋操作的時間複雜度為 O(log N)。因此，插入 N 個數字的時間複雜度為 O(N log N)。前序走訪的時間複雜度為 O(N)。
- 空間複雜度: O(N)，因為 BST 最壞情況下可能退化為線性鏈表，需要 O(N) 的空間來儲存節點。遞迴調用也會消耗堆疊空間，最壞情況下為 O(N)。
程式碼
#include <iostream>
using namespace std;
typedef struct tree *node;
struct tree{
int val;
node right=NULL;
node left=NULL;
};
void put(int tmp,tree* a){
if(tmp>a->val){
if(a->right==NULL){
node k=new tree;
k->val=tmp;
a->right=k;
return;
}
else{
put(tmp,a->right);
}
}
else if(tmp<a->val){
if(a->left==NULL){
node k=new tree;
k->val=tmp;
a->left=k;
return;
}
else{
put(tmp,a->left);
}
}
}
void pt(tree* a){
if(a!=NULL){
cout << a->val << " ";
pt(a->left);
pt(a->right);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,tmp,x;
while(cin >> n){
node ans=new tree;
cin >> x;
ans->val=x;
--n;
while(n){
--n;
cin >> tmp;
put(tmp,ans);
}
pt(ans);
cout << "\n";
}
}