一個有 n 個節點的二元樹，共有 2n 個 Link，但實際上有很多鏈結（Link）是浪費掉。為了改善這個問題，就有引線二元樹（Thread Binary Tree ）的出現。每一個節點都會有左引線跟右引線分別指到其他合適的節點，並且有額外的欄位來辨識是引線還是正常的指標。若把下圖二元樹的引線畫出來，請問節點 I 的右引線及節點 G 的左引線分別指到那個節點？
A節點 E 跟節點 F
B節點 B 跟節點 F
C節點 B 跟節點 C正確答案
D節點 E 跟節點 C
答案與詳解
為什麼答案是 C
依中序走訪 (LVR)：I 為某子樹最右節點，其中序後繼回溯至祖先 B；G 為某子樹最左節點，其中序前驅回溯至祖先 C。符合引線規則。
考點：走訪順序錯誤考點：半對陷阱考點：中序前驅/後繼考點：走訪判讀錯誤
載入中…
