#include <stdio.h>
#include <stdlib.h>

typedef struct t_node{
    char*   word;
    struct t_node* left;    
    struct t_node* right;
}Treenode;


/*
  Liefert einen leeren Baum zurueck
 */
Treenode* mkEmpty(void);


/*
  Verhaelt sich wie _isEmpty, der Parameter w wird vernachlaessig.
  Grund: Funktion soll mit prad() aufgerufen werden koennen.
  @param Treenode* : Baum der auf Leere geprueft wird.
  return: 1, wenn leer sonst 0.
*/
int isEmpty(char* w, Treenode* ptr);


/*
  prueft, ob w im Baum enthalten ist
  @param char*: Wort, deren Inhalt im Baum gesucht wird.
  @param Treenode*: Baum, in welchem gesucht wird.
  return: 1, wenn das Wort im Baum vorhanden ist, sonst 0.
 */
int isIn(char* w, Treenode* ptr);

/*
  Erzeugt einen neuen Baum mit der Wurzel w
  @param char*: Das Wort, mit dem der Baum erzeugt wird.
  return: der neue Baum.
 */
Treenode* mkOne(char* w);


/*
  Produziert einen Baum, welcher keine linken Teilbaeume bestitzt.
  Der Kopf ist das kleinste Element.
  @param Treenode*: Der Baum, welcher sortiert werden soll.
  return Treenode*: Ein sortierter Baum ohne linke Teilbaeume.
 */
Treenode* sortToRight(Treenode* ptr);


/*
  Produziert einen Baum, welcher keine rechten Teilbaeume bestitzt.
  Der Kopf ist das groesste Element.
  @param Treenode*: Der Baum, welcher sortiert werden soll.
  return Treenode*: Ein sortierter Baum ohne rechte Teilbaeume.
 
 */
Treenode* sortToLeft(Treenode* ptr);


/* --- BONUS ---
  Balanciert den Baum aus.
  Es wird u.U. nicht immer ganz aufgehen.
  @param Treenode*: Der Baum, der ausbalanciert werden soll.
  return Treenode*: Der ausbalancierte Baum.
 */
Treenode* sortToBalance(Treenode* ptr);


/*	
  Liefert die Anzahl der Elemente im Baum.
  w verhaelt sich als dummy.
  Grund: Funktion soll mit prad() aufgerufen werden koennen.
  @param Treenode*: Baum, von dem die Anzahl Elemente bestimmt
                    werden soll. Ist der Baum leer, so sind
                    0 Elemente im Baum!
*/
int card(char* w, Treenode* ptr) ;


/*
  Liefert die Ebene, auf welcher sich w im Baum befindet.
  Der Wurzelknoten befindet sich auf 1.
  @param char*: Wort dessen Tiefe im Baum gesucht ist.
  @param Treenode*: Baum in dem w gesucht wird.
  return: Ebene, auf welcher sich w befindet.
  z.B.	1: w ist Wurzelknoten.
	0: w ist nicht im Baum.
 */
int ord(char* w, Treenode* ptr);

/*
  Haengt w in den bestehenden Baum ein.
  @param char*: Wort, welches in den Baum gehaengt werden soll.
                Ist das Wort schon vorhanden wird es nicht erneut
		eingefuegt und der bestehende Baum unveraendert 
		zurueckgeliefert.
  @param Treenode*: Der Baum, welcher um w erweitert wird.
                Ist der Baum leer, so wird ein neuer Baum mit w
		erzeugt.
  return Treenode*: der neue Baum.
*/
Treenode* append(char* w, Treenode* ptr);


/* 
   Produziert eine Projektion des Baumes auf die Standardausgabe.
   Hierbei soll die Baumstruktur erkennbar sein.
   @param Treenode*: Der Baum, der ausgegeben werden soll
*/
void output(Treenode* ptr);


/* ---BONUS---
  Entfernt w aus dem Baum, wenn w vorhanden ist :-)
  Ist der Baum nach dem entfernen von w leer, so ist ein leerer Baum
  zurueckzugeben. 
  @param char*: Wort, welches aus dem Baum entfernt wird. Ist das Wort
                nicht vorhanden, so wird der Baum unverandert zurueckgeliefert.
  @param Treenode*: Der Baum. War der Baum schon vor dem Aufruf leer, so
                wird auch ein leerer Baum zurueckgeliefert.
*/
Treenode* removeTree(char* w, Treenode* ptr);


/*
  Entfernt w und alles was dran haengt aus dem Baum,
  wenn w vorhanden ist :-)
  @param char*: Wort, welches aus dem Baum geloescht wird.
                Geloescht wird ebenfalls der Baum, welcher an w 
		dranhaengt.
		Ist w nicht vorhanden, so bleibt der Baum unveraendert.
  @param Treenode*: Der Baum. Ist der Baum leer, so ist das
                    Ergebnis ebenfalls ein leerer Baum.
  return Treenode*: Der resultierende Baum
*/
Treenode* removePartTree(char* w, Treenode* ptr);


/*
   Zerstoert den Baum.
   @param Treenode*: Der Baum der zerstoert werden soll.
                     Handelt es sich bereits um einen leeren Baum,
		     so wird dieser zurueckgegeben.
   return Treenode*: ein leerer Baum
*/
Treenode* destroyTree(Treenode* ptr);

/*
  ================= Funktionsbeschreibungen ==================
 */
/*
Funktion sort:
@param1: Funktion f mit dem Parameter Treenode* und dem Rueckgabewert Treenode*.
@param2: Treenode* ptr
return: Treenode*

Funktion change:
@param1: Funktion f mit den Parametern (char* und Treenode*) und dem Rueckgabewert Treenode*.
@param2: char* w
@param3: Treenode* ptr
return: Treenode*

Funktion prad:
@param1: Funktion f mit den Parametern (char* und Treenode*) und dem Rueckgabewert int.
@param2: char* w
@param3: Treenode* ptr
return: int
*/