Programmieren

Hauptseite -
Welches System? -
Hardware -
Software -
Textverarbeitung -

Internet
MausNet
Programmieren
Verweise
Über

TOS - Algorithmen - Beispiele - weitere Informationen

Beispiel: Baum

Die folgenden Beispiele zeigen einen Binärbaum.

Sprache	C	Pascal	Modula
Beispiel	baum.c	baum.pas	baum.mod

baum.c

/* Da der Datentyp des Baums erst bei einer konkreten Anwendung  */
/* feststeht, ist der Baum nur als Beispiel und nicht als Modul  */
/* programmiert.                                                 */

#include 
#include 

typedef long BaumKeyType;
typedef struct baum_knoten {
   BaumKeyType Key;
   struct baum_knoten *Left,*Right;
} BaumElement, *BaumKnoten;
typedef BaumKnoten Baum;

void BaumCreate(Baum *MyBaum)
{
   *MyBaum = NULL;
}

void BaumInsert(Baum *MyBaum, BaumKeyType Daten)
{  BaumKnoten Element;

   if (*MyBaum == NULL)
   {
      Element = malloc(sizeof(BaumElement));
      if (Element != NULL)
      {
         Element->Key = Daten;
         Element->Right = NULL;
         Element->Left = NULL;
         *MyBaum = Element;
      }
   }
   else if (Daten < (*MyBaum)->Key)
      BaumInsert(&((*MyBaum)->Left), Daten);
   else
      BaumInsert(&((*MyBaum)->Right), Daten);
}

static void PutOut(BaumKnoten *Old)
{  BaumKnoten CopyOld, DaddyMaxLeft, MaxLeft;

   CopyOld = *Old;
   if (CopyOld->Right == NULL)
      *Old = CopyOld->Left;
   else if (CopyOld->Left == NULL)
      *Old = CopyOld->Right;
   else
   {
      DaddyMaxLeft = CopyOld->Right;
      if (DaddyMaxLeft->Left == NULL)
      {
         DaddyMaxLeft->Left = CopyOld->Left;
         *Old = DaddyMaxLeft;
      }
      else
      {
         MaxLeft = DaddyMaxLeft->Left;
         while (MaxLeft->Left != NULL)
         {
            DaddyMaxLeft = MaxLeft;
            MaxLeft = DaddyMaxLeft->Left;
         }
         MaxLeft->Left = CopyOld->Left;
         DaddyMaxLeft->Left = MaxLeft->Right;
         MaxLeft->Right = CopyOld->Right;
         *Old = MaxLeft;
      }
   }
   free(CopyOld);
}

void BaumRemove(Baum *Tree, BaumKeyType Key)
{
   if (*Tree != NULL)
   {
      if (Key < (*Tree)->Key)
         BaumRemove(&((*Tree)->Left), Key);
      else if (Key > (*Tree)->Key)
         BaumRemove(&((*Tree)->Right), Key);
      else
         PutOut(Tree);
   }
}

BaumKnoten BaumFind(Baum Tree, BaumKeyType Key)
{
   if (Tree != NULL)
   {
      if (Key < Tree->Key)
         return(BaumFind(Tree->Left, Key));
      else if (Key > Tree->Key)
         return(BaumFind(Tree->Right, Key));
      else
         return(Tree);
   }
   else
      return(NULL);
}

void BaumWalkPraeorder(Baum Tree)
{
   if (Tree!=NULL)
   {
      /* tue etwas mit aktuellen Knoten */
      BaumWalkPraeorder(Tree->Left);
      BaumWalkPraeorder(Tree->Right);
   }
}

void BaumWalkPostorder(Baum Tree)
{
   if (Tree!=NULL)
   {
      BaumWalkPostorder(Tree->Left);
      BaumWalkPostorder(Tree->Right);
      /* tue etwas mit aktuellen Knoten */
   }
}

void BaumWalkInorder(Baum Tree)
{
   if (Tree!=NULL)
   {
      BaumWalkInorder(Tree->Left);
      /* tue etwas mit aktuellen Knoten */
      BaumWalkInorder(Tree->Right);
   }
}

baum.pas

