[問題] zerojudge b346 二元搜尋樹快速建造

看板C_and_CPP作者sunhextfn (阿毛)時間10年前發表 (2015/02/15 14:35), 10年前編輯推噓5(5推 0噓 11→)

留言16則, 5人參與討論串1/2 (看更多)

開發平台(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... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.87.155 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1424010938.A.A4B.html ※ 編輯: sunhextfn (118.166.87.155), 02/15/2015 22:41:16

推

s25g5d4

02/16 00:27, , 1^F

02/16 00:27, 1^F

推

longlongint

02/16 01:58, , 2^F

02/16 01:58, 2^F

→

longlongint

02/16 02:17, , 3^F

02/16 02:17, 3^F