% hufftree.m
%
% given alphabet and probabilities: create huffman-tree


function [tree, table] = hufftree(alphabet,prob)

for l=1:length(alphabet)       % create a vector of nodes (leaves), one for each letter
   leaves(l).val = alphabet{l};
   leaves(l).zero= '';
   leaves(l).one='';
   leaves(l).prob = prob(l);
end

% combine the two nodes with lowest probability to a new node with the summed prob.
% repeat until only one node is left
while length(leaves)>1                           
   [dummy,I]=sort(prob);                         
   prob = [prob(I(1))+prob(I(2)) prob(I(3:end))];
   node.zero = leaves(I(1));         
   node.one  = leaves(I(2));         
   node.prob = prob(1);
   node.val = '';
   leaves = [node leaves(I(3:end))];
end


% pass through the tree,
% remove unnecessary information
% and create table recursively (depth first)
table.val={}; table.code={};
[tree, table] = descend(leaves(1),table,'');




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [tree, table] = descend(oldtree, oldtable, code)

table = oldtable;
if(~isempty(oldtree.val))
   tree.val = oldtree.val;
   table.val{end+1}  = oldtree.val;
   table.code{end+1} = code;
else
   [tree0, table] = descend(oldtree.zero, table, strcat(code,'0'));
   [tree1, table] = descend(oldtree.one,  table, strcat(code,'1'));
   tree.zero=tree0;
   tree.one= tree1;
end