Uses crt;

type ptr = ^node;
node = record
  info : char;
  llink, rlink : ptr;
end;

     pStack = ^tStack;
tStack =  record
  nd : ptr;
  next : pStack;
end;


procedure Push (var Stack: pStack; nd: ptr);
var StackEl: pStack;
begin
new (StackEl);
StackEl^.next:=Stack;
Stack:=StackEl;
StackEl^.nd:=nd;
end;

function Pop (Var Stack: pStack): ptr;
var StackEl: pStack;
begin
pop:=Stack^.nd;
StackEl:=Stack;
Stack:=StackEl^.next;
dispose (StackEl);
end;

procedure PrintTree( p : ptr;  h : integer );
begin
if p<>nil then begin
  PrintTree(p^.llink, h+1);
  gotoxy(wherex, h);
  textcolor(yellow);
  write(p^.info);
  textcolor(white);
  PrintTree(p^.rlink, h+1);
end;
end;

function CreateTree( n : integer; var i : integer) : ptr;
var newnode : ptr;
     nl, nr : integer;
     x : char;
begin
if n <= 0 then CreateTree := nil
else begin
  nl := n div 2;
  nr := n - nl - 1;
  i:=i+1;
  writeln;
  write ('Vvedite info uzla ',i,': ');
  readln(x);
  new(newnode);
  newnode^.info := x;
  newnode^.llink := CreateTree(nl, i);
  newnode^.rlink := CreateTree(nr, i);
  CreateTree := newnode;
end;
end;

procedure PLK(p : ptr);
begin
if p <> nil then begin
  plk(p^.Rlink);
  plk(p^.Llink);
  write(p^.info, ' ');
end;
end;

procedure plkstack(stack : ptr);
var root,p:ptr;
    flag : boolean;
    pr: boolean;

begin
p:=root;
{stack:=nil;}
flag := true;
while flag = true do begin
  while p <> nil do begin
   Push(p:false);
   p := p^.llink;
  end;
  p := Pop(pr);
  if pr=true then begin
  write(p^.info,' ');
  p:=nil;
  end
  else begin
   Push(p:true);
   p := p^.rlink;
  end;
  if stack=nil then begin flag:=false;
end;
end;

var root : ptr;
    n,i :integer;
begin
clrscr;
i:=0;

writeln('DEREVO');

write('Vvedite kolichestvo uzlov: ');
writeln;
readln(n);
root := CreateTree(n,i);
writeln('Psevdograficheskiy risunok: ');
PrintTree(root, n+5);
gotoxy(1, 2*n+3);
writeln('Gama-obhod (rekursiya): ');
PLK (root);
writeln;
writeln('Gama-obhod (stack): ');
plkstack(root);
readln;
end.