// bintree.c
// zeigt zwei Grundaufgaben mit Bäumen

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

// Datenstruktur für einen Knoten: Inhalt und zwei Zeiger auf die nächsten Knoten

typedef struct node
{
  int wert;
  struct node* left;
  struct node* right;
} t_node;

// Alle Knoten eines Baum in der Reihenfolge
// Wurzel -> Knoten -> Blätter (top-down) erfassen.
// printf steht stellvertretend fÜr die Aktion mit dem Knoten


void topdown(t_node* node)
{
  if (node != NULL) {
    printf("%i\n", node->wert);
    topdown(node->left);
    topdown(node->right);
  }
}


// Alle Knoten eines Baum in der Reihenfolge
// Blätter -> Knoten (bottom-up) erfassen
// printf steht stellvertretend fÜr die Aktion mit dem Knoten

void bottomup(t_node* node)
{
  if (node != NULL) {
    bottomup(node->left);
    bottomup(node->right);
    printf("%i\n", node->wert);
  }
}


int main(void)
{
  t_node *root;
  t_node *nodelist[11];
  int i;
  int size = sizeof (t_node);

  /* Beispiel eines Baumes:

               0
               |
      +--------+--------+
      |                 |
      1                  6
      |                 |
  +---+---+         +---+---+
  |       |         |       |
  2       3         7       8
          |                 |
      +---+---+         +---+---+
      |       |         |       |
      4       5         9      10

  Der Aufbau des Baumes erfolgt hier auf eine sehr einfache Art:
  Zuerst werden die einzelnen Knoten erzeugt, Inhalt des Knotens ist eine
  fortlaufende Nummer. Der Inhalt kann jedoch beliebig sein: ein Zeichen,
  eine Zeichenkette, eine Struktur.
  Die Adressen der Knoten merken wir uns vorläufig in einem Vektor nodelist[].
  Bei dieser Methode werden also zuerst "frei herumliegende Knoten" erzeugt.
  Öfters wachsen Bäume aus sich selber heraus, d. ausgehend von einem Knoten
  erzeugt man sich weitere Knoten und hängt sie an den Knoten.
  */

  for (i = 0; i < 11; i++) {
    nodelist[i] = (t_node*) malloc(size);   // Speicherplatz anfordern
    nodelist[i]->wert = i;                  // Inhalt festlegen
    nodelist[i]->left = NULL;               // Zeiger auf nächsten Knoten links
    nodelist[i]->right = NULL;              // Zeiger auf nächsten Knoten rechts
  }

  // Jetzt stellen wir die Verbindungen zwischen den Knoten her,
  // d.h bauen den eigentlichen Baum auf.

  root = nodelist[0];
  nodelist[0]->left = nodelist[1];
  nodelist[0]->right = nodelist[6];

  nodelist[1]->left = nodelist[2];
  nodelist[1]->right = nodelist[3];

  nodelist[3]->left = nodelist[4];
  nodelist[3]->right = nodelist[5];

  nodelist[6]->left = nodelist[7];
  nodelist[6]->right = nodelist[8];

  nodelist[8]->left = nodelist[9];
  nodelist[8]->right = nodelist[10];

  // Kontrollausgabe

  for (i = 0; i < 11; i++) {
    printf("%2i: %2i left = %p, right = %p\n",
      i, nodelist[i]->wert, nodelist[i]->left, nodelist[i]->right);
  }

  // Jetzt brauchen wir die Liste eigentlich nicht mehr und zeigen wie man

  // den Baum von oben nach unten durchläuft

  printf("List the tree top-down\n");
  topdown(root);

  // den Baum von unten nach oben durchläuft

  printf("List the tree bottom up\n");
  bottomup(root);

  return 0;
}