/***************************************

              Routine di Sort
           last update 10/07/87
      AMIGA-Version by Frank Kremser
PC-Original-Version by Dr. Edgar Huckent
       (C) 1987  by Markt & Technik

****************************************

	Ordinamento mediante albero
      Esempio di procedura ricorsiva

***************************************/

#include <stdio.h>
#include <ctype.h>

/* Struttura di un nodo dell' albero */
struct knoten
{
  char *word;
  int haeuf;             /* Frequenza */
  struct knoten *links;  /* Successore sinistro */
  struct knoten *rechts; /* Successore destro   */
};

/* crea un nodo con parola = w */
struct knoten *mache_knoten(p,w)
struct knoten *p;    /* Precedente */
char *w;             /* Parola (Etichetta) */
{
  int cond;

  if (p == NULL)
    {
     /* Nuovo nodo */
     p = malloc(sizeof(struct knoten));
     p->word = malloc(strlen(w) + 1);
     if (p->word != NULL) strcpy(p->word,w);
     p->haeuf = 1;
     p->links = p->rechts = NULL;
    }
  else
    if ((cond = strcmp(w,p->word)) == 0)
            p->haeuf++;             /* C'e gia' una parola uguale */
    else if (cond < 0)              /* aggiungi a sinistra */
            p->links = mache_knoten(p->links,w);
    else                            /* aggiungi a destra */
            p->rechts = mache_knoten(p->rechts,w);
    return(p);
}   /* end mache_knoten */

/* Stampa ricorsiva dell' albero */
void drucke_knoten(p)
struct knoten *p;
{
  if (p != NULL)
    {
     drucke_knoten(p->links);
     printf("%4d %s\n",p->haeuf,p->word);
     drucke_knoten(p->rechts);
    }
}   /* fine stampa  */

void main()
{
  struct knoten *wurzel;
  char buffer[80];
  int t;

  wurzel = NULL;
  for (;;)
    {
     printf("Prossima parola : ");
     gets(buffer);
     if (strlen(buffer) == 0) break;
     t = buffer[0];
     if (isalpha(t))
       wurzel = mache_knoten(wurzel,buffer);
    }
  drucke_knoten(wurzel);
  printf ("\n\n");
}   /* fine main */