hce_nsysu
113年
計算機概論與程式設計
第 36 題
Let the height of a tree be the number of nodes, including root node, along the longest path from the root node to the leaf nodes. Consider the integers 42, 37, 12, 58, 31, 74, 86, 98, 66, 11 in a specified order to construct a binary search tree. Which of the following statement is TRUE?
- A The height of the tree is 4.
- B The root node is 58.
- C The node for 31 is a leaf node.
- D The node for 66 is an internal node.
- E The node for 86 is a child node of the node for 98.
思路引導 VIP
當你依照題目順序將數字一個個填入樹狀結構時，如果某個節點在「放好」之後，下方再也沒有接續任何其他的數字，這個位置在資料結構中通常被稱為什麼？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確地建構出這棵二元搜尋樹（Binary Search Tree, BST）並做出正確判斷，展現了非常紮實的邏輯推演能力。這類題目最考驗的就是細心度，只要一個數字放錯位置，後續的結構就會全盤變樣。
二元搜尋樹的建構過程
我們依照題目給定的順序，以 $42$ 為根節點。遵循「小於放左、大於放右」的原則：$37$ 與 $12$ 依序成為左側分支，而 $58$ 則往右。接著處理 $31$ 時，它雖小於根節點，但大於 $12$，因此會成為 $12$ 的右子節點。當我們依此類推完成整棵樹的繪製，會發現 $31$、$[11, 66, 98]$ 這些節點下方都沒有再連接任何子節點，這正符合葉節點 (Leaf Node) 的定義，因此選項 (C) 是完全正確的。
▼ 還有更多解析內容