/*Program implementira funkcije za rad sa binarnim pretrazivackim stablom celih brojeva*/
	
#include <stdio.h>
#include <stdlib.h>

/* struktura kojom se predstavlja cvor drveta */
typedef struct dcvor{
	int broj;
	struct dcvor* levo, *desno;
} Cvor;

/* Funkcija alocira prostor za novi cvor drveta, inicijalizuje polja
  strukture. Vraca pokazivac na nov cvor ili NULL ako je doslo 
  do greske pri alokaciji. */
Cvor* napravi_cvor(int b )
{	Cvor* novi = (Cvor*) malloc(sizeof(Cvor));

	if( novi == NULL)
	  return NULL;	
	  
	novi->broj = b;
	novi->levo = NULL;
	novi->desno = NULL;
	
	return novi;
}

/* Oslobadjamo dinamicki alociran prostor za stablo */
Cvor* oslobodi_stablo(Cvor* koren)
{	/* rekurzivno oslobadjamo najpre levo, a onda i desno podstablo*/
	if( koren->levo ) oslobodi_stablo(koren->levo);
	if( koren->desno) oslobodi_stablo(koren->desno);
	free(koren);
	
	return NULL;
}

/* Funkcija dodaje nov cvor u stablo */
Cvor* dodaj_u_stablo(Cvor* koren, int broj)
{
	if( koren == NULL){
	  Cvor *novi =napravi_cvor(broj);
	  if(novi == NULL) {
	    fprintf(stderr, "GRESKA: malloc() u funkciji napravi_cvor()!\n");
	    koren = oslobodi_stablo(koren);
	    exit(EXIT_FAILURE);
	  }
	  
	  return novi;
	}
	
	/* Brojeve smestamo u uredjeno binarno stablo, pa 
	ako je broj koji ubacujemo manji od broja koji je u korenu  */
	if( broj < koren->broj)		/* dodajemo u levo podstablo */
		koren->levo = dodaj_u_stablo(koren->levo, broj);
	/* ako je broj manji ili jednak od broja koji je u korenu stabla, dodajemo nov cvor desno od korena */
	else 
		koren->desno = dodaj_u_stablo(koren->desno, broj);

	return koren;	
}

/* funkicija trazi ceo broj u stablu, ako ga nadje vraca pokazivac
	na cvor sa trazenim brojem. Ukoliko ne nadje vraca NULL pokazivac. */
Cvor* pretrazi_stablo(Cvor* koren, int n)
{	/* izlaz iz rekurzije*/
	if(koren == NULL)
		return NULL;

	if(koren->broj == n)
		return koren;
	
	if( koren->broj > n)
		return pretrazi_stablo(koren->levo, n);
	else 
		return pretrazi_stablo(koren->desno, n);
}
	
/* Funkcija nalazi najmanji element u binarnom stablu pretrage. 
   Vraca pokazivac na cvor sa najvecim brojem. 
   U slucaju neuspeha i praznog stabla vraca NULL. */
Cvor* pronadji_najmanji(Cvor* koren)
{
	if(koren == NULL)
		return NULL;
	if(koren->levo == NULL)
		return koren;
	return pronadji_najmanji(koren->levo);
}


/* funkcija nalazi najveci element u binarnom stablu pretrage. 
	Vraca pokazivac na cvor sa najvecim brojem. U slucaju neuspeha i praznog stabla vraca NULL. */
Cvor* pronadji_najveci(Cvor* koren)
{
	if(koren == NULL)
		return NULL;
	if(koren->desno == NULL)
		return koren;
	return pronadji_najveci(koren->desno);
}

/* Funkcija brise element iz stabla ciji je broj upravo jednak broju n. 
	Funkcija Vraca koren stabla koji moze biti promenjen u funkciji. */
