定義: 若一顆二元樹滿足以下兩點:

a. 左子節點的值小於節點的值

b. 右子節點的值大於節點的值

即可稱為二元搜尋樹

1
2
3
4
5
  2            6
 / \          / \
1   3        5   8     <-----像這樣, 這兩棵都是BST
            /   / \
           3   7   9

二元搜尋樹的查詢, 插入, 走訪, 查詢最大最小值和刪除操作

提示: 刪除節點有兩個子節點的時候, 要用它的中序後繼來代替該節點,

演算法為: 找到被刪除節點的右子節點, 然後查詢此右子節點下的最後一個左子節點, 即此顆子樹的最小值節點, 這就是被刪除節點的中序後繼節點.

何謂前序, 中序, 後序?

以上圖右邊的三層樹為例, 看1~2層的子樹:

preorder 前序: 6 -> 5 -> 8

inorder 中序: 5 -> 6 -> 8

postorder 後序: 5 -> 8 -> 6

若看整顆:

中序: 3 -> 5 -> 6 -> 7 -> 8 -> 9

所以若要刪除8, 要找它的“中序後繼節點(in-order successor)”的話, 就是9了