(* Da der Datentyp des Baums erst bei einer konkreten Anwendung  *)
(* feststeht, ist der Baum nur als Beispiel und nicht als Modul  *)
(* programmiert.                                                 *)

type
   BaumKeyType = long_integer;
   BaumKnoten = ^BaumElement;
   BaumElement = record
      Key : BaumKeyType;
      Left, Right : BaumKnoten;
   end;
   Baum = BaumKnoten;

procedure BaumCreate(var MyBaum:Baum);
begin
   MyBaum := nil;
end;

procedure BaumInsert(var MyBaum:Baum; Daten:BaumKeyType);
var
   Element : BaumKnoten;
begin
   if (MyBaum = nil) then
   begin
      new(Element);
      Element^.Key := Daten;
      Element^.Right := nil;
      Element^.Left := nil;
      MyBaum := Element;
   end
   else if (Daten < MyBaum^.Key) then
      BaumInsert(MyBaum^.Left, Daten)
   else
      BaumInsert(MyBaum^.Right, Daten);
end;

procedure BaumRemove(var Tree:Baum; Key:BaumKeyType);
   procedure PutOut(var Old:BaumKnoten);
   var
      CopyOld, DaddyMaxLeft, MaxLeft : BaumKnoten;
   begin
      CopyOld := Old;
      if (CopyOld^.Right = nil) then
         Old := CopyOld^.Left
      else if (CopyOld^.Left = nil) then
         Old := CopyOld^.Right
      else
      begin
         DaddyMaxLeft := CopyOld^.Right;
         if (DaddyMaxLeft^.Left = nil) then
         begin
            DaddyMaxLeft^.Left := CopyOld^.Left;
            Old := DaddyMaxLeft;
         end
         else
         begin
            MaxLeft := DaddyMaxLeft^.Left;
            while (MaxLeft^.Left <> nil) do
            begin
               DaddyMaxLeft := MaxLeft;
               MaxLeft := DaddyMaxLeft^.Left;
            end;
            MaxLeft^.Left := CopyOld^.Left;
            DaddyMaxLeft^.Left := MaxLeft^.Right;
            MaxLeft^.Right := CopyOld^.Right;
            Old := MaxLeft;
         end;
      end;
      dispose(CopyOld);
   end;
begin
   if (Tree <> nil) then
   begin
      if (Key < Tree^.Key) then
         BaumRemove(Tree^.Left, Key)
      else if (Key > Tree^.Key) then
         BaumRemove(Tree^.Right, Key)
      else
         PutOut(Tree);
   end;
end;

function BaumFind(Tree:Baum; Key:BaumKeyType):BaumKnoten;
begin
   if (Tree <> nil) then
   begin
      if (Key < Tree^.Key) then
         BaumFind := BaumFind(Tree^.Left, Key)
      else if (Key > Tree^.Key) then
         BaumFind := BaumFind(Tree^.Right, Key)
      else
         BaumFind := Tree;
   end
   else
      BaumFind := nil;
end;

procedure BaumWalkPraeorder(Tree:Baum);
begin
   if (Tree <> nil) then
   begin
      (* tue etwas mit aktuellen Knoten *)
      BaumWalkPraeorder(Tree^.Left);
      BaumWalkPraeorder(Tree^.Right);
   end;
end;

procedure BaumWalkPostorder(Tree:Baum);
begin
   if (Tree <> nil) then
   begin
      BaumWalkPostorder(Tree^.Left);
      BaumWalkPostorder(Tree^.Right);
      (* tue etwas mit aktuellen Knoten *)
   end;
end;

procedure BaumWalkInorder(Tree:Baum);
begin
   if (Tree <> nil) then
   begin
      BaumWalkInorder(Tree^.Left);
      (* tue etwas mit aktuellen Knoten *)
      BaumWalkInorder(Tree^.Right);
   end;
end;

baum.mod

(* Da der Datentyp des Baums erst bei einer konkreten Anwendung  *)
(* feststeht, ist der Baum nur als Beispiel und nicht als Modul  *)
(* programmiert.                                                 *)

FROM Heap IMPORT Allocate, Deallocate;
FROM SYSTEM IMPORT TSIZE;

