{ ------------------------------------------------------------------------------------------------------------------- }
{                                                                                                                     }
{ Die Unit stellt einen inhaltslosen Datentypen TBinBaum zur Verfügung. Um einen Binärbaum mit Inhalt zu erhalten,    }
{ muss eine hiervon abgeleitete Klasse erstellt werden, z. B.:                                                        }
{                                                                                                                     }
{  type TIntBinBaum = class(TBinBaum)                                                                                 }
{         public                                                                                                      }
{           content: integer;                                                                                         }
{           constructor Create(w: Integer);                                                                           }
{           function contentToString: string; override;                                                               }
{       end;                                                                                                          }
{                                                                                                                     }
{  Ein Binärbaum kann entweder leer sein (NIL) oder eine Wurzel mit zwei evtl. leeren Teilbäumen righttree, lefttree  }
{                                                                                                                     }
{ ------------------------------------------------------------------------- Tool zum Binärbaum ---------------------- }

unit Binbaum;

interface

type
      TBinBaum = class
         private
         // Gekapselte Attribute; Zugriff nur über Methode next() möglich.
         leftTree, rightTree: TBinBaum;

         protected
         // Möglichst viele der Methoden sind geschützt, um die Abstraktheit der Klasse BinBaum zu simulieren.
         constructor Create;
                                { Erzeugt ein Blatt, d.h. "leeres Element mit righttree=lefttree=NIL                  }
         destructor Destroy;
                                { Zerstört das Element inklusive seiner Teilbäume                                     }

         function append (which: TBinBaum; where: Char) : TBinBaum;
                                { Fügt einen Teilbaum an das aktuelle Baumelement links bzw. rechts an.               }
                                { HINWEIS: Ein eventuell vorhandener Teilbaum wird abgehängt und zurückgegeben        }
                                { Diese Methode wird (mit which=Nil) auch zum Löschen eines Teilbaumes genutzt.       }

         function deleteNext (where: Char) : TBinBaum;
                                { Löscht ab dem aktuellen Baumelement den linken bzw. rechten Teilbaum.               }
                                { HINWEIS: Ein eventuell vorhandener Teilbaum wird abgehängt und zurückgegeben        }
                                { Diese Methode ruft (mit which=Nil) die Methode append() auf.                        }

         function deleteAndGetNext (where: Char) : TBinBaum;
                                { Löscht den aktuellen Knoten und gibt den linken bzw. rechten Nachfolger zurück.     }
                                { ACHTUNG: Der jeweils andere Nachfolger geht dabei verloren!                         }
                                { Die Methode sollte nur bei Halbbäumen angewendet werden.                            }

         function  isLeaf: Boolean;
                                { Liefert "true", wenn das aktuelle Element leere Teilbäume hat.                      }

         public
         // Diese Methoden werden in BaumAnzeige verwendet und müssen also public sein;
         // alternativ könnte eine Klasse ZeigBaum von BinBaum abgeleitet werden.
         function isEmpty: boolean;
                                { Liefert "true" wenn der Baum leer ist, d. h. der Baum ist = NIL                     }
         function next (where: Char): TBinBaum;
                                { Liefert den linken oder rechten Teilbaum im Funktionsergebnis zurück. }
         function contentToString: string; virtual; abstract;
                                { Abstrakte Methode zur Darstellung des Inhalts auf dem Bildschirm (Editfeld, etc.)   }
       end;

implementation

constructor TBinBaum.Create;
begin
  rightTree:= NIL;                                                { Rechter und linker Teilbaum auf NIL, einen Inhalt gibt     }
  leftTree:= NIL;                                                 { es auf dieser Hierarchieebene noch nicht.                  }
end;

destructor TBinBaum.Destroy;
begin
  leftTree.Free;                                                  { wenn noch links etwas ist, dann dies zerstören             }
  rightTree.Free;                                                 { wenn noch rechts etwas ist, dann auch das zerstören        }
  inherited Destroy;                                              { und schließlich sich selbst (ererbte Methode von TObject)  }
end;

function TBinBaum.isEmpty: boolean;
begin
  isEmpty := (Self=NIL);                                          { Leer heißt, dass der Zeiger "Self" auf NIL zeigt           }
end;

function TBinBaum.next (where: Char): TBinBaum;
begin
  case Upcase (where) of
   'L': IF not isEmpty then next := leftTree else next := Nil;
   'R': IF not isEmpty then next := rightTree else next := Nil;
   else next := Nil;
  end;
end;

function TBinBaum.append (which: TBinBaum; where: Char) : TBinBaum;
begin

  { ***** HIER ERGÄNZEN! ***** }

end;

function TBinBaum.deleteNext (where: Char) : TBinBaum;
begin
  deleteNext := self.append (Nil, where);
end;

function TBinBaum.deleteAndGetNext (where: Char) : TBinBaum;
var hilf : TBinBaum;
begin
  hilf   := self.next (where);
  self.append (Nil, where);
  self.destroy;
  deleteAndGetNext := hilf;
end;

function  TBinBaum.isLeaf: Boolean;
begin

  { ***** HIER ERGÄNZEN! ***** }

end;

end.