伊莉討論區

標題: 一串數字依前序中序後序排列! [打印本頁]

作者: coolhuang829 時間: 2013-5-12 07:04 PM 標題: 一串數字依前序中序後序排列!

給予一串數字，利用binary tree 讓他依 INFIX 、PREFIX 、POSTFIX 排列

5031 67 88 2 35 21 48 8 27 49 //the elements ofbinary search tree

INFIX 2 8 21 27 31 35 48 49 50 67 88 //output the infix notation in the output file

PREFIX 50 31 2 21 8 27 34 48 49 67 88 //output the prefix notation in the output file

POSTFIX 8 27 21 2 49 48 35 31 88 67 50 //output the postfix notation in the output file

INSERT //insert the following number into the tree

370 //the numbers need to be inserted

INFIX //…

謝謝~

作者: snowflying 時間: 2013-5-12 07:48 PM

所以是要做什麼和求什麼? Binary Tree? Code?
第一行數字後的 INFIX PREFIX POSTFIX 是給定的?
不然只給一串數字，binary tree 有可能有好幾種

作者: coolhuang829 時間: 2013-5-13 05:57 PM

snowflying 發表於 2013-5-12 07:48 PM
所以是要做什麼和求什麼? Binary Tree? Code?
第一行數字後的 INFIX PREFIX POSTFIX 是給定的?
不然只給一 ...

只有第一行是給定還有insert 其他就是要用 Binary Tree 來求我需要code 謝謝...

作者: snowflying 時間: 2013-5-13 06:16 PM

coolhuang829 發表於 2013-5-13 05:57 PM
只有第一行是給定還有insert 其他就是要用 Binary Tree 來求我需要code 謝謝... ...

只給一串數字這樣 INFIX PREFIX POSTFIX BINARY-SEARCH-TREE 都不唯一吧
題目是任意解都可?

作者: 撲殺兔 時間: 2013-5-14 01:29 PM

題目是不是沒寫清楚，我看測資是 binary search tree 喔。

然後 PREFIX 那裏的 34 應該是 35吧 ?

作者: swordfish000 時間: 2013-6-2 05:52 AM

本帖最後由 swordfish000 於 2013-6-2 06:03 AM 編輯

50 31 67 88 2 35 21 48 8 27 49==>求INFIX(中序排列)
剛開始抓35當頂節點  比35小往左丟  比35大往右丟  所以樹會變成
31 2 21 8 27 35 50 67 88 48 49
同上步驟  分別處理31 2 21 8 27 (左邊)和  50 67 88 48 49(右邊)
2 8 21 31 27 35 50 67 48 49 88
做到最後順序就變成
2 8 21 27 31 35 48 49 50 67 88

這是簡單的左遞迴和右遞迴概念

這是我之前做類似的作業給你參考
[attach]91055608[/attach]
前序就是抓第一個當結點後序就是抓最後一個當結點
這種樹做完都會有很多空白  屬於非完整2元樹
補充

中序遍歷的規則就是把根放在中間，從左到右。即左——根——右。

以下圖為例：

則是先遍歷左子樹（即以B為根的子樹），再遍歷根結點，最后遍歷右子樹(以E為根結點的子樹)。

首先在遍歷左子樹（以B為根的子樹）的時候，同樣用中序遍歷的規則（左——根——右），此時，我們把左子樹當成一個獨立的樹來看。那麼在這個左子樹里面，遍歷的順序就應該是CBD。（暫且把結果放一邊）

然后遍歷根結點，就是輸出A（根結點就是A嘛！）

最后遍歷右子樹（以E為根的子樹），按照前面第一步的方法，暫且把這個右子樹當成一個獨立的樹來看，遍歷結果應該是EF(因為在這個子樹里，它的左子樹為空)。

最后一步，我們把上面三步的結果順序串聯起來，就可以得到遍歷的結果：CBDAEF

PS:不管哪一種遍歷，只要把各個子樹當成一個“大結點”來看。在各個“大結點”內部又各自依相應的遍歷方式遍歷，最終將結果返回即可得到所要的遍歷結果（呃！不知道會不會說復雜了！總之就是一個遞歸的過程！你要好好体會一下！）

[attach]91055614[/attach]

歡迎光臨伊莉討論區 (http://a401.file-static.com/)