gusucode.com > 基于matlab的JPEG彩色图像编码解码源码程序 > 基于matlab的JPEG彩色图像编码解码源码程序/code/huffman.m

    function tree=huffman(values,frequencys,sum)
n=length(values);
p(:,1)=frequencys;
p(:,2)=1:n;
node.left=int16(-1);
node.right=int16(-1);
node.parent=int16(-1);
node.value=int16(-1);
node.isleaf=false;
node.code='';
tree(2*n-1)=node;
if n==1 %只有一个数
    tree(1).code='0';
    tree(1).value=values(1);
     tree(1).isleaf=true;
    return;
end
for i=1:n
    tree(i)=node;
    tree(i).value=int16(values(i));
    tree(i).isleaf=true;
end
for i=n+1:2*n-1
    tree(i)=node;
end

for i=1:n-1 %共需n-1次合并
    [q(:,1),ix]=sort(p(:,1));%把q的元素按照降序排列放到q中,
    q(:,2)=p(ix(:),2);
    p(:,:)=[q(1,:)+q(2,:);q(3:n,:);[sum,0]];
    p(1,2)=n+i;
    tree(n+i).left=int16(q(1,2));
    tree(n+i).right=int16(q(2,2));
    tree(q(1,2)).parent=n+i;
    tree(q(1,2)).code='0';
    tree(q(2,2)).parent=n+i;
    tree(q(2,2)).code='1';
end
front=0;
rear=0;
queue=zeros(2*n-1,2);%队列,存储每层节点
rear=rear+1;
queue(rear,1)=2*n-1;%将根节点放入队列
queue(rear,2)=1;%根节点树的高度为1
h=0;
while front~=rear
    h=h+1;
    hnodeindexs=[];%保存该层节点
    hn=1;%hnodeindexs数组的下标
    %求出高度为h的所有节点
    while front<2*n-1 && queue(front+1,2)==h %队列总共有2n-1个节点
        front=front+1;
        hnodeindexs(hn)=queue(front,1);%取出h层上的一个节点
        hn=hn+1;
    end
    %对该层节点进行重新排序,使得该层的叶子节点集中在前面,内节点集中在后面
    i=1;
    j=hn-1;
    if(hn>2)
        while i<j
            %寻找处在前面位置的非叶子节点
            while i<j && tree(hnodeindexs(i)).isleaf==true
                i=i+1;
            end
            %寻找处在后面位置的非内节点
            while j>i && tree(hnodeindexs(j)).isleaf==false
                j=j-1;
            end
            %两节点交换位置
            ii=tree(hnodeindexs(i)).parent;
            jj=tree(hnodeindexs(j)).parent;
            %修改父节点的左右孩子指向
            if tree(ii).left==hnodeindexs(i)
                if tree(jj).left==hnodeindexs(j)
                    tree(ii).left=hnodeindexs(j);
                    tree(jj).left=hnodeindexs(i);
                else
                    tree(ii).left=hnodeindexs(j);
                    tree(jj).right=hnodeindexs(i);
                    tree(hnodeindexs(i)).code='1';
                    tree(hnodeindexs(j)).code='0';
                end
            else
                if tree(jj).left==hnodeindexs(j)
                    tree(ii).right=hnodeindexs(j);
                    tree(jj).left=hnodeindexs(i);
                    tree(hnodeindexs(i)).code='0';
                    tree(hnodeindexs(j)).code='1';
                else
                    tree(ii).right=hnodeindexs(j);
                    tree(jj).right=hnodeindexs(i);
                end
            end
            %修改两节点的父节点指向
            tree(hnodeindexs(i)).parent=jj;
            tree(hnodeindexs(j)).parent=ii;
            %修改两节点在该层中的排序
            temp=hnodeindexs(i);
            hnodeindexs(i)=hnodeindexs(j);
            hnodeindexs(j)=temp;
            %两节点已交换,寻找下一对节点
            i=i+1;
            j=j-1;
        end
        %将该层节点的孩子节点放入队列        
    end
    for i=1:hn-1
        if tree(hnodeindexs(i)).left~=-1 %非叶子节点
            rear=rear+1;
            queue(rear,1)=tree(hnodeindexs(i)).left;
            queue(rear,2)=h+1;
            rear=rear+1;
            queue(rear,1)=tree(hnodeindexs(i)).right;
            queue(rear,2)=h+1;
        end
    end
end
%对叶子节点进行编码
for i=1:n
    p=tree(i).parent;
    while(p~=-1)
        tree(i).code=strcat(tree(p).code,tree(i).code);
        p=tree(p).parent;
    end
end
end