TYPE
   BaumKeyType = LONGINT;
   BaumKnoten = POINTER TO BaumElement;
   BaumElement = RECORD
      Key : BaumKeyType;
      Left, Right : BaumKnoten;
   END;
   Baum = BaumKnoten;

PROCEDURE BaumCreate(VAR MyBaum:Baum);
BEGIN
   MyBaum := NIL;
END BaumCreate;

PROCEDURE BaumInsert(VAR MyBaum:Baum; Daten:BaumKeyType);
VAR
   Element : BaumKnoten;
BEGIN
   IF (MyBaum = NIL) THEN
      Allocate(Element, TSIZE(BaumElement));
      Element^.Key := Daten;
      Element^.Right := NIL;
      Element^.Left := NIL;
      MyBaum := Element;
   ELSIF (Daten < MyBaum^.Key) THEN
      BaumInsert(MyBaum^.Left, Daten);
   ELSE
      BaumInsert(MyBaum^.Right, Daten);
   END;
END BaumInsert;

PROCEDURE BaumRemove(VAR Tree:Baum; Key:BaumKeyType);
   PROCEDURE PutOut(VAR Old:BaumKnoten);
   VAR
      CopyOld, DaddyMaxLeft, MaxLeft : BaumKnoten;
   BEGIN
      CopyOld := Old;
      IF (CopyOld^.Right = NIL) THEN
         Old := CopyOld^.Left;
      ELSIF (CopyOld^.Left = NIL) THEN
         Old := CopyOld^.Right;
      ELSE
         DaddyMaxLeft := CopyOld^.Right;
         IF (DaddyMaxLeft^.Left = NIL) THEN
            DaddyMaxLeft^.Left := CopyOld^.Left;
            Old := DaddyMaxLeft;
         ELSE
            MaxLeft := DaddyMaxLeft^.Left;
            WHILE (MaxLeft^.Left # NIL) DO
               DaddyMaxLeft := MaxLeft;
               MaxLeft := DaddyMaxLeft^.Left;
            END;
            MaxLeft^.Left := CopyOld^.Left;
            DaddyMaxLeft^.Left := MaxLeft^.Right;
            MaxLeft^.Right := CopyOld^.Right;
            Old := MaxLeft;
         END;
      END;
      Deallocate(CopyOld, TSIZE(BaumElement));
   END PutOut;
BEGIN
   IF (Tree # NIL) THEN
      IF (Key < Tree^.Key) THEN
         BaumRemove(Tree^.Left, Key);
      ELSIF (Key > Tree^.Key) THEN
         BaumRemove(Tree^.Right, Key);
      ELSE
         PutOut(Tree);
      END;
   END;
END BaumRemove;

PROCEDURE BaumFind(Tree:Baum; Key:BaumKeyType) : BaumKnoten;
BEGIN
   IF (Tree # NIL) THEN
      IF (Key < Tree^.Key) THEN
         RETURN BaumFind(Tree^.Left, Key);
      ELSIF (Key > Tree^.Key) THEN
         RETURN BaumFind(Tree^.Right, Key);
      ELSE
         RETURN Tree;
      END;
   ELSE
      RETURN NIL;
   END;
END BaumFind;

PROCEDURE BaumWalkPraeorder(Tree:Baum);
BEGIN
   IF (Tree # NIL) THEN
      (* tue etwas mit aktuellen Knoten *)
      BaumWalkPraeorder(Tree^.Left);
      BaumWalkPraeorder(Tree^.Right);
   END;
END BaumWalkPraeorder;

PROCEDURE BaumWalkPostorder(Tree:Baum);
BEGIN
   IF (Tree # NIL) THEN
      BaumWalkPostorder(Tree^.Left);
      BaumWalkPostorder(Tree^.Right);
      (* tue etwas mit aktuellen Knoten *)
   END;
END BaumWalkPostorder;

PROCEDURE BaumWalkInorder(Tree:Baum);
BEGIN
   IF (Tree # NIL) THEN
      BaumWalkInorder(Tree^.Left);
      (* tue etwas mit aktuellen Knoten *)
      BaumWalkInorder(Tree^.Right);
   END;
END BaumWalkInorder;

English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
11 März 2002.
Home - Mail an den Webmaster - Impressum