打印

[ICT] A question about Inorder traversal

HSH

學院師父

Rank: 4

發短消息
加為好友
當前離線

1^# 大中小發表於 2014-1-26 12:07 PM (第 3735 天) 只看該作者

A question about Inorder traversal

題目：
如圖所示之樹，將其二元化後做中序追蹤(inorder traversal)
則所拜訪的節點順序為
(A) ABCDEFGHI (B) EFBCGHIDA (C)EBFACGHID (D) EBFCAGHDI

ANS: B

Answer怎係(B)???(B)唔係"postorder traversal"???

感覺(D)較正確???

請問各位小卒，答案真係(B)咩??

TOP

tony625

得道高僧

Rank: 14

發短消息
加為好友
當前離線

2^# 大中小發表於 2014-1-26 03:57 PM (第 3735 天) 只看該作者

[隱藏]

errata from internet: the answer is (C) EBFACGDHI
step 1:
　　　　　Ａ
　　　／　｜　＼
　　Ｂ　　Ｃ　　Ｄ
　／　＼　　　／｜＼
Ｅ　　　Ｆ　Ｇ　Ｈ　Ｉ
step 2:
　　　　　Ａ
　　　／　｜　＼
　　Ｂ－－Ｃ－－Ｄ
　／　＼　　　／｜＼
Ｅ－－－Ｆ　Ｇ－Ｈ－Ｉ
step 3:
　　　　　Ａ
　　　／
　　Ｂ－－Ｃ－－Ｄ
　／　　　　　／
Ｅ－－－Ｆ　Ｇ－Ｈ－Ｉ
step 4:
　　　　Ａ
　　　／
　　Ｂ
　／　＼
Ｅ　　　Ｃ
　＼　　　＼
　　Ｆ　　　Ｄ
　　　　　／
　　　　Ｇ
　　　　　＼
　　　　　　Ｈ
　　　　　　　＼
　　　　　　　　Ｉ