/* Implementation des Moduls BinBaum.  Die Funktionen sind nur gruppiert und 
   nicht anderweitig kommentiert, da sie weitgehend trivial sind. */

#include "BinBaum.h"
#include <stdlib.h>             // NULL
#include <iostream>

using namespace std;

/* Knoten eines binaeren Baumes zum Speichern ganzer Zahlen. */
struct BinBaumKnotenT
{
   int wert;                    // Der gespeicherte Wert
   BinBaumKnotenT *linkerAst;   // Zeiger auf den linken Ast oder NULL
   BinBaumKnotenT *rechterAst;  // Zeiger auf den rechten Ast oder NULL
   BinBaumKnotenT *stamm;       // Zeiger auf den (naechsten) Stamm oder NULL
};


BinBaumKnotenT & neuerKnoten()
{ 
   /* Speicher fuer den neuen Knoten besorgen. */
   BinBaumKnotenT & ergebnis = *new BinBaumKnotenT;

   /* Verzeigerung auf definierte Werte setzen.  Der Knoten haengt in noch
      keinem Baum. */
   ergebnis.linkerAst = NULL;
   ergebnis.rechterAst = NULL;
   ergebnis.stamm = NULL;
   
   /* Den Wert auf einen Defaultwert setzen. */
   setzeWert(ergebnis, 0);

   return ergebnis;
}

void zerstoereKnoten(BinBaumKnotenT & opfer)
{
   delete &opfer;
}


/* Zugriff auf den gespeicherten Wert */
int leseWert(BinBaumKnotenT const & knoten)
{ return knoten.wert; }

void setzeWert(BinBaumKnotenT& knoten, int neuerWert)
{ knoten.wert = neuerWert; }


/* Navigation zu den Nachbarn */
BinBaumKnotenT * linkerAst(BinBaumKnotenT const & stamm) {
   if (NULL == stamm.linkerAst) {
      cerr << "Versuche, leerem linken Ast zu folgen!" << endl;
   }
   return stamm.linkerAst;
}

BinBaumKnotenT * rechterAst(BinBaumKnotenT const & stamm) {
   if (NULL == stamm.rechterAst) {
      cerr << "Versuche, leerem rechten Ast zu folgen!" << endl;
   }
   return stamm.rechterAst;
}

BinBaumKnotenT * stamm(BinBaumKnotenT const & ast)
{
   if (NULL == ast.stamm) {
      cerr << "Versuche, leerem Stamm zu folgen!" << endl;
   }
   return ast.stamm;
}


/* Abfragen zur Struktur */
bool linkerAstExistiert(BinBaumKnotenT const & knoten)
{ return knoten.linkerAst != NULL; }

bool rechterAstExistiert(BinBaumKnotenT const & knoten)
{ return knoten.rechterAst != NULL; }

bool stammExistiert(BinBaumKnotenT const & knoten)
{ return knoten.stamm != NULL; }


/* Struktur des Baumes Aendern: Aeste hinzufuegen oder absaegen.  Der Stamm
   bleibt.  */
void setzeLinkenAst(BinBaumKnotenT & stammKnoten, 
                    BinBaumKnotenT & neuerLinkerAstKnoten)
{
   stammKnoten.linkerAst = & neuerLinkerAstKnoten;
   neuerLinkerAstKnoten.stamm = & stammKnoten;
}

void setzeRechtenAst(BinBaumKnotenT & stammKnoten,
                     BinBaumKnotenT & neuerRechterAstKnoten)
{
   stammKnoten.rechterAst = & neuerRechterAstKnoten;
   neuerRechterAstKnoten.stamm = & stammKnoten;
}


/* Interne Hilfsfunktion.  Ueber die oeffentliche Schnittstelle kann man
   einen Teilbaum nur aus dem umgebenden Baum aushaengen.  Dazu muss aber
   auch beim umgebenden Baum bekanntgegeben werden, dass der Teilbaum weg
   ist. */
static void loescheStamm(BinBaumKnotenT & ast)
{
   ast.stamm = NULL;
}

void loescheLinkenAst(BinBaumKnotenT & stammKnoten)
{
   if(linkerAstExistiert(stammKnoten)) {
      loescheStamm(*linkerAst(stammKnoten));
   }
   stammKnoten.linkerAst = NULL;
}

void loescheRechtenAst(BinBaumKnotenT & stammKnoten)
{
   if(rechterAstExistiert(stammKnoten)) {
      loescheStamm(*rechterAst(stammKnoten));
   }
   stammKnoten.rechterAst = NULL;
}