/*
    xx__binarno_stablo.c
    -----
    Primjer implementacije binarnog stabla.
*/
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
 
struct cvor {
    char slovo;
    int count;          /* broj pojavljivanja */
    struct cvor *left;  /* left child */
    struct cvor *right; /* right child */
};
 
struct cvor *addToTree(struct cvor *, char);
void preorder(struct cvor *);
void postorder(struct cvor *);
void inorder(struct cvor *);
void izbrisistablo(struct cvor*);
void poNivoima(struct cvor*);
void nivo(struct cvor*, int, int);
int visina(struct cvor*);
 
int main() {
    struct cvor *root = NULL;
    char recenica[256];
    int i=0;
 
    printf("Unesite neku recenicu:\n");
    scanf("%[^\n]%*c", recenica);
 
    while (recenica[i]!='\0') {
        while (recenica[i]==' ' ||  recenica[i]=='\t' || recenica[i]==',' ||
               recenica[i]==':')
               i++;
        root = addToTree(root, tolower(recenica[i++]));
    }
 
    printf("Inorder:\n");
    inorder(root);
    scanf("%*c"); /* cekamo da se stisne enter */
    printf("Preorder:\n");
    preorder(root);
    scanf("%*c"); /* cekamo da se stisne enter */
    printf("Postorder:\n");
    postorder(root);
    scanf("%*c"); /* cekamo da se stisne enter */
    printf("Ispis po nivoima:\n");
    poNivoima(root);
 
    izbrisistablo(root);
 
    return 0;
}
 
/* Funkcija addTotree dodaje slovo c u stablo na ili ispod cvora p.
   Ukoliko vec postoji, povecava se broj pojavljivanja. */
struct cvor *addToTree(struct cvor *p, char c) {
    if (p == NULL) {
        p = (struct cvor*) malloc(sizeof(struct cvor));
        p->slovo = c;
        p->count = 1;
        p->left = p->right = NULL;
    }
    else if (c == p->slovo)
        p->count++;
    /* ako je slovo manje od onog u trenutnom cvoru stavi ga u
       lijevo podstablo */
    else if (c < p->slovo)
        p->left = addToTree(p->left, c);
    /* ako je slovo vece od onog u trenutnom cvoru stavi ga u
       desno podstablo */
    else
        p->right = addToTree(p->right, c);
 
    return p;
}
 
void inorder(struct cvor *p) {
    if (p != NULL) {
        inorder(p->left);
        printf("%c %4d\n", p->slovo, p->count);
        inorder(p->right);
    }
}
 
void postorder(struct cvor *p) {
    if (p != NULL) {
        postorder(p->left);
        postorder(p->right);
        printf("%c %4d\n", p->slovo, p->count);
    }
}
 
void preorder(struct cvor *p) {
    if (p != NULL) {
        printf("%c %4d\n", p->slovo, p->count);
        preorder(p->left);
        preorder(p->right);
    }
}
 
void izbrisistablo(struct cvor *p) {
    if (p != NULL) {
        izbrisistablo(p->left);
        izbrisistablo(p->right);
        free(p);
    }
}
 
int visina(struct cvor *p) {
    int l,d;
    if (p==NULL) return -1;
    else {
        l=visina(p->left);
        d=visina(p->right);
        return l>d ? l+1 : d+1;
    }
}
 
/* Funkcija nivo ispisuje oznake svih cvorova na i-tom nivou zadanog stabla) */
void nivo(struct cvor *p, int i, int j) {
    if (p!=NULL) {
        if (i==j) printf("%c ", p->slovo);
        else {
            nivo(p->left, i, j+1);
            nivo(p->right, i, j+1);
        }
    }
}
 
void poNivoima(struct cvor* p) {
    int i, v = visina(p);
    printf("Visina stabla -> %d\n", v);
    for (i=0; i<=v; i++) {
        printf("Nivo %d: ", i);
        nivo(p,i,0);
        printf("\n");
    }
}