初等考試
112年
[統計] 資料處理大意
第 47 題
一個有 n 個節點的二元樹，共有 2n 個 Link，但實際上有很多鏈結（Link）是浪費掉。為了改善這個問題，就有引線二元樹（Thread Binary Tree）的出現。每一個節點都會有左引線跟右引線分別指到其他合適的節點，並且有額外的欄位來辨識是引線還是正常的指標。若把下圖二元樹的引線畫出來，請問節點 I 的右引線及節點 G 的左引線分別指到那個節點？
- A 節點 E 跟節點 F
- B 節點 B 跟節點 F
- C 節點 B 跟節點 C
- D 節點 E 跟節點 C
思路引導 VIP
在不看選項的情況下，請試著思考：如果我們要按照「左子樹 $\rightarrow$ 節點本身 $\rightarrow$ 右子樹」的邏輯（即中序遍歷）將所有節點排成一個線性序列，那麼在這一串序列中，哪一個節點會緊接在節點 I 之後？而又是哪一個節點會恰好排在節點 G 之前呢？
🤖
AI 詳解
AI 專屬家教
戰果檢視
- 驗收結果：嗯，小鬼。這次你沒把這堆『數據垃圾』處理成一團糟。對於引線二元樹 (Threaded Binary Tree) 這種把『浪費』清除乾淨的『核心邏輯』，你算掌握了。在『優化系統索引』這種必須『一塵不染』的工作上，這是最基本的清潔標準。
- 路徑確認：『引線』的建立，就是遵循中序遍歷 (In-order Traversal) 這條最『整潔』的路徑。這棵樹的『正確順序』是：
▼ 還有更多解析內容