
function plot_pst(pst)

degree = 3;

root = find_feature(pst, []);
pst = study_pst(pst, root, 0, degree);
pst = compute_offsets(pst, root, 0, degree);
m = length(pst);
for i = 1:m
    cx(i) = pst{i}.rootcoord;
    cy(i) = pst{root}.depth - pst{i}.level;    
end

newplot
radius = 0.1;
for i = 1:m
    for j = 1:length(pst{i}.children)
        line([cx(i) cx(pst{i}.children(j))],[cy(i) cy(pst{i}.children(j))],'Color','k');
        h_edge = text((cx(i)+cx(pst{i}.children(j)))/2, (cy(i)+cy(pst{i}.children(j)))/2, sprintf('%d',pst{pst{i}.children(j)}.x(end)));
        textsize = get(h_edge,'Extent');
        set(h_edge, 'Position', [textsize(1)+1.5*textsize(3) textsize(2)]);
    end
    if(~isempty(pst{i}.x))
        h = text(cx(i), cy(i), '    ');
    else
        h = text(cx(i), cy(i), 'root');
    end
    set(h, 'BackgroundColor', 'w', 'EdgeColor', 'k');
    textsize = get(h,'Extent');
    set(h, 'Position', [cx(i)-textsize(3)/2 cy(i)-textsize(4)/2]);
end
axis equal
axis off
%set(gca,'XTick',[],'YTick',[],'XColor','w','YColor','w')


% -----------------------------------------------------
function pst = study_pst(pst, root, level, degree)

for i = 1:degree
    f(i) = find_feature(pst,[pst{root}.x i-1]);
end

pst{root}.depth = 1;
pst{root}.left = 0;
pst{root}.right = 0;
pst{root}.level = level;
pst{root}.children = f(find(f));

nf = length(f);
for i = 1:nf
    if f(i)
        pst = study_pst(pst, f(i), level+1, degree);
        pst{root}.depth = max([pst{root}.depth pst{f(i)}.depth+1]);
        if(i < (degree+1)/2)
            pst{root}.left = pst{root}.left + pst{f(i)}.left + pst{f(i)}.right + 1;
        elseif(i > (degree+1)/2)
            pst{root}.right = pst{root}.right + pst{f(i)}.left + pst{f(i)}.right + 1;
        else
            pst{root}.left = pst{root}.left + pst{f(i)}.left;
            pst{root}.right = pst{root}.right + pst{f(i)}.right;
        end
    end        
end


% -----------------------------------------------------
function pst = compute_offsets(pst, root, rootcoord, degree)

pst{root}.rootcoord = rootcoord;

for i = 1:degree
    f(i) = find_feature(pst,[pst{root}.x i-1]);
end
midl = rootcoord -1;
midr = rootcoord + 1;
if(mod(degree,2))
    i = (degree+1)/2;
    if(f(i))
        midl = rootcoord - (pst{f(i)}.left+1);    
        midr = rootcoord + (pst{f(i)}.right+1);    
        pst = compute_offsets(pst, f(i), rootcoord, degree);
    end
end
for i = floor(degree/2):-1:1
    if f(i)
        pst = compute_offsets(pst, f(i), midl - pst{f(i)}.right, degree);
        midl = midl - pst{f(i)}.right - pst{f(i)}.left - 1;
    end
end
for i = (degree-floor(degree/2)+1):degree
    if f(i)
        pst = compute_offsets(pst, f(i), midr + pst{f(i)}.left, degree);
        midr = midr + pst{f(i)}.right + pst{f(i)}.left + 1;
    end
end


% -----------------------------------------------------
function i = find_feature(pst, x)

m = length(pst);
for i = 1:m
    if(isequal(pst{i}.x, x))
        return
    end
end
i = 0;