开发平台(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...