Binary Search Tree with Swift
主要有兩個物件，Tree 和 Node, Node 代表Tree裡面的每個節點, 然後節點存有自己及left , right的子節點。
1. 將節點加到樹的規則(Add node to tree):
- 如果樹完全沒有節點，第一個加入的就是root
- 之後加入的如果加入的值比節點小，就放到left child。如果比較大就放到right child。放的時候檢查如果該子節點已經有值，繼續遞迴往下搜尋到沒有值的地方存放。
2. 顯示排序節點from smallest to biggest(Depth-First Search in-order) traverse:
 |
| A-B-C-D-E-F-G-I-H |
- 從最左邊(最小的)開始找，如果已經找不到left child代表已經是最小的，然後print出來。
- 然後檢查有沒有right child，繼續遞迴去找。
- Big O: O(n)
Pre-order traverse:
 |
| F-B-A-D-C-E-F-I-H |
- 顯示current node, 然後再顯示左邊子節點, 再來右邊子結點
Post-order traverse:
 |
| A-C-E-D-B-H-I-G-F |
- 遞迴顯示左邊子結點, 如果都巡覽完了再遞迴找右邊節點, 然後再顯示current node.
3. Remove node from tree:
- Check first if root exists. If not then return.
- Find the node to remove.
- If node doesn't have child, direct remove it.
- If node have one child, copy child's value to it then remove child.
- If node have 2 child:
- find a minimum value in the node's right subtree.
- replace value of the node to be removed with found minimum.
- remove to the right subtree to remove a duplicate(original minimum value in the node's right subtree).
參考:
0 comments: