iT邦幫忙

0

二元樹

一顆二元樹以中序追蹤拜訪的順序為ECFBDAHG,另以後序追蹤拜訪的順序為EFBCHGAD,則以前序追蹤拜訪的順序為(A)ABDGCEHF (B)ABCDEFGH (C)DECFBAHG (D)DCEBFAHG

這類型的題目 充滿疑惑
感謝回答

tryit iT邦研究生 4 級 ‧ 2021-03-08 13:11:57 檢舉
請問你疑惑的點在哪裡?這樣的敘述有點難回答。
上次幫你畫的圖沒問題的話幫忙給個最佳解答,謝謝
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
0
koro_michael
iT邦新手 2 級 ‧ 2021-03-09 14:02:56
最佳解答

中序為ECFBDAHG
後序為EFBCHGAD

後序最後一個元素一定是根,也就是 D 是根

       D

接下來看中序

D 把中序一分為二,左半部 ECFB 右半部 AHG

左半部 = 左半邊的節點
右半部 = 右半邊的節點

=====================================

先從左半部開始看

中序為ECFB
後序為EFBC(去掉 D 及右半部的元素)

後序最後一個元素為 C,代表左半部的根是 C

       D
      /
     C

C 把中序一分為二,左半部 E 右半部 FB

因為左半部只剩下一個元素,直接畫上去

       D
      /
     C
    /
   E

剩下的元素為右半部的 FB

中序為FB
後序為FB(去掉 C 及 E)

後序最後一個元素為 B,代表右半部的根是 B

       D
      /
     C
    / \
   E   B

剩下一個 F 在 B 的左邊,直接畫上去

       D
      /
     C
    / \
   E   B
      /
     F

=====================================

剩下右半的節點,步驟都一樣

中序為AHG
後序為HGA

後序最後一個元素為 A,代表右半部的根是 A

       D
      / \
     C   A
    / \
   E   B
      /
     F

剩下的元素為右半部的 HG

中序為HG
後序為HG(去掉 A)

後序最後一個元素為 G,代表右半部的根是 G

       D
      / \
     C   A
    / \   \
   E   B   G
      /
     F

剩下一個 H 在 G 的左邊,直接畫上去

       D
      / \
     C   A
    / \   \
   E   B   G
      /   /
     F   H

如果還是不會就放棄這一類型的題目吧

0
tryit
iT邦研究生 4 級 ‧ 2021-03-08 13:33:20

首先,不知道你知不知道前中後序走訪是如何去運行的,不知道的話你可以看這篇。
前輩已經有作出解釋了。
https://ithelp.ithome.com.tw/articles/10205571
接下來看題目給的條件,他已有說
中序為ECFBDAHG
後序為EFBCHGAD
可知root為D(後序尾),右有AHG,左有ECFB(中序透過root左右區分)
最左下為E,那接下來就是CFB這三個東西要做排列,這邊建議開始進行繪圖去判斷,當然你必須先理解中序跟後序的遍歷流程,那理論上圖會畫出來長這樣
空空D
空C
空空B
空F
E
右邊我不管,反正答案就出來了。

看更多先前的回應...收起先前的回應...

我畫出來發現跟答案沒有一個是符合的/images/emoticon/emoticon02.gif

       D
      / \
     C   A
    / \   \
   E   B   G
      /   /
     F   H
tryit iT邦研究生 4 級 ‧ 2021-03-08 14:49:50 檢舉

代表你畫錯啊....
你E可以接F底下阿

E 接 F 底下按照中序不是應該會變成 CEFBD 嗎?

左分支空的就直接從 C 開始

我認真覺得D選項最後兩個肯定寫反了....

不好意思,沒寫清楚,解答是D,我的疑惑是怎麼解而已,因為這種類型的題目,實在看不太懂怎解

tryit iT邦研究生 4 級 ‧ 2021-03-09 15:40:19 檢舉

個人覺得,像這種類考試題目,找不到你認為最正確的,就找最近的,畢竟C肯定不對。

0
海綿寶寶
iT邦大神 1 級 ‧ 2021-03-08 16:06:06

答案是 D
10年前就有人回答了
/images/emoticon/emoticon10.gif

最新此題出處
110年一次考上銀行 計算機概論(含網路概論)
題目在第 140 頁 第5題
答案在第 142 頁,答案是D。此二元樹的前序追蹤為 DCEBFAHG

不服去找出版社辯
/images/emoticon/emoticon38.gif

看更多先前的回應...收起先前的回應...

D的答案最後兩個應該是寫反了吧,樹畫出來就是這個樣子,最後怎麼會是HG

       D
      / \
     C   A
    / \   \
   E   B   G
      /   /
     F   H

不好意思,沒寫清楚,解答是D,我的疑惑是怎麼解而已,因為這種類型的題目,實在看不太懂怎解

解法就在這裡
看懂解法之前一定要先看懂的基本觀念在這裡

因為我也是買這本書,但解答沒寫怎來的,所以才來發問的,囧

謝謝你的回答,感謝

看懂解法之前一定要先看懂的基本觀念在「這裡」<--這藍色的字是超連結,你有點來看嗎?

其實上面所有藍色的字都是超連結,你知道吧...

有喔,我知道,兩個超連結我已經有看過了,還在練習,我只是對於這題的解答,課本沒附而已,謝謝~

我要發表回答

立即登入回答