/* Binarno drvo */

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

#define MAXREC 100

typedef struct drvo_tag
{
   char *rec;                 	/* pokazuje na tekst */
   int broj;                  	/* broj pojavljivanja */
   struct drvo_tag *levo;       /* levi grana */
   struct drvo_tag *desno;      /* desna grana */
} drvo;	                        /* cvor drveta */

/* Prototipovi funkcija */
drvo *addtree(drvo *, char *);
void treeprint(drvo *);
int uzmi_rec(char *, int);
drvo *talloc( void );
char *strdpl(char *);

int main()
{
   drvo *koren;
   char rec[MAXREC];
   koren = NULL;

   /* U "mrtvoj" petlji se vrsi formiranje drveta */
   while( 1 )
   {
      /* Uzima se rec sa ulaza najvise MAXREC karaktera promenljiva
         kraj  cuva informaciju da li se siglo do EOF-a*/
      int kraj = uzmi_rec(rec, MAXREC);
      /* Ukoliko rec nije prazna dodaje se u drvo */
      if(strlen(rec))
         koren = addtree( koren, rec);
      /* Ukoliko na ulazu nema vise reci iskace se iz "mrtve" petlje*/
      if(kraj == EOF)
         break;
   }
   /* Ispisuje se drvo */
   treeprint(koren);

   return 0;
}

/* Funkcija addtree - dodaje cvor sa tekstom na koji pokazuje w,
   na ili ispod p u drvetu*/
drvo *addtree( drvo *p, char *w )
{
   /* Promenljiva koja ce cuvati vrednost leksikografskog poredjenja reci */
   int comp;
   /* Ukoliko je drvo prazno (izlaz iz rekurzije) - doslo se do mesta
      gde treba smestiti novu rec*/
   if( p == NULL )
   {
      /* Alocira se prostor za novi cvor drveta uz pomoc talloc funkcije*/
      p = talloc();
      /*Dodeljuju se odgovarajuce vrednosti cvoru */
      p->rec = strdpl(w);
      p->broj = 1;
      p->levo = p->desno = NULL;
   }

   else if ((comp = strcmp(w,p->rec)) == 0 )
           /*Ukoliko je comp == 0 rec vec postoji u drvetu pa se broj pojavljivanja
             te reci uvecava za 1 */
           p->broj++;
        /* Inace ako je comp < 0 ide se u levu granu stabla */
        else if ( comp < 0 )
                p->levo = addtree(p->levo, w);
             /* U suprotnom sledi da je comp > 0 pa se rekurzivno nastavlja
                sa desnom granom stabla */
             else
                p->desno = addtree(p->desno, w);

   return p;
}

/* Funkcija treeprint  rekurzivno stampa drvo */
void treeprint(drvo  *p)
{
    if( p != NULL )
    {
       /* Ide se ulevo do NULL - a */
       treeprint( p->levo );
       /* Stampa se podatak */
       printf("%4d %s\n", p->broj, p->rec );
       /* Pa se obilaze desne grane obidjenih cvorova*/
       treeprint( p->desno );
    }
}
/* Funkcija koja uzima rec sa ulaza makslimalno lim duzine i vraca EOF
   ukoliko dodje do kraja ulaza */
int uzmi_rec(char s[], int lim)
{
   char c, i = 0;
   /* Preskace se sve do pojave slova ili cifre */
   while( !isalnum(c = s[0] = getchar()) && c!=EOF);
   /* Ukoliko je EOF uzrok izlaska iz petje - vraca se prazna rec */
   if( c==EOF )
   {
      s[0] = '\0';
      return EOF;
   }

   /* Ucitava se ostatak reci (u s[0] se vec nalazi prvo slovo) */
   while( (c = getchar()) != EOF && isalnum(c) && i < lim)
      s[++i] = c;
   /* Zavsava se niska  sa \0 */
   s[++i] =  '\0';

   /* Ukoliko je poslednji ucitani karakter EOF funkcija
      vraca EOF kao signal za kraj ulaza */
   if( c==EOF )
      return EOF;
   /* Inace funkcija vraca duzinu niske */
   return i;
}

/* Funkcija talloc oslobadja memorijski prostor za jedan cvor drveta */
drvo *talloc(void)
{
   return (drvo *) malloc(sizeof(drvo));
}

/* Funkcija koja pravi kopiju niske s ( <string.h> sadrzi standardnu
   funkciju strdup koja radi isti posao */
char *strdpl(char *s)
{
   char *p;
   /*Alocira se prostor za kopiju niske */
   p = (char *) malloc(strlen(s) + 1 );
   /* Vrsi se kopiranje niske */
   if( p != NULL )
      strcpy(p,s);
   /* Vraca se nova niska identicna originali samo na drugoj
      memoriskoj lokaciji */
   return p;
}