先來複習一下霍夫曼樹(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,這種巢狀結構適合樹狀結構的需求。
程式如下:
- function HT = ghftree(p)
- tree = cell(length(p),1); %產生與陣列p相同長度的cell
- for i=1:length(p)
- tree{i}=i; %每個節點的代號初始值依序為1,2,3...
- end
- while numel(tree)>2
- [p, pos] = sort(p,'ascend'); %從小排到大
- p(2)=p(1)+p(2); %將最小及次小的值相加,存到次小位置
- p(1)=[]; %刪除最小值的元素,因此陣列p的個數少一個
- tree = tree(pos); %節點依照p值大小排序
- tree{2}={tree{1},tree{2}}; %最小及次小的節點合併,存至次小節點內
- tree(1)=[]; %刪除最小的節點
- end
- HT = printtree(tree);
- function tt = printtree(tree) %將樹結構(cell)印出來
- if isa(tree,'cell') %如果是一個cell,就印左括號,左樹,右樹,右括號
- tt = strcat('(', printtree(tree{1}),printtree(tree{2}),')');
- else
- tt = num2str(tree);%如果不是cell,就印內含的值(把數字轉換成字串)
- end
以上程式中,輸入的p是一個一維矩陣,tree一開始的長度與p相同。在while 迴圈內,p與tree的長度一直遞減,但tree減少的元素"塞進"其它元素內,形成樹狀結構。
在第12行中,tree(1)=[]; 不可寫成 tree{1}=[]; 後者的意思是將tree第一個元素清空,不是刪除。
第14行是一個遞迴到程式,將tree以左括號、左樹、右樹、右括號的方式,遞迴印出。
第19行:因為tree的初始值在第4行設定為數字,所以需要轉換成字串形態印出來。
實際執行看看吧!
答案正確!
--- end ---
這應該是錯的吧
回覆刪除相加之後相同的值應該移到最後面
刪除不曉得妳說的是不是 第八行:p(2)=p(1)+p(2);
刪除相加之後放在第2個,第1個會被刪除,所以第2個變成了第1個。重點是後面的步驟還要再排序,所以不需要移到特定的位置!
請問要如何製造二元樹 matlab~QQ
回覆刪除題意有點模糊,可否具體一點!
刪除不好意思 我是MATLAB新手
回覆刪除請問一下ghftree()是要自己設嗎?謝謝
對啊!ghftree()是自己寫得!
刪除