若要在一棵「二元搜尋樹（Binary Search Tree）」中插入一個新值X，已知此二元搜尋樹的定義為：「每個節點的左子樹中所有節點值均小於該節點，右子樹中…

題目

若要在一棵「二元搜尋樹（Binary Search Tree）」中插入一個新值X，已知此二元搜尋樹的定義為：「每個節點的左子樹中所有節點值均小於該節點，右子樹中所有節點值均大於該節點」。下列敘述何者正確？ A. 先比較X 與根節點，若X 較大則往左子樹走，否則往右子樹走 B. 先比較X 與根節點，若X 較大則往右子樹走，否則往左子樹走 C. 只要找到葉節點就立即插入，不必比較數值大小 D. 對根節點做旋轉（rotation），再將X 插入葉節點

官方答案

• 答案：B. 先比較X 與根節點，若X 較大則往右子樹走，否則往左子樹走

解析

二元搜尋樹的核心性質是「左小右大」：任一節點的左子樹所有值都小於該節點，右子樹所有值都大於該節點。因此插入 X 時，從根節點開始逐層比較：若 X 大於目前節點就往右子樹移動，若 X 小於目前節點就往左子樹移動，直到遇到空指標為止，再將 X 建立成新的葉節點。選項 A 把左右方向說反了，與 BST 定義矛盾；選項 C 忽略比較，插入後便不再具備 BST 性質；選項 D 的旋轉是平衡樹（如 AVL、Red-Black Tree）在失衡後調整結構的手段，並非 BST 插入的必要步驟。

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

官方資料

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

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