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

struct Baum
{
  int zahl;
  struct Baum *links, *rechts;
};

void einsort(struct Baum *wurzel, struct Baum *zgr);
void LWR(struct Baum *zgr);
int nodecount(struct Baum *zgr);
void printTreeLevel(struct Baum *zgr, int, int);
void printLevelorder(struct Baum *zgr);

int main(void)
{
  struct Baum *wurzel = NULL;
  struct Baum *zgr;
  int zahl;

  do
  {
    printf("Eingabe: ");
    scanf("%d", &zahl);
    if (zahl)
    {
      zgr = calloc(1,sizeof*zgr); // neues element angelegt
      zgr->zahl = zahl; // Element mit Wert von Zahl befüllt
      //zgr->links = zgr->rechts = NULL; // Zeiger des Elementes werden auf NULL gesetzt, dass ein Ende gefunden werden kann
      if (wurzel == NULL) wurzel = zgr;
      else einsort(wurzel, zgr); // Element soll über die Funktion einsort einsortiert werden

    }
  } while (zahl);
  LWR(wurzel);
  printf("\n\nnodes: %d\n\n", nodecount(wurzel));
  printLevelorder(wurzel);


  printf("\n");


  return 0;
}


void einsort(struct Baum *wurzel, struct Baum *zgr)
{
  int flag = 1;
  do
  {
    if (zgr->zahl < wurzel->zahl)
    {
      if (wurzel->links != 0) wurzel = wurzel->links; // gehe nach links
      else
      {
        flag = 0;
        wurzel->links = zgr;
      }

    }
    else
    {
      if (wurzel->rechts != 0) wurzel = wurzel->rechts; // gehe nach rechts
      else
      {
        flag = 0;
        wurzel->rechts = zgr;
      }
    }

  } while (flag);


}

void LWR(struct Baum *zgr) // Links Wurzel Rechts - aufsteigend sortiert
{
  if (zgr == NULL)
    return;
  if (zgr->links != NULL) LWR(zgr->links);
  printf(" %d", zgr->zahl);
  if (zgr->rechts != NULL) LWR(zgr->rechts);
}

// Zählen der Knoten im Baum
int nodecount(struct Baum *zgr)
{
  if (zgr == NULL)
    return 0;
  if (zgr->links == NULL && zgr->rechts == NULL)
    return 1;
  else
    return nodecount(zgr->links) +
    nodecount(zgr->rechts);
}

#define MAXX(x,y) ((x)>(y)?(x):(y))
int maxTreeDepth(struct Baum *zgr, int level)
{
  if (zgr == NULL)
    return 0;

  if (zgr->links == NULL && zgr->rechts == NULL)
    return level;

  return MAXX(maxTreeDepth(zgr->links, level + 1), maxTreeDepth(zgr->rechts, level + 1));
}

// Alle Knoten einer Stufe ermitteln
void printTreeLevel(struct Baum *zgr, int level, int zlevel)
{
  if (zgr == NULL)
    return;
  if (level == zlevel)
  {
    printf("%d ", zgr->zahl);
    return;
  }
  else
  {
    printTreeLevel(zgr->links, level + 1, zlevel);
    printTreeLevel(zgr->rechts, level + 1, zlevel);
  }
}

// Traversierung in Levelorder
void printLevelorder(struct Baum *zgr)
{
  int i, j = maxTreeDepth(zgr, 0);
  for (i = 0; i <= j; ++i, puts(""))
    printTreeLevel(zgr, 0, i) ;
}