zerojudge連結http://zerojudge.tw/ShowProblem?problemid=c101
acm online judge連結 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=58
內容 :
樹狀結構在電腦科學的許多領域中都相當重要。本問題牽涉到建立樹及走訪樹。
給你一二元樹,你的任務是寫一個程式來列印依「階層(level-order)」走訪的結果。在本問題中,二元樹的每個節點含有一個正整數,並且節點的數目最少1個,最多256個。
在「階層」走訪中,依階層從低到高,同階層從左到右的次序來列印。例如以下的二元樹階層走訪的結果為:5, 4, 8, 11, 13, 4, 7, 2, 1
在本問題中,二元樹以節點來表示。每個節點以一對(n,s)來表示。n代表此節點的值,s為一字串,代表從根節點到達此 節點的路徑。其中L代表往左,R代表往右。所以在上方的圖中內容為13的節點其表示法為(13,RL),而內容為2的節點其表示法為(2,LLR),而根 節點為(5,)。
輸入說明 :
輸入含有多組測試資料。每組測試資料為若干節點的集合。各節點間以white space(包含空白、換列等字元)分隔。注意:在各節點內(也就是左刮號到又刮號之間)不會有white space。當遇到一()的節點,代表該組測試資料結束。請參考Sample Input。
輸出說明 :
對每一組測試資料,如果輸入的節點可以正常的構成一二元樹的話,請輸出按「階層」走訪的結果。如果輸入的節點無法正常的構成一二元樹的話,也就是說有某些該有的節點沒有給,或重複給(同一路徑有2個節點),請輸出not complete。請參考Sample Output。
範例輸入 :
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (2,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
範例輸出 :
5 4 8 11 13 4 7 2 1
not complete
not complete
提示 :
* 中文翻譯:Lucky 貓
出處 :
ACM 122
解題策略
建立樹,使用queue實作level order走訪