使用下列數字序列：20、2、3、4、7、6、9、1、5、8，依序輸入建立一個二元搜尋樹（binary search tree），下列敘述何者錯誤？

題目

使用下列數字序列：20、2、3、4、7、6、9、1、5、8，依序輸入建立一個二元搜尋樹（binary search tree），下列敘述何者錯誤？ A. 由根節點出發使用前序（preorder）方式走訪此二元搜尋樹，輸出為20, 2, 1, 3, 4, 7, 6, 5, 9, 8 B. 節點1 和節點3 的父節點相同 C. 節點6 位於節點9 的左子樹 D. 若最後再新增一個數字10，此二元搜尋樹的高度不變

官方答案

• 答案：C. 節點6 位於節點9 的左子樹

解析

依序插入後，20 為根，2 為 20 左子、1 為 2 左子、3 為 2 右子，4、7 依次為右鏈，6 為 7 左子、5 為 6 左子，9 為 7 右子、8 為 9 左子。前序走訪為 20,2,1,3,4,7,6,5,9,8，故 A 正確；1 與 3 的父節點同為 2，B 正確。節點 6 是 7 的左子，並不在節點 9 的子樹中（9 的左子為 8），故 C 錯誤。新增 10 會沿 20→2→3→4→7→9 落到 9 的右子，深度與既有最深的 5、8 同為 6，樹高不變，D 正確。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。