作者：bake

9-7堆積樹排序法-1

堆積樹排序法可以算是選擇排序法的改進法，它可以減少在選擇排序法中的比較次數，進而減少排序時間。堆積排序法使用到了二元樹的技巧，它是利用堆積樹來完成排序。堆積是一種特殊的二元樹，可分為最大堆積樹及最小堆積樹兩種。而最大堆積樹滿足以下3個條件：

1.它是一個完整二元樹。
2.所有節點的值都大於或等於它左右子節點的值。
3.樹根是堆積樹中最大的。

而為小堆積樹則具備以下3個條件

1.它是一個完整二元樹。
2.所有節點的值都小於會等於它左右子節點的值。
3.樹根是堆積樹中最小的。

在開始討論堆積樹排序法前，各位必須先認識如何將二元樹轉換成堆積樹(heap tree)。我們以下面實例進行說明：
假設有9筆資料32、17、16、24、35、87、65、4、12，我們以二元樹表示如下：

如果要將該二元樹轉換成堆積樹。我們可以用陣列來儲存二元樹所有節點的值，即

1.A[0]=32為樹根，若A[1]大於父節點則必須互換。此處A[1]=17<A[0]=32故不交換。
2.A[2]=16<A[0]故不交換。

3.A[3]=24>A[1]=17 故交換

4.A[4]=35>A[1]=24 故交換，再與A[0]=32比較，A[1]=35>A[0]=32 故交換

5.A[5]=87>A[2]=16 故交換，再與A[0]35比較，A[2]=87>A[0]=35 故交換

6.A[6]=65>A[2]=35 故交換，且A[2]=65<A[0]=87 故不必換。

7.A[7]=4<A[3]=17 故不必換。
  A[8]=12<A[3]=17 故不必換。

可得下列的堆積樹

剛才示範由二元樹的樹根開始由上往下逐一依堆積樹的建立原則來改變個節點值，最終得到一最大堆積樹。各位可以發現堆積樹並非唯一，您也可以由陣列最後一個元素(例如此例中的A[8])由下往上逐一比較來建立最大堆積樹。如果您想由小到大排序，就必須建立最小堆積樹，做法和建立最大堆積樹類似，在此不另外說明。

9-5二元樹節點插入

談到二元樹節點插入的情況和搜尋相似，重點是插入後仍要保持二元搜尋樹的特性。如果插入的節點在二元樹就沒有插入的必要，而搜尋失敗的狀況，就是準備插入的位置。

if (search (ptr, data)!=null)
       process.stdout.write(‘二元樹中有此節點了！\n’)
else {
       ptr=create_tree(ptr.data);
       inorder(ptr);
}

JS           add_search.js

class tree {
	constructor () {
		this.data=0;
		this.left=0;
		this.right=0;
	}
}

var create_tree=(root, val)=> {
	newnode=new tree();
	newnode.data=val;
	newnode.left=null;
	newnode.right=null;
	if (root==null) {
		root=newnode;
		return root;
	}
	else {
		current=root;
		while (current!=null) {
			backup=current;
			if (current.data>val)
				current=current.left;
			else
				current=current.right;
		}
		if (backup.data>val)
			backup.left=newnode;
		else
			backup.right=newnode;
	}
	return root;
}

var search=(ptr, val)=> {
	while (true) {
		if (ptr==null)
			return null;
		if (ptr.data==val)
			return ptr;
		else if (ptr.data>val)
			ptr=ptr.left;
		else
			ptr=ptr.right;
	}
}

var inorder=(ptr)=> {
	if (ptr!=null) {
		inorder(ptr.left);
		process.stdout.write('['+ptr.data+'] ');
		inorder(ptr.right);
	}
}

arr=[7,1,4,2,8,13,12,11,15,9,5];
ptr=null;
process.stdout.write('[原始陣列內容]\n');

for (i=0; i<11; i++) {
	ptr=create_tree(ptr,arr[i]);
	process.stdout.write('['+arr[i]+'] ');
}
process.stdout.write('\n');
const prompt=require('prompt-sync')();
const data=parseInt(prompt('請輸入搜尋值：'));
if (search(ptr,data) !=null)
	process.stdout.write('二元樹中有此節點了！\n');
else {
	ptr=create_tree(ptr,data);
	inorder(ptr);
}

9-6二元樹節點的刪除

二元樹節點的刪除則稍微複雜，可分為以下三種狀況：

>刪除的節點為樹葉

只要將其相連的父節點指向null即可。

>刪除的節點只有一棵子樹

如下圖刪除節點1，就將其右指標欄放到其父節點的左指標欄：

>刪除的節點有兩棵子樹

如下圖刪除節點4，方式有兩種，雖然結果不同，但都可符合二元樹特性：

1.找出中序立即前行者(inorder immediate successor)，即是將欲刪除節點的左子樹最大者向上提，在此即為節點2，簡單來說，就是在該節點的左子樹，往右尋找，直到右指標為null，這個節點就是中序立即前行者。

2.找出中序立即後繼者(inorder immediate successor)，即是將欲刪除節點的右子樹最小者向上提，在此即為節點5，簡單來說，就是在該節點的右子樹，往左尋找，直到左指標為null，這個節點就是中序立即後繼者。

解法：
30<32  -> 所以往左邊。
30>24  -> 所以往右邊。
30>28  -> 所以往右邊。

刪除的資料32：

解法：
方法1：中序後繼者->左子樹最大者：左子樹後往右邊找到最大，為節點8 數字30。
方法2：中序後繼者->右子樹最小者：右子樹往左找，碰到左右都有往左邊找，為節點6 數字43。