依序輸入六筆資料，下列何者所建的二元搜尋樹 (binary search tree) 層數最少？ (A) 3, 2, 5, 4, 6, 1 (B) 6, 5, 4, 3, 2, 1 (C) 1, 2, 3, 4, 5, 6 (D) 4, 1, 5, 3, 6, 2

正確答案為 A。選項(A)的插入順序能建構出最平衡的二元搜尋樹，使其層數最少（僅3層）。 (B) 遞減序列會使所有新節點皆成為前一個節點的左子節點，形成向左傾斜的鏈狀樹，層數達到最多的6層。 (C) 遞增序列會使所有新節點皆成為前一個節點的右子節點，形成向右傾斜的鏈狀樹，層數同樣達到最多的6層。

國中教甄｜資訊科技資訊科技102 年第 7 題單選題

依序輸入六筆資料，下列何者所建的二元搜尋樹 (binary search tree) 層數最少？

A3, 2, 5, 4, 6, 1正確答案

B6, 5, 4, 3, 2, 1

C1, 2, 3, 4, 5, 6

D4, 1, 5, 3, 6, 2

答案與詳解

正確答案

選項(A)的插入順序能建構出最平衡的二元搜尋樹，使其層數最少（僅3層）。

A3, 2, 5, 4, 6, 1✓ 正確

B6, 5, 4, 3, 2, 1✕ 錯誤

遞減序列會使所有新節點皆成為前一個節點的左子節點，形成向左傾斜的鏈狀樹，層數達到最多的6層。

C1, 2, 3, 4, 5, 6✕ 錯誤

遞增序列會使所有新節點皆成為前一個節點的右子節點，形成向右傾斜的鏈狀樹，層數同樣達到最多的6層。

D4, 1, 5, 3, 6, 2✕ 易錯陷阱

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解