发布时间 : 星期三 文章基于matlab构造最优二叉树更新完毕开始阅读0f0c7bc1d5bbfd0a795673c8
xxxx20xx届本科生毕业设计（论文）
图4-4 最优二叉树仿真图（4）
17
xxxx20xx届本科生毕业设计（论文）
图4-5 最优二叉树最终生成图
4.3 用Matlab构造最优二叉树算法
在MATLAB中实现哈夫曼算法，可用一个5?(2n?1)的矩阵来表示哈夫曼树，该矩阵的含义如表6-3-3所示。
18
xxxx20xx届本科生毕业设计（论文）
表4-1 最优二叉树算法结构表
字符 1 序号 概率 父结点 序号 2 3 4 5 ……… 2n-1 左右子0表示1表示树标志 左子树 右子树 是否在1在集0不在集合F 合F
集合F 下面给出哈夫曼树的生成算法： function htree = HuffmanTree(pro) %构造哈夫曼树 %pro为一概率向量
n=size(pro,2);%得到字符个数 tree=ones(6,2*n-1);%构造树数据结构 tree(1,:)=1:(2*n-1);%填充结点序号 tree(5,(n+1):end)=0;%设置结点是否在集合 tree(2,1:n)=pro;%设置概率
tree(6,1:end)=0;%记录查找的结点对顺序 for i=(n+1):(2*n-1);%循环控制
[l,r]=findminval(tree);%找到集合中两个最小的值的序号 tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值 tree(5,i)=1;%设置新构造结点在集合中
19
xxxx20xx届本科生毕业设计（论文）
tree(3,l)=i;tree(3,r)=i;%设置父结点序号 tree(4,l)=0;tree(4,r)=1;%设置左右标志 tree(5,l)=0;tree(5,r)=0;%设置不在集合中
tree(6,l)=i-n;tree(6,r)=i-n;%记录该次删除的结点对顺序 end
htree=tree;
function [l,r]=findminval(tree) s=find(tree(5,:)==1); if size(s,2)<2
error('Error input!'); end
firval=realmax;secval=realmax; for i=s;
if firval>tree(2,i) if secval>firval
second=first;secval=firval; end
first=i;firval=tree(2,i); elseif secval>tree(2,i)
second=i;secval=tree(2,i); end
20