基于matlab构造最优二叉树

xxxx20xx届本科生毕业设计（论文）

disp('% p is a vector with the probability'); disp(p');

ltr=length(tr);% augment with the growing of the huffman tree lp=length(p);% decrease with the growing of huffman tree roolp=3; while lp>1

%if(length(list)-lp+1 <= 9)

%subplot(roolp,roolp,length(list)-lp+1); figure(length(list)-lp+1); drawhufftree(tr,list,tempp); %end

% merge p(lp) and p(lp-1); p(lp-1)=p(lp-1)+p(lp); p=p(1:lp-1);

% tr(ltr+1) is a new node of the huffman tree

% tr(find(tr==lp)) and tr(find(tr==lp-1)) is its two children ltr=length(tr); tr(find(tr==lp))=ltr+1; tr(find(tr==lp-1))=ltr+1; tr(ltr+1)=lp-1;

tempp(ltr+1)=p(lp-1); % record the probability of this node % sort p again after merging; pp=-p; [pp t]=sort(pp); p=-pp; %[p,t]=sort(p,'descend'); lp=length(p);

% tempp(1:lp-1)=p(1:lp-1); % update the order of probability to display % update the pointer of tr then temp=tr; for j=1:lp

tr(find(temp==t(j)))=j; end

%show the middle result disp('tr:(huffman tree)'); disp(tr');

disp('tempp:(probability on the tree)'); disp(tempp');

13

xxxx20xx届本科生毕业设计（论文）

disp('p:(probability)'); disp(p');

disp('t:(sort of p)'); disp(t'); end

tr(length(tr))=0; % the root of huffman tree %draw the result

figure(length(list)-lp+1); drawhufftree(tr,list,tempp); end

经过matlab的仿真可得到如下最优二叉树图形：

图4-1 最优二叉树仿真图（1）

14

xxxx20xx届本科生毕业设计（论文）

图4-2 最优二叉树仿真图（2）

15

xxxx20xx届本科生毕业设计（论文）

图4-3 最优二叉树仿真图（3）

16