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

答案：登入後查看
統計： A(38), B(142), C(56), D(38), E(0) #1484871

詳解 (共 1 筆)

#2847659

二元搜尋樹：

1.若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；

2.若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；

3.任意節點的左、右子樹也分別為二元搜尋樹；

4.沒有鍵值相等的節點。


後序訪問為左子樹->右子樹->根。

3個節點一組以條件1,2比較決定為左子樹、右子樹、父節點，

所有節點分左右子樹組以條件1,2比較，適當降低節點高度，

(例：於決定16位置時降至15的父節點位置、決定12位置時降至8的父節點位置、決定20位置時降至12的父節點位置)

可得：

                                20

                      12                24

              8                16

         5                15       18

    4        6                            19

3

3到19有7個邊

17
0