program exam4;
type
tp=^tprec;
tprec=record
inf:integer;
next:tp
end;
tree=^treerec;
treerec=record
inf:integer;
left:tree;
right:tree;
end;
var genroot:tree;
genfirst:tp;
temp:tp;
listlen:integer;
q:boolean;
f:text;
procedure create_sortlist(var first:tp; inp:string);
var p,q:tp; c:integer; f:text;
begin
assign(f,inp);
reset(f);
new(p);
p^.next:=nil;
read(f,p^.inf);
first:=p;
while not eof(f) do
begin
read(f,c);
p:=first;
if (p^.next<>nil) and (c>first^.inf)
then
begin
while not((c>p^.inf)and(c<=p^.next^.inf)) and (p^.next<>nil) do
p:=p^.next;
q:=p^.next;
new(p^.next);
p:=p^.next;
p^.inf:=c;
p^.next:=q
end
else if c<p^.inf
then
begin
new(first);
first^.inf:=c;
first^.next:=p
end
else
begin
q:=p^.next;
new(p^.next);
p:=p^.next;
p^.inf:=c;
p^.next:=q
end
end;
close(f)
end;
procedure output_list(first:tp; out: string);
var p:tp; f:text;
begin
assign(f,out);
rewrite(f);
p:=first;
while p<>nil do
begin
write(f,p^.inf,' ');
p:=p^.next
end;
close(f)
end;
procedure CreateTree(var parent:tree;k,l:integer;q:boolean;lf:boolean);
var o,i:integer;
m:integer;
temp:tp;
begin
m:=0;
if (k = l) and not q then exit;
if (l-k<2) then
begin
if q then
begin
if k = 1 then o:=1 else
if l = listlen then o:=l else exit
end else
begin
if l = listlen then o:=l else
if k = 1 then o:=1 else exit;
end;
end else
begin
if lf then
o := (k+l) div 2
else
o:=(k+l+1) div 2;
end;
temp:=genfirst;
for i:=2 to o do
temp:=temp^.next;
if q then
begin
parent^.inf := temp^.inf;
parent^.left:=nil;
parent^.right:=nil;
CreateTree(parent,k,o,false,true);
CreateTree(parent,o,l,false,false);
q:=false;
end else
begin
if (parent^.inf>temp^.inf) then
begin
new(parent^.left);
parent^.left^.left:=nil;
parent^.left^.right:=nil;
parent^.left^.inf := temp^.inf;
if (o = 1)or(o=listlen) then exit;
CreateTree(parent^.left,k,o,false,true);
CreateTree(parent^.left,o,l,false,false);
end else
begin
new(parent^.right);
parent^.right^.left:=nil;
parent^.right^.right:=nil;
parent^.right^.inf := temp^.inf;
if (o = 1)or(o=listlen) then exit;
CreateTree(parent^.right,k,o,false,true);
CreateTree(parent^.right,o,l,false,false);
end;
end;
end;
procedure OutputTree(parent:tree);
begin
if parent^.left<>nil then OutputTree(parent^.left);
write(f,parent^.inf,' ');
if parent^.right<>nil then OutputTree(parent^.right);
end;
begin
create_sortlist(genfirst,'input4.inp');
output_list(genfirst,'output4.out');
temp:=genfirst;
listlen:=0;
while temp <> nil do
begin
temp:=temp^.next;
inc(listlen);
end;
new(genroot);
q:=true;
CreateTree(genroot,1,listlen,q,true);
assign(f,'output4.out');
append(f);
writeln(f);
OutputTree(genroot);
close(f)
end.