最优二叉树：Huffman编码(基于MATLAB)

function h =Huffman(p)

%%最优二叉树的霍夫曼算法

%输入：概率数组p

%输出：对应的Huffman编码

n=length(p);

q=p;

a=zeros(n-1,n);                    

 %生成一个n-1行n列的数组

for i=1:n-1  

  [q,l]=sort(q);            

%对概率数组q进行从小至大的排序，并且用l数组返回一个数组，

%该数组表示概率数组q排序前的顺序编号

  a(i,:)=[l(1:n-i+1),zeros(1,i-1)];    

%由数组l构建一个矩阵，该矩阵表明概率合并时的顺序，用于后面的编码

  q=[q(1)+q(2),q(3:n),1];      

 %将排序后的概率数组q的前两项，即概率最小的两个数加和，得到新的一组概率序列

end  

%w完成最优二元树的建立，下面进行编码

for i=1:n-1  

  c(i,1:n*n)=blanks(n*n);    

%　生成一个n-1行n列，并且每个元素的的长度为n的空白数组，c矩阵用于进行huffman编码，

%　并且在编码中与a矩阵有一定的对应关系

end  

c(n-1,n)='0';c(n-1,2*n)='1';        

 %　由于a矩阵的第n-1行的前两个元素为进行huffman编码加和运算时所得的最后两个概率，因此其值为0或1，

　%　在编码时设第n-1行的第一个空白字符为0，第二个空白字符1。

for i=2:n-1  

 c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1)));

  %矩阵c的第n-i行的第一个元素的n-1个字符赋值为对应于a矩阵中第n-i+1行中值为1的位置在c矩阵中的编码值

  c(n-i,n)='0';            

  %根据之前的规则，在分支的第一个元素最后补0

  c(n-i,n+1:2*n-1)=c(n-i,1:n-1);

%矩阵c的第n-i行的第二个元素的n-1个字符与第n-i行的第一个元素的前n-1个符号相同，因为其根节点相同

  c(n-i,2*n)='1';            

 %根据之前的规则，在分支的第二个元素最后补1

  for j=1:i-1

    c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1));  

%矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在

%c矩阵中的编码值                                                                                                                          

  end  

end                      

%完成huffman码字的分配

for i=1:n

 h(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n);  

%用h表示最后的huffman编码，矩阵h的第i行的元素对应于矩阵c的第一行的第i个元素

end  

fprintf('\nhuffman code:\n');

%---------- 应用测试---------

>> p=[0.350.1 0.2 0.1 0.2 0.05];

>> h =Huffman(p)

huffman code:

h =

   11

 1011

   00

  100

   01