Huffman Tree using Matlab

先來複習一下霍夫曼樹(Huffman Tree)是如何產生的。假設有六個數字，分別是 0.5, 0.125, 0.125, 0.125, 0.0625, 0.0625。這六個數字其實代表機率，而且相加等於壹。產生霍夫曼樹的演算法簡單講起來就是：

初始值：每個節點(NODE)的值就是剛才的六個機率值，所以共有六個節點

第一步：排序
第二步：將最小值的兩個節點合併成成一個，合併後的節點值就是合併前兩個節點值相加。
重複以上第一步及第二步，直到剩下一個節點為止。最後一個節點的值就是原節點值的總合，也就是壹。


在第二步中，合併兩節點(假設叫節點A與節點B)產生的新節點(假設是節點C)，新節點就是原兩節點的父節點；相對地，原兩節點就是子節點。也就是說C是A與B共同的父節點，至於A與B當然是C的子節點。霍夫曼樹就是經由以上的排序及合併步驟產生的二元樹。

以實例圖解上述步驟：

初始狀態：有6個節點

step1: 排序

step2: 合併

step1: 排序

step2: 合併

step1: 排序

step2: 合併

step1: 排序

step2: 合併

step1: 排序

step2: 合併

重複五次的排序及合併動作，最後得到了霍夫曼二元樹。

為了簡化表示，我們以(A B) 代表節點A與節點B共同的父節點。所以最後的霍夫曼二元樹就是 (((3 4)((5 6) 2))1)

現在我們要用Matlab來完成這樣的要求，輸入 [0.5 0.125 0.125 0.125 0.0625 0.0625]，輸出結果為 (((3 4)((5 6) 2))1)

我們可以利用Matlab的cell來完成樹狀結構的要求，cell裡面可以有cell，這種巢狀結構適合樹狀結構的需求。

程式如下：

1. function HT = ghftree(p)
2. tree = cell(length(p),1);       %產生與陣列p相同長度的cell
3. for i=1:length(p)
4.     tree{i}=i;                           %每個節點的代號初始值依序為1,2,3...
5. end
6. while numel(tree)>2       
7.     [p, pos] = sort(p,'ascend'); %從小排到大
8.     p(2)=p(1)+p(2);                %將最小及次小的值相加,存到次小位置
9.     p(1)=[];                              %刪除最小值的元素,因此陣列p的個數少一個
10.     tree = tree(pos);              %節點依照p值大小排序
11.     tree{2}={tree{1},tree{2}}; %最小及次小的節點合併，存至次小節點內
12.     tree(1)=[];                          %刪除最小的節點
13. end
14. HT = printtree(tree);
15. function tt = printtree(tree)      %將樹結構(cell)印出來
16. if isa(tree,'cell')    %如果是一個cell,就印左括號,左樹,右樹,右括號
17.     tt = strcat('(', printtree(tree{1}),printtree(tree{2}),')');
18. else
19.     tt = num2str(tree);%如果不是cell,就印內含的值(把數字轉換成字串)
20. end

以上程式中，輸入的p是一個一維矩陣，tree一開始的長度與p相同。在while 迴圈內，p與tree的長度一直遞減，但tree減少的元素"塞進"其它元素內，形成樹狀結構。

在第12行中，tree(1)=[]; 不可寫成 tree{1}=[]; 後者的意思是將tree第一個元素清空，不是刪除。

第14行是一個遞迴到程式，將tree以左括號、左樹、右樹、右括號的方式，遞迴印出。

第19行：因為tree的初始值在第4行設定為數字，所以需要轉換成字串形態印出來。

實際執行看看吧！

答案正確！

--- end ---