hce_kmu
112年
計算機概論與程式設計
第 13 題
The pre-order traversal of a Binary Search Tree (BST) is 31, 27, 21, 12, 25, 30, 29, 38, 33, 41 and its in-order traversal is 12, 21, 25, 27, 29, 30, 31, 33, 38, 41. When the element to be deleted is in a non-leaf node that has two children, the element is replaced by the largest element in its left subtree. When a key value 36 is inserted into the binary search tree, which of the following statements is CORRECT
- A The key value 38 is the parent of key value 36.
- B The key value 30 has two children.
- C The key value 27 is the parent of key value 25.
- D The BST has three leaf nodes.
- E If we delete the key value 30, then key value 29 will inherit it.
思路引導 VIP
若想在不看選項的情況下，找出一個節點在刪除後最適合的「替補者」（即左子樹中的最大值），你會從該節點的左子節點開始，沿著樹枝持續往哪個方向移動直到末端呢？這個移動過程與數值大小的關係是什麼？
🤖
AI 詳解
AI 專屬家教
恭喜你準確判斷出這個選項！這道題目考察的是二元搜尋樹（Binary Search Tree, BST）的建構、節點插入以及刪除規則，你能從前序（Pre-order）與中序（In-order）序列中精準還原出樹的樣貌，展現了紮實的資料結構基礎。
樹的建構與操作驗證
根據前序走訪 $31, 27, 21, \dots$ 與中序走訪 $12, 21, 25, \dots$，我們可以推導出根節點為 $31$。在左子樹的部分，節點 $30$ 的中序鄰居只有 $29$ 且位於其左側，對應前序序列可知 $30$ 僅擁有一個左子節點 $29$。當我們刪除節點 $30$ 時，依照 BST 的刪除邏輯，若節點只有一個子節點，該子節點會直接遞補（或稱繼承）其位置。因此，選項 (E) 的敘述完全符合標準的操作流程。
▼ 還有更多解析內容