標題: [ICT] 有關Traversal的問題 [打印本頁]

---

作者: HSH    時間: 2014-1-26 11:43 AM     標題: 有關Traversal的問題

題目：
一棵二元樹(binary tree)
以中序搜尋(inorder traversal)拜訪的順序為ECFBDAHG
以後序搜尋(postorder traversal)拜訪的順序為EFBCHGAD
則以前序搜尋(preorder traversal)拜訪的順序為
(A) ABDGCEHF
(B) ABCDEFGH
(C) DECFBAHG
(D) DCEBFAGH

答案是(D)

不過我試著畫了一下，仍覺怪怪的
Inorder:


Postorder:


兩個好像不大一樣
若以Inorder畫的來推估Preorder應為 DCEBFHAG
若以Postorder畫的來推估Preorder應為 DCEBFAHG

但答案為何為(D)呢？
還是我有畫錯呢？
希望各位小卒幫我解個惑一下，說不定是我搞錯了，謝謝各位！

---

作者: tony625    時間: 2014-1-26 03:39 PM

inorder (LVR): ECFB-D-AHG
postorder (LRV): EFBC-HGA-D
Ｄ
　＼
　　Ａ
　　　＼
　　　　Ｇ
　　　／
　　Ｈ

---

作者: HSH    時間: 2014-1-30 07:31 PM

原來還有這樣的走法
沒有想到
感謝您的解析，很有用

---

歡迎光臨 小卒資訊論壇 (http://lsforum.net/board/)

Powered by Discuz! 6.0.0