/* Loesung der 4. Aufgabe (AGS 3.29) */


typedef struct Nodeelem *Ptr;
typedef struct Nodeelem {
  int key;
  Ptr left, right;
} Node;

/*
 * Einfügen des Baumes node in Baum *tree
 */
void node_insert(Ptr *tree, Ptr node) {
  if (node == NULL) return;
  if (*tree == NULL) *tree = node;
  else
    if (node->key < (*tree)->key) node_insert(&(*tree)->left, node);
    else node_insert(&(*tree)->right, node);
  return;
}

/*
 * Löschen des Knotens mit dem Eintrag wert
 * aus dem Baum *tree
 */
void node_del(Ptr *tree, int wert) {
  Ptr q;
  if (*tree != NULL) {
    /*
     * Knoten gefunden..
     */
    if ((*tree)->key == wert) {
      q = *tree;
      *tree = q->left;
      /*
       * Einfügen von Baum B in A
       */
      node_insert(tree, q->right);
      /*
       * Speicherplatz freigeben
       */
      
      free(q);
    }
    /*
     * anderenfalls weitere Suche im linken oder 
     * rechten Nachfolger des Suchbaumes
     */
    else
      if (wert < (*tree)->key) node_del(&(*tree)->left, wert);
      else node_del(&(*tree)->right, wert);
  }
  return;
}