如果一個二元搜尋樹以後序(postorder)方式走訪(traversal)的結果為一個嚴格遞增數列(即:x1 < x2< … < xn),1 < n,則下列敘述何者恆為正確?
A此二元搜尋樹為歪向左傾的樹(left skewed,即所有非樹葉節點都只有左子)正確答案
B此二元搜尋樹為歪向右傾的樹(right skewed,即所有非樹葉節點都只有右子)
C此二元搜尋樹既不為歪向右傾,亦不為歪向左傾
D此二元搜尋樹的高度必為二
答案與詳解
後序走訪順序為「左子樹→右子樹→根節點」。若結果為遞增數列,代表最後拜訪的「根節點」是整棵樹的最大值。在二元搜尋樹(BST)中,要讓根節點成為最大值,就絕對不能有右子樹(因為右子樹的值必大於根)。套用到每個節點,整棵樹只能有左子樹,即為歪向左傾的樹。
