基于matlab构造最优二叉树

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