Help20:=proc(): print(`BT(n), DrawT(T), BTw(n,L) `): end:

with(plots):

#Root(T,Leav): the root of the tree with Leaves at Leav
Root:=proc(T,Leav)
local root1,root2,T1,T2,Leav1,Leav2:
 if Size1(T)<>nops(Leav) then
  ERROR(`Bad output`):
 fi:

if T=[] then
RETURN(Leav[1]):
fi:

T1:=T[1]:
T2:=T[2]:
Leav1:=[op(1..Size1(T1),Leav)]:
Leav2:=[op(Size1(T1)+1..Size1(T),Leav)]:
root1:=Root(T1,Leav1):
root2:=Root(T2,Leav2):

[(root1[1]+root2[1])/2,max(root1[2],root2[2])+1]:
end:

Size1:=proc(tree):
if tree=[] then 1 else Size1(tree[1])+Size1(tree[2]) fi:
end:


#DrawT1(T,Leav): Draws the (complete) binary tree T
#with prescribed places for the leaves
#For example, try: DrawT1([[],[]],[[-1,0],[1,0]]);
DrawT1:=proc(T,Leav)
local gu,gu1,gu2,T1,T2,Root1L,Root1R,Leav1,Leav2,Root1:
if T=[] then
  gu:=plot([Leav[1]],style=point,axes=none,scaling=unconstrained):
RETURN(gu):
fi:
T1:=T[1]:
T2:=T[2]:
Leav1:=[op(1..Size1(T1),Leav)]:
Leav2:=[op(Size1(T1)+1..Size1(T),Leav)]:
gu1:=DrawT1(T1,Leav1):
gu2:=DrawT1(T2,Leav2):
Root1L:=Root(T1,Leav1):
Root1R:=Root(T2,Leav2):
Root1:=Root(T,Leav):

gu:=
plot([Root1,Root1L],thickness=3,axes=none),plot([Root1,Root1R],thickness=3),
gu1,gu2:

end:


DrawT:=proc(T) local i:
display(DrawT1(T,[seq([i,0],i=1..Size1(T))])):end:


#BT(n): the set of binary trees on n leaves
BT:=proc(n)
local gu,k,gu1,gu2,i,j:
option remember:
if not type(n,integer) then
ERROR(`input should be an integer`):
fi:
if n<=0 then
RETURN({}):
fi:
if n=1 then
RETURN({[]}):
fi:

gu:={}:

for k from 1 to n-1 do
gu1:=BT(k):gu2:=BT(n-k):

for i from 1 to nops(gu1) do
for j from 1 to nops(gu2) do
gu:=gu union {[gu1[i],gu2[j]]}:
od:
od:
gu:
od:
gu:
end:




#BTw(n,L): the set of binary trees on n leaves with reward list L. Try: BTw(5,[[2,-1],[1,2],[4,1],[6,3],[3,4]]);
BTw:=proc(n,L)
local gu,k,gu1,gu2,i,j:
option remember:
if not type(n,integer) and type(L,list) and nops(L)=n then
ERROR(`input should be an integer, and a list of the that size`):
fi:
if n<=0 then
RETURN({}):
fi:
if n=1 then
RETURN({[L[1]]}):
fi:

gu:={}:

for k from 1 to n-1 do
gu1:=BTw(k,[op(1..k,L)]):gu2:=BTw(n-k,[op(k+1..n,L)]):

for i from 1 to nops(gu1) do
for j from 1 to nops(gu2) do
gu:=gu union {[gu1[i],gu2[j]]}:
od:
od:
gu:
od:
gu:
end:




#textplot([A[1],A[2],NA])






#RootW(T,Leav): the root of the tree with Leaves at Leav
RootW:=proc(T,Leav)
local root1,root2,T1,T2,Leav1,Leav2:
 if Size1(T)<>nops(Leav) then
  ERROR(`Bad output`):
 fi:

if nops(T)=1 and nops(T[1])=2 then
RETURN(Leav[1]):
fi:

T1:=T[1]:
T2:=T[2]:
Leav1:=[op(1..Size1(T1),Leav)]:
Leav2:=[op(Size1(T1)+1..Size1(T),Leav)]:
root1:=Root(T1,Leav1):
root2:=Root(T2,Leav2):

[(root1[1]+root2[1])/2,max(root1[2],root2[2])+1]:
end:

Size1:=proc(tree):
if tree=[] then 1 else Size1(tree[1])+Size1(tree[2]) fi:
end: