作者：bake

9-8延伸二元樹入門   Extended Binary Tree

至於什麼叫最小搜尋成本呢？就讓我們先從延伸二元樹(Extension Binary Tree)談起。任何一個二元樹中，若有n個節點，則有n-1個非空鏈結及n+1個空鏈結。如果在每一個空鏈結加上一個特定節點，則稱為外節點，其餘的節點稱為內節點，且定義此種樹為(延伸二元數)，另外定義外徑長=所有外節點到樹根距離的總和，內徑長=所有內節點到樹根距離的總和。我們將以下例來說明(A)(B)兩圖，它們的延伸二元樹繪製：

以上(A)、(B)二圖為例，如果每個節點有加權值(例如搜尋機等)，則外徑常必須考慮相關加權值，或稱為加權外徑長，以下將討論(A)、(B)的 加權外徑長：

iT幫幫忙-解說：延伸二元樹

---

9-9霍夫曼樹特訓班

霍夫曼樹經常用於處理資料壓縮的問題，可以根據資料出現的頻率來建構的二元樹。例如資料的儲存和傳輸是資料處裡的二個重要領域，兩者皆和資料量的大小息息相關，而霍夫曼樹正可用來進行資料壓縮的演算法。

簡單來說，如果有n個權值(q1,q2…qn)，且構成一個有n個節點的二元樹，每個節點節點外部節點權值為qi，則加權徑長度最小的就稱為(最佳化二元樹)或(霍夫曼樹)Huffman Tree。對上一小節中，(A)、(B)二元樹而言，(A)就是二者的最佳化二元樹。接下來我們將說明，對一含權值的串列，該如何求其最佳化二元樹，步驟如下：

1.產生兩個節點，對資料中出現過的每一元素各自產生一樹葉節點，並賦予樹葉節點該元素之出現頻率。
2.另N為T1和T2的父親節點，T1和T2是T中出現頻率最低的兩個節點，令N節點的出現頻率等於T1和T2的出現頻率總和。
3.消去步驟的兩個節點，插入N，再重複步驟1。

我們將利用以上的步驟來實作求取霍夫曼樹的過程，假設現有五個字母BDACE的頻率分別為0.09、0.12、0.19、0.21和0.39，請說明霍夫曼樹建構之過程：

9-7堆積樹排序法-2

下面我們利用堆積排序法針對34、19、40、14、57、17、4、43的排序過程示範如下：

1.依下圖數字順序建立完整二元數。

2.建立堆積樹

3.將57自樹根移除，重新建立堆積樹

4.將43自樹根移除，重新建立堆積樹。

5.將40樹根移除，重新建立堆積樹

6.將34自樹根移除，重新建立堆積樹

7.將19自樹根移除，重新建立堆積樹

8.將17自樹根移除，重新建立堆積樹

9.將14自樹根移除，重新建立堆積樹

最後將4自樹根移除。得到的排序結果為57、43、40、34、19、17、14、4

JS                    heap.js

var heap=(data,size)=> {
	for (let i=Math.floor(size/2); i>0; i--)
		ad_heap(data, i, size-1);
	process.stdout.write('\n');
	process.stdout.write('堆積內容：');
	for (let i=1; i<size; i++)
		process.stdout.write('['+data[i]+'] ');
	process.stdout.write('\n\n');
	for (let i=size-2; i>0; i--) {
		temp=data[1];
		data[1]=data[i+1];
		data[i+1]=temp;
		ad_heap(data, 1, i);
		process.stdout.write('處理過程：');
		for (let j=1; j<size; j++)
			process.stdout.write('['+data[j]+'] ');
		process.stdout.write('\n');
	}
}

var ad_heap=(data, i, size)=> {
	j=2*i;
	tmp=data[i];
	post=0;
	while (j<=size && post==0) {
		if (j<size) {
			if (data[j]<data[j+1])
				j+=1;
		}
		if (tmp>=data[j])
			post=1;
		else {
			data[Math.floor(j/2)]=data[j];
			j=2*j;
		}
	}
	data[Math.floor(j/2)]=tmp;
}
data=[0,5,6,4,8,3,2,7,1];
size=9;
process.stdout.write('原始陣列：');
for (i=1; i<size; i++)
	process.stdout.write('['+data[i]+'] ');
heap(data,size);
process.stdout.write('排序結果：');
for (i=1; i<size; i++)
	process.stdout.write('['+data[i]+'] ');

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])由下往上逐一比較來建立最大堆積樹。如果您想由小到大排序，就必須建立最小堆積樹，做法和建立最大堆積樹類似，在此不另外說明。