作者koehie (開喜烏龍茶)
看板Grad-ProbAsk
標題[問題] 前後序求二元樹
時間Thu Apr 9 21:48:14 2009
Given a binary tree T whose pre-order and post-order sequence are "9, 8 ,6, 1
4, 7, 5, 3, 2" and "1, 4, 6, 7, 8, 3, 2, 5, 9" respectively.
(a) Draw T.
(b) Is T unique ? Why ?
(c) Is T a max heap ? Why ?
我知道只給予前中或後中就可以畫出一顆二元樹，但是如果只給前序和後序，那麼怎麼
畫出這一顆二元樹呢 ?
請指教了，謝謝。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.18.32.143
1F：推 liamgallager:照畫= =不過2元樹不唯一 就盡量去試試看 04/09 21:55
2F：→ koehie:我剛剛試著畫有畫出來，畫來來也是一個 Max Heap ，但是為 04/09 22:29
3F：→ koehie:什麼呢 ? 這要怎麼解釋阿 ? 因為這一顆二元樹符合 Heap 所 04/09 22:30
4F：→ koehie:定義的特性嗎 ? 04/09 22:30
5F：推 sunneo:假設給予的資料是可排序的(比如數字或者英文字) 04/09 23:03
6F：→ sunneo:那麼它就已經暗示有中序的存在 04/09 23:03
7F：→ sunneo:但你只能利用這結果畫圖 不能拿來說他一定是唯一 04/09 23:05
8F：→ sunneo:因為可排序是自己假設的 (如果題目有給才是唯一) 04/09 23:05