二元樹刪除可分為幾種狀況:
❶ 刪除的節點為樹葉:只要將相連的父節點指向Null即可。
❷ 刪除的節點只有一顆子樹
將其右指標欄放到其父節點的左指標欄。
❸ 刪除的節點有兩顆子樹,這方式有兩種,雖然結果不同,但都可符合二元樹特性。
1.找出中序立即前行者,即是將遇刪除節點的左子樹最大者向上提,在此節點為2,也就是在該節點的左子樹,往右尋找,直到右指標為Null,這個節點就是中序立即前行者。
2.找出中序立即後繼者,就是將欲刪除節點的右子樹最小者向上提,在此即為節點5,也就是在該節點的右子樹,往左尋找,直到左指標為Null,這個節點就是中序立即後繼者。
範例:
將32,24,57,28,10,43,72,62,依照中序方式存入可放10個節點之陣列內,說明節點在陣列中相關位置,如果插入資料30寫出相關變化,再來刪除32寫出相關變化。
root=1 | left | data | right |
---|---|---|---|
1 | 2 | 32 | 3 |
2 | 4 | 24 | 5 |
3 | 6 | 57 | 7 |
4 | 0 | 10 | 28 |
5 | 0 | 28 | 0 |
6 | 0 | 43 | 0 |
7 | 8 | 72 | 0 |
8 | 0 | 62 | 0 |
9 | |||
10 |
插入資料30:
root=1 | left | data | right |
---|---|---|---|
1 | 2 | 32 | 3 |
2 | 4 | 24 | 5 |
3 | 6 | 57 | 7 |
4 | 0 | 10 | 0 |
5 | 0 | 28 | 8 |
6 | 0 | 43 | 0 |
7 | 8 | 72 | 0 |
8 | 0 | 30 | 0 |
9 | 0 | 62 | 0 |
10 |
刪除資料32:
root=1 | left | data | right |
---|---|---|---|
1 | 3 | 24 | 4 |
2 | 5 | 57 | 6 |
3 | 0 | 10 | 0 |
4 | 0 | 28 | 0 |
5 | 0 | 43 | 0 |
6 | 7 | 72 | 0 |
7 | 0 | 62 | 0 |
8 | 1 | 30 | 2 |
9 | |||
10 |
堆積排序法算是選擇排序法的強化,他可以減少選擇排序法中的比較次數,進而減少排序時間。堆積法排序法使用了二元樹技巧,利用堆積樹來完成排序。可分為最大堆積樹及最小堆積樹兩種。
最大堆積樹:
➊ 是一個完整二元樹。
➋ 所有節點的值都大於或等於他左右子節點的值。
➌ 樹根是堆積樹中最大的。
最小堆積樹:
➊ 是一個完整二元樹。
➋ 所有節點的值都小於或等於他左右子節點的值。
➌ 樹根是堆積樹中最小的。
這邊先來了解如何將二元樹轉換成堆積樹:
這邊有一筆資料[32,17,16,24,35,87,65,4,12],以二元樹表示
要將該二元樹轉換成堆積樹,可用堆陣列來儲存二元樹所有節點的值。
A[0]=32,A[1]=17,A[2]=16,A[3]=24,A[4]=35,A[5]=87,A[6]=65,A[7]=4,A[8]=12
㈠ A[0]=32為樹根,若A[1]大於父節點則必須互換。此處A[1]=17 < A[0]=32所以不換。
㈡ A[2]=16 < A[0]不換。
㈢ A[3]=24 > A[1]=17所以交換。
㈣ A[4]=35 > A[1]=24所以交換,再與A[0]=32比較,A[1]=35 > A[0]=32所以交換。
㈤ A[5]=87 > A[2]=16所以交換,再與A[0]=35比較,A[2]=87 > A[0]=35所以交換。
㈥ A[6]=65 > A[2]=35所以交換,且A[2]=65 < A[0]=87所以不交換。
㈦ A[7]=4 < A[3]=17所以不換,A[8]=12 < A[3]=17所以不交換。
這是由上往下逐一堆積樹的建立來改變個節點值,最終得到一最大堆積樹。
堆積樹並非唯一解,也可以由陣列最後一個元素由下往上逐一比較來建立最大堆積樹。若想由小到大,就必須建立最小堆積樹,做法和建立最大堆積樹類似。
㈠ 依順序建立完整二元樹。
㈡ 建立堆積樹。
㈢ 將57自樹根移除,重新建立堆積樹。
㈣ 將43自樹根移除,重新建立堆積樹。
㈤ 將40自樹根移除,重新建立堆積樹。
㈥ 將34自樹根移除,重新建立堆積樹。
㈦ 將19自樹根移除,重新建立堆積樹。
㈧ 將17自樹根移除,重新建立堆積樹。
㈨ 將14自樹根移除,重新建立堆積樹。
最後將4自樹根移除。得到排序為[57,43,40,34,19,17,14,4]
fn main() {
let mut arr = vec![34,19, 40, 14, 57, 17, 4, 43];
println!("原始陣列: {:?}", arr);
heap_sort(&mut arr);
println!("排序後的陣列: {:?}", arr);
}
fn heap_sort(arr: &mut Vec<i32>) {
let n = arr.len();
// 建構最大堆
for i in (0..n / 2).rev() {
heapify(arr, n, i);
}
// 從中取出元素並排序
for i in (0..n).rev() {
arr.swap(0, i);
// 將跟節點移到陣列尾
heapify(arr, i, 0);
// 重新建立
println!("步骤 {}: {:?}", n - i, arr);
}
}
fn heapify(arr: &mut Vec<i32>, n: usize, i: usize) {
let mut largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if left < n && arr[left] > arr[largest] {
largest = left;
}
if right < n && arr[right] > arr[largest] {
largest = right;
}
if largest != i {
arr.swap(i, largest);
heapify(arr, n, largest);
}
}
今天終於把基本的樹狀演算法都講完了,算是快速地講解以及實際走法,樹狀走的步驟可能要多看幾次會比較清楚點。
這邊應該不會太難吧🎍🎍!!
要是哪裡理解上還是邏輯上有錯請各位大大指正,感謝 🧙🧙🧙。