{ Gefaedelte Baum - DEMO fuer Datenstrukturen Vorlesung, SS03-Benn }
{ Autor: Dipl.-Ing. Thomas Speiser                                 }
{ Source from: http://Codes.TurboTools.de                          }

program gefaedelte_baeume;
uses Crt;
type ref = ^baum;
       baum = record
       value: char;
       left, right: ref;
       gefaedelt: boolean
end;

var GTree,GNode: ref;
    count: integer;
    c: char;

function first(k: ref): ref;
begin
     if k = nil then first:=nil else
     while (k^.left <> nil) do k:=k^.left;
     first:=k;
end;

function next(k: ref): ref;
begin
     if k^.gefaedelt then next:=k^.right
                     else next:=first(k^.right);
end;

procedure inorder(k: ref);
begin
     k:=first(k);
     while (k <> nil) do
     begin if k^.gefaedelt then write('*');
           write(k^.value);
           k:=next(k);
     end;
end;

function Set_GTree(i: char): ref;
var w: ref;
begin
   new(w);
   w^.left:=nil;
   w^.right:=nil;
   w^.gefaedelt:=false;
   w^.value:=i;
   Set_GTree:=w;
end;

procedure Set_Left(p: ref; i: char);
var k: ref;
begin
   new(k);
   k^.left:=nil;
   k^.right:=p;
   k^.gefaedelt:=true;
   k^.value:=i;
   p^.left:=k;
end;

procedure Set_Right(p: ref; i: char);
var k: ref;
begin
   new(k);
   k^.left:=nil;
   k^.right:=p^.right;
   k^.gefaedelt:=p^.gefaedelt;
   p^.gefaedelt:=false;
   k^.value:=i;
   p^.right:=k;
end;


procedure Menu_Set;
begin
ClrScr;
writeLN('Gefaedelte T R E E - D E M O ! ! !');
writeLN;
writeLN('d - Inorder');
writeLN('______________x_');
writeLN('e - Menu_set');
writeLN('q - Ende_Gel„nde');
writeLN;
end;

begin
TextMode(CO80 xor Lo(LastMode)+Font8x8 xor LASTMODE);
Menu_Set;
repeat
c:=readkey;
case c of
'd': begin
     writeLN;
     Inorder(GTree);
     writeLN;
     end;
'x': begin
      GTree:=Set_GTree('C');
      GTree:=First (GTree);
      Set_Left     (GTree,'B');
      GTree:=First (GTree);
      Set_Left     (GTree,'A');
      GTree:=First (GTree);
      GTree:=Next  (GTree);
      GTree:=Next  (GTree);
      GTree^.right:=Set_GTree('F');
      GTree:=GTree^.right;
      GTree^.left:=Set_GTree('D');
      GTree:=First (GTree);

{      GTree:=Next  (GTree);
{      GTree:=Next  (GTree);
      GTree^.right:=Set_GTree('E');
      Set_Right    (GTree,'F');
      Set_Left     (GTree,'G');
      Set_Right    (GTree,'I');}
     end;
{________________}
'e': Menu_Set;
'q': Halt(1);
end;
until count = 1;
end.