對一個有十二個節點的二元搜尋樹（Binary Search Tree）作後序訪問（Postorder Traversal），並依序輸出訪問節點的數值，其結果如下（次序由左至右）：3, 4, 6, 5, 8, 15, 19, 18, 16, 12, 24, 20。在此樹中有多少個節點其左子節點（Left Child）及右子節點（Right Child）皆有數值？

正確答案為 B。後序最後一個是根(20)，BST左子樹<根<右子樹，遞迴還原二元樹後計算有雙子的節點。

【109 普考-電子工程】計算機概要第21題：對一個有十二個節點的二元搜尋樹（Binary… 答案與詳解

B

正確答案

後序最後一個是根(20)，BST左子樹<根<右子樹，遞迴還原二元樹後計算有雙子的節點。

後序最後為20（根）；<20的左子樹為{3,4,6,5,8,15,19,18,16,12}，>20的右子樹為{24}。左子樹根為12，其左子為8、右子為16；8只有左子5，16有左子15、右子18；5有左子4、右子6。因此同時有左右子節點者為20、12、5、16，共4個。

載入中…