Cvor* obrisi_element(Cvor* koren, int n)
{	Cvor *pomocni = NULL;

    /* Izlaz iz rekurzije: ako je stablo prazno, ono ostaje
       prazno i nakon brisanja */
    if (koren == NULL)
		return NULL;

    /* Ako je vrednost broja veca od vrednosti korena,
       tada se broj eventualno nalazi u desnom podstablu,
       pa treba rekurzivno primeniti postupak na desno 
       podstablo. Koren ovako modifikovanog stabla je
       nepromenjen, pa vracamo stari koren */
    if (koren->broj < n) 
	{	koren->desno = obrisi_element(koren->desno, n);
		return koren;
    }

    /* Ako je vrednost broja manja od vrednosti korena,
       tada se broj eventualno nalazi u levom podstablu,
       pa treba rekurzivno primeniti postupak na levo 
       podstablo. Koren ovako modifikovanog stabla je
       nepromenjen, pa vracamo stari koren */
    if (koren->broj > n) 
	{	koren->levo = obrisi_element(koren->levo, n);
		return koren;
    }

    /* Slede podslucajevi vezani su za slucaj kada je vrednost
       korena jednaka broju koji se brise (tj. slucaj kada 
       treba obrisati koren) */

    /* Stablo, prema definiciji funkcije dodaj_u_stablo(), moze sadrzati
      cvorove sa istom vrednoscu. Prema tome ako je vrednost u korenu bas
      ta koja se brise, moguce je da se ta ista vrednost pojavljuje i u
      desnom podstablu. Ako postoji desno podstablo, iz njega brisemo 
      elemente sa vrednoscu n. Tako smo obezbedili da se brisu sva ponavljanja.
      broja n u stablu, a ne samo jedan cvor. */
    
    if(koren->desni != NULL)
      koren->desni = obrisi_element(koren->desni, n);
  
    
    /* Ako koren nema sinova, tada se on prosto brise, i
       rezultat je prazno stablo (vracamo NULL) */
    if (koren->levo == NULL && koren->desno == NULL) 
	{	free(koren);
		return NULL;
    }

    /* Ako koren ima samo levog sina, tada se brisanje
       vrsi tako sto obrisemo koren, a novi koren postaje
       levi sin */
    if (koren->levo != NULL && koren->desno == NULL) 
	{	pomocni = koren->levo;
		free(koren);
		return pomocni;
    }

    /* Ako koren ima samo desnog sina, tada se brisanje 
       vrsi tako sto obrisemo koren, a novi koren postaje
       desni sin */
    if (koren->desno != NULL && koren->levo == NULL)
	{	pomocni = koren->desno;
		free(koren);
		return pomocni;
    }

    /* Slucaj kada koren ima oba sina. U tom slucaju se
       brisanje vrsi na sledeci nacin: najpre se potrazi
       sledbenik korena (u smislu poretka) u stablu. To
       je upravo po vrednosti najmanji cvor u desnom podstablu.
       On se moze pronaci npr. funkcijom pronadji_najmanji().
       Nakon toga se u koren smesti vrednost tog cvora, a u taj
       cvor se smesti vrednost korena (tj. broj koji se brise).
       Onda se prosto rekurzivno pozove funkcija za brisanje
       na desno podstablo. S obzirom da u njemu treba obrisati
       najmanji element, a on definitivno ima najvise jednog 
       potomka, jasno je da ce to brisanje biti obavljeno na 
       jedan od nacina koji je gore opisan. */
    pomocni = pronadji_najmanji(koren->desno);
    koren->broj = pomocni->broj;
    pomocni->broj = n;
    koren->desno = obrisi_element(koren->desno, n);
    return koren;

}

/* Funkcija ispisuje stablo u infiksnoj notaciji ( Levo - Koren - Desno )*/
void ispisi_stablo_infiksno(Cvor* koren)
{	if(koren != NULL)
	{	ispisi_stablo_infiksno(koren->levo);		/* Prvo ispisujemo sve cvorove levo od korena */
		printf("%d ", koren->broj);				/* ispisujemo broj u korenu */
		ispisi_stablo_infiksno(koren->desno);		/* Na kraju ispisujemo desno podstablo */
	}
}	

/* Funkcija ispisuje stablo prefiksno  ( Koren - Levo - Desno )*/
void ispisi_stablo_prefiksno(Cvor* koren)
{	if(koren != NULL)
	{	printf("%d ", koren->broj);			/* ispisujemo broj u korenu */
		ispisi_stablo_prefiksno(koren->levo);	/* Prvo ispisujemo sve cvorove levo od korena */
		ispisi_stablo_prefiksno(koren->desno);	/* Na kraju ispisujemo desno podstablo */
	}
}	

/* Funkcija ispisuje stablo postfiksno  ( Levo - Desno - Koren)*/
void ispisi_stablo_postfiksno(Cvor* koren)
{	if(koren != NULL)
	{	ispisi_stablo_postfiksno(koren->levo);	/* Prvo ispisujemo sve cvorove levo od korena */
		ispisi_stablo_postfiksno(koren->desno);	/* Na kraju ispisujemo desno podstablo */
		printf("%d ", koren->broj);			/* ispisujemo broj u korenu */
	}
}	

int main()
{
	Cvor* koren = NULL; /* Napomena: Prazno stablo! */
	int n;
	Cvor* trazeni;
	
	printf("Unosite cele brojeve! --- CTRL+D za prekid unosenja!\n");
	while( scanf("%d",&n) != EOF)
	{	koren=dodaj_u_stablo(koren,n);
		printf("    Stablo ( L-K-D) : ");
		ispisi_stablo_infiksno(koren);
		putchar('\n');
	}	
	
	printf("\nUneto drvo u infiksnom obilasku (L-K-D): ");
	ispisi_stablo_infiksno(koren);
	putchar('\n');

	printf("Uneto drvo u prefiksnom obilasku (K-L-D): ");
	ispisi_stablo_prefiksno(koren);
	putchar('\n');
	
	printf("Uneto drvo u postfiksnom obilasku (L-D-K): ");
	ispisi_stablo_postfiksno(koren);
	putchar('\n');
	
	printf("\nKoji se to broj trazi u stablu? \t");
	scanf("%d",&n);
	
	trazeni = pretrazi_stablo(koren,n);
	if(trazeni == NULL)
		printf("Element %d nije u stablu!\n",n);
	else printf("Element %d se nalazi u stablu!!!\n", trazeni->broj);
	
	
	printf("\nNajveci element u stablu je %d, a najmanji je %d.\n", pronadji_najveci(koren)->broj , pronadji_najmanji(koren)->broj);
	
	printf("\nKoji se to broj brise iz stabla? \t");
	scanf("%d",&n);
	
	koren = obrisi_element(koren,n);
	ispisi_stablo_infiksno(koren);
	putchar('\n');
	koren = oslobodi_stablo(koren);
	return 0;
}