開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
dev-c++
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question)：
小弟只會用插入法建造BST，不知有沒有其他方法快速建造BST?
題目:
http://zerojudge.tw/ShowProblem?problemid=b346
餵入的資料(Input)：
預期的正確結果(Expected Output)：
錯誤結果(Wrong Output)：
程式碼(Code)：(請善用置底文網頁, 記得排版)
http://codepad.org/tyKZQLPI
#include <iostream>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
};
void pre_order(Node* ptr){
cout<< ptr->data <<' ';
if(ptr->left)
pre_order(ptr->left);
if(ptr->right)
pre_order(ptr->right);
}
int main(){
int N;
Node* nodes=NULL;
while(cin>>N){
nodes=new Node[N];
Node* head=&nodes[0];
Node* ptr=head;
cin>> head->data;
head->left=NULL;
head->right=NULL;
for(int i=1;i<N;++i,ptr=head){
cin>> nodes[i].data;
while(1){
if(nodes[i].data < ptr->data){
if(ptr->left)
ptr=ptr->left;
else{
ptr->left=&nodes[i];
ptr->left->left=NULL;
ptr->left->right=NULL;
break;
}
}
else{
if(ptr->right)
ptr=ptr->right;
else{
ptr->right=&nodes[i];
ptr->right->left=NULL;
ptr->right->right=NULL;
break;
}
}
}
}
pre_order(head);
cout<<endl;
delete[] nodes;
nodes=NULL;
}
return 0;
}
補充說明(Supplement)：
Node的設計是:
struct Node{
int data;
Node* left;
Node* right;
};
因為題目會先告訴你總共有N個數字，所以我先創造N個Node
(這樣在delete時比較方便，雖然不是正統作法)
nodes=new Node[N];
如此第i個數字會存在nodes[i-1].data;
之後是重點了...如何快速建立BST?
我只會從樹頭開始比較，對於第i個數字，
如果比較小就往左邊走，如果左邊沒有資料(left==NULL)就把left設成&nodes[i-1]
如果比較大...方法雷同。
這是沒啥創意的設計
所以就TLE了 Orz...