#Written by Kellen Myers, Feb. 12, 2009
# This file contains the procedures needed to make lots of trees of same height
# For help, you can type HELP();

HELP:=proc()
 print(` DisplayTree(T) , AllTrees(h) , NumTrees(h) , ShowTrees(h) ` );
end:

with(plots):

DT:=proc(T,a,b,i) local v,pic:
 
 v:=[ (a+b)/2 , i ];
 
 pic:=plot({v},style=point,axes=none,symbol=solidbox,symbolsize=20);
 
 if T[1]<>{} then
    pic:=display(pic,DT(T[1],a,(a+b)/2,i+1));
    pic:=display(pic,plot( { v , [ (3*a+b)/4,i+1 ] } ) );
 fi:

 if T[2]<>{} then
    pic:=display(pic,DT(T[2],(a+b)/2,b,i+1));
    pic:=display(pic,plot( { v , [ (a+3*b)/4,i+1 ] } ) );
 fi:

 pic;
 
end:

DisplayTree:=proc(T) DT(T,0,1,0) end:

#let's get all the trees! -- also I wrote this one on my own!
AllTrees:=proc(k) local S,Sk,i,j,Trees:
option remember:
 if k=0 then RETURN( { {} } ) fi:
 Sk:=AllTrees(k-1);
 S:={};
 for j from 0 to k-1 do
  S:=S union AllTrees(j):
 end:
 
 Trees:={}:
 
 for j from 1 to nops(S) do
 for i from 1 to nops(Sk) do
  Trees:=Trees union { [Sk[i],S[j]] , [S[j],Sk[i]] }:
 end:
 end:
 
 RETURN(Trees):

end:


#plots a sequence of plots in a nice rectangular format (not great for <4 plots).
plotseq:=proc(plts) local n,i,a,b,plts2:
 n:=nops(plts):
 a:=floor(sqrt(n)):
 b:=ceil(n/a):
 plts2:=array(0..a-1,0..b-1):
 for i from 0 to n-1 do
  plts2[iquo(i,b),irem(i,b)]:=display(plts[i+1]):
 end:
 for i from n to a*b-1 do
  plts2[iquo(i,b),irem(i,b)]:=plot(0,x=0..1,axes=none,color=white):
 end:
 display(plts2):
end:

#Let's count them, using the shell of the recursion in AllTrees:
NumTrees:=proc(k) local S,Sk:
option remember:
 if k=0 then RETURN(1) fi:
 Sk:=NumTrees(k-1);
 S:=add(NumTrees(j),j=0..k-1):
 
# Trees:=Trees union { [Sk[i],S[j]] , [S[j],Sk[i]] }:
# In this line, we get two trees for each pair EXCEPT when they are the same (thus both lenght k), we double count, so subtract:
 RETURN(2*Sk*S-Sk^2):

end:

#Show them all of a specific height
ShowTrees:=proc(n) plotseq([seq(DisplayTree(AllTrees(n)[i]),i=1..nops(AllTrees(n)))]) end:

# The p will stand for a leaf of the tree, making it a bit easier to make sense of it.
# You can check out NumTrees(i) in the online encyclopedia of integer sequences
# Try the following lines:

# read `W:\\kellenstrees.txt`;
# p:=[ {} , {} ]:
# DisplayTree([[p,p],[[p,p],p]]);
# ShowTrees(3);
# seq(nops(AllTrees(i)),i=0..4);
# seq(NumTrees(i),i=0..8);