Q184.
下列有關延伸二元樹（Extended Binary Tree）的敘述，何者是正確的？
電腦軟體設計共同科目 · 乙級 · Q184
難易度分析
3 / 5
本題要求考生區分不同二元樹結構對路徑長度的影響，需精確掌握完整二元樹與歪斜樹在路徑長度上的極值差異，以及內外路徑長度之間的數學關聯性。
正確答案：③當二元樹為完整二元樹（Complete Binary Tree）時，具有最小之內路徑長度（Internal Path Length）
③ 當二元樹為完整二元樹（Complete Binary Tree）時，具有最小之內路徑長度（Internal Path Length）:完整二元樹結構最為平衡，所有節點盡量靠近根節點，因此能達到最小內路徑長度，此為資料結構中的重要性質。
錯誤選項解析
- ① 當二元樹為歪斜樹（Skewed Tree）時，具有最小之內路徑長度（Internal Path Length）:歪斜樹會使所有節點集中在單一支路，導致從根節點到各節點的距離總和最大，因此具有最大內路徑長度而非最小。
- ② 當二元樹為歪斜樹（Skewed Tree）時，具有最小之外路徑長度（External Path Length）:歪斜樹同樣會使外部節點（擴充的空指標）位於最深層，造成外路徑長度最大化，而非最小化。
- ④ 當內路徑長度（Internal Path Length）愈大時，外路徑長度（External Path Length）則愈小:內路徑長度 I 與 外路徑長度 E 的關係為 E = I + 2n（n 為內部節點數），兩者呈正相關而非負相關。
Learning Tip
"本題核心考點為延伸二元樹的路徑長度性質。切記：完整二元樹最小化路徑長度，歪斜樹最大化路徑長度；且內、外路徑長度滿足 E = I + 2n 的固定關係，兩者同增同減，此為資料結構檢定常見陷阱。"
學員答題分佈
①當二元樹為歪斜樹（Skewed Tree）時，具有最小之內路徑長度（Internal Path Length）0%
②當二元樹為歪斜樹（Skewed Tree）時，具有最小之外路徑長度（External Path Length）0%
③當二元樹為完整二元樹（Complete Binary Tree）時，具有最小之內路徑長度（Internal Path Length）0%
④當內路徑長度（Internal Path Length）愈大時，外路徑長度（External Path Length）則愈小0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
建立一個含有五個內節點(Internal Node)的延伸二元樹(Extended Binary Tree)，使此延伸二元樹的外路徑長(External Path Length)為最小，則此最小外路徑為何？
假設T 是一個延伸二元樹(Extended Binary Tree)，內路徑長為25，外部節點有13 個，則此外路徑長度為何？
下圖為一延伸二元樹(Extended Binary Tree)，其中圓形節點表內節點（Internal Node），方形節點代表外節點（External Node），其外路徑長(External Path Length) 是多少？
假設T 是一個延伸二元樹(Extended Binary Tree)，外路徑長為80，外部節點有13 個，則此內路徑長度為何？
下圖為一個二元樹(Binary Tree)，下列之描述何者是正確的？