問題詳情

18 對一個有 12 個節點的二元搜尋樹（Binary Search Tree）作後序訪問（Postorder Traversal），並依序輸出訪問節點的數值，其結果如下（次序由左至右）：3, 4, 6, 5, 8, 15, 19, 18, 16, 12, 24, 20。在此樹中兩個節 點之間的路徑（Path）最多含有多少個邊（Edge）？
(A)6
(B)7
(C)8
(D)9

參考答案

答案：B
難度：適中0.428571
統計：A(0),B(3),C(1),D(3),E(0)

用户評論

【San Hsien】評論

二元搜尋樹：1.若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；2.若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；3.任意節點的左、右子樹也分別為二元搜尋樹；4.沒有鍵值相等的節點。後序訪問為左子樹-右子樹-根。3個節點一組以條件1,2比較決定為左子樹、右子樹、父節點，所有節點分左右子樹組以條件1,2比較，適當降低節點高度，(例：於決定16位置時降至15的父節點位置、決定12位置時降至8的父節點位置、決定20位置時降至12的父節點位置)可得：      20    12  ...