最优二叉树的matlab实现

%v = [0.8147 0.9058 0.1270 0.9134 0.6324 0.0975 0.2785 0.5469 0.9575 0.9649 0.1576 0.9706 0.9572 0.4854 0.8003]; origv = rand(1,7); v=origv;

MAXVAL = 100; ov = zeros(size(v)); numOL = length(v);

vv = zeros(1, numOL*2-1); tv = vv;

vv(numOL:length(tv)) = v;

for i=numOL-1:-1:1

[i1,i2] = findLeast2Val(v+ov); vv(i) = v(i1)+v(i2); ov(i1) = MAXVAL; ov(i2) = MAXVAL; tv(i1+i)=i; tv(i2+i)=i; v = [vv(i),v]; ov = [0,ov]; drawtree(tv); pause end

drawtree(tv);

function [ind1,ind2]=findLeast2Val(v) len=length(v);

if len==2

ind1=1; ind2=2; return; end

MIN2=100;

MIN1=99;

ind1=1; ind2=1; for i=1:len

if v(i)

MIN2 = MIN1; ind2=ind1; MIN1 = v(i); ind1=i; end end

function drawtree(treeVec)

treeplot2(treeVec);

count = size(treeVec,2); [x,y] = treelayout(treeVec); x = x'; y = y';

name1 = cellstr(num2str((1:count)'));

text(x(:,1), y(:,1), name1, 'VerticalAlignment','bottom','HorizontalAlignment','right') title({'Level Lines'},'FontSize',12,'FontName','Times New Roman'); end

function treeplot2(p,c,d)

%TREEPLOT Plot picture of tree.

% TREEPLOT(p) plots a picture of a tree given a row vector of % parent pointers, with p(i) == 0 for a root. %

% TREEPLOT(P,nodeSpec,edgeSpec) allows optional parameters nodeSpec % and edgeSpec to set the node or edge color, marker, and linestyle. % Use '' to omit one or both. %

% Example:

% treeplot([2 4 2 0 6 4 6]) % returns a complete binary tree. %

% See also ETREE, TREELAYOUT, ETREEPLOT.

% Copyright 1984-2009 The MathWorks, Inc.

% $Revision: 5.12.4.3 $ $Date: 2009/04/21 03:26:23 $

[x,y,h]=treelayout(p); f = find(p~=0);

pp = p(f);

X = [x(f); x(pp); repmat(NaN,size(f))]; Y = [y(f); y(pp); repmat(NaN,size(f))]; X = X(:); Y = Y(:);

if nargin == 1, n = length(p); if n < 500,

plot (x, y, 'ro', X, Y, 'r-'); else

plot (X, Y, 'r-'); end; else

[~, clen] = size(c); if nargin < 3, if clen > 1,

d = [c(1:clen-1) '-']; else

d = 'r-'; end; end;

[~, dlen] = size(d); if clen>0 && dlen>0 plot (x, y, c, X, Y, d); elseif clen>0, plot (x, y, c); elseif dlen>0, plot (X, Y, d); else end; end;

% 显示外部节点 k=find(y==min(y));

hold on , plot(x(k),y(k),'bs'); hold off

xlabel(['height = ' int2str(h)]); axis([0 1 0 1]);