試題詳解

15 二元搜尋樹是建立在樹節點鍵值的大小上。左子樹的所有鍵值均小於樹根的鍵值，右子樹所有鍵值均大於樹根的鍵值。而高度平衡二元搜尋樹則又定義某一個節點右子樹跟左子樹的高度，高度差的 絕對值要小於等於 1，否則需要做調整，但調整的方法，最後必須維持二元搜尋樹的特質。在建立二 元搜尋樹時，如果鍵值分別是 50、40、60、30、45。此時若再加入20，此二元搜尋樹的高度平衡原則就會被破壞。請問根據高度平衡的原則去調整後，最後的二元搜尋樹的前序走訪的結果為何？
(A) 20 30 40 50 45 60
(B) 40 30 20 45 50 60
(C) 50 40 30 60 20 45
(D) 40 30 20 50 45 60