地方政府公務人員四等-電子工程類科計算機概要108 年第 13 題單選題
如果一個二元搜尋樹以後序(postorder)方式走訪(traversal)的結果為一個嚴格遞增數列(即: $x_{1}<x_{2}<\ldots<x_{n}$ ),1<n,則下列敘述何者恆為正確?
A此二元搜尋樹為歪向左傾的樹(left skewed,即所有非樹葉節點都只有左子)正確答案
B此二元搜尋樹為歪向右傾的樹(right skewed,即所有非樹葉節點都只有右子)
C此二元搜尋樹既不為歪向右傾,亦不為歪向左傾
D此二元搜尋樹的高度必為二
A正確答案
BST後序走訪(左-右-根)若為遞增,代表最後印出的「根節點」是最大值,這意味著整棵樹不能有右子樹,必定是向左傾斜的樹。
為什麼答案是 A
後序走訪順序為「左子樹→右子樹→根節點」。若結果為遞增數列,代表最後拜訪的「根節點」是整棵樹的最大值。在二元搜尋樹(BST)中,要讓根節點成為最大值,就絕對不能有右子樹(因為右子樹的值必大於根)。套用到每個節點,整棵樹只能有左子樹,即為歪向左傾的樹。
載入中…
完整詳解
Pro · 無限重點 BST後序走訪(左-右-根)若為遞增,代表最後印出的「根節點」是最大值,這意味著整棵樹不能有右子樹,必定是向左傾斜的樹。
後序走訪最後印根節點。數列遞增代表根節點是最大值。在二元搜尋樹中,根節點若為最大值,代表它沒有右子樹,故必為左傾樹。
逐選項分析
A✓ 正確
後序走訪順序為「左子樹→右子樹→根節點」。若結果為遞增數列,代表最後拜訪的「根節點」是整棵樹的最大值。在二元搜尋樹(BST)中,要讓根節點成為最大值,就絕對不能有右子樹(因為右子樹的值必大於根)。套用到每個節點,整棵樹只能有左子樹,即為歪向左傾的樹。
B✕ 陷阱
若是歪向右傾的樹(只有右子樹),其後序走訪順序會先走到最深處的右子葉,然後一路往上印回根節點。因為 BST 右邊的值較大,這樣印出來的結果會是「嚴格遞減」數列,而非遞增。
C✕
根據推論,為了滿足後序走訪遞增的條件,該樹必定是歪向左傾的樹,不可能「既不左傾也不右傾」。
D✕
只要是歪向左傾的樹,無論高度為多少(n 可以是任意大於 1 的整數),其後序走訪都會是嚴格遞增數列,因此高度不必然限制為二。
二元搜尋樹 (BST) 極端型態走訪結果比較
| 樹的型態 | 中序走訪 (L-V-R) | 前序走訪 (V-L-R) | 後序走訪 (L-R-V) |
|---|
| 一般 BST | 嚴格遞增 | 無固定規律 | 無固定規律 |
| 歪向左傾 (Left Skewed) | 嚴格遞增 | 嚴格遞減 | 嚴格遞增 |
| 歪向右傾 (Right Skewed) | 嚴格遞增 | 嚴格遞增 | 嚴格遞減 |
考生通常死背「BST 走訪出來是遞增數列」,但那是「中序走訪 (Inorder)」的專利!本題刻意考「後序走訪 (Postorder)」,必須透過走訪順序 (L-R-V) 反推根節點為最大值,進而推導出樹的幾何形狀。