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

typedef struct c
{
    int k;
    char v[10];
	struct c* lijevi;
	struct c* desni;  	   
} Cvor;

Cvor* UmetniUStablo(Cvor* korjen, int k, char* v)
{
  	 if(korjen == NULL)
 	 {
	  	korjen = (Cvor*) malloc(sizeof(Cvor));		 
 	    korjen->k = k;
 	    strcpy(korjen->v, v);
        korjen->lijevi = NULL;
	    korjen->desni = NULL;   
     }
     else
     {
  	    Cvor* trenutni = korjen;
		Cvor* otac;  
	    while(trenutni != NULL)
	    {
		     if(trenutni->k == k)
	 			  return;
             
			 otac = trenutni;
   			 if(k < trenutni->k)
   			  	  trenutni = trenutni->lijevi;
			 else
			  	  trenutni = trenutni->desni;	 
		}
		
		trenutni = (Cvor*) malloc(sizeof(Cvor));		
	 	strcpy(trenutni->v, v);
	 	trenutni->k = k;
	 	
	 	if(otac->k > k)
	 	    otac->lijevi = trenutni;
        else
            otac->desni = trenutni;
		trenutni->lijevi = NULL;
		trenutni->desni = NULL;	 
     }
     return korjen;
}

Cvor* NadjiUStablu(Cvor* c, int k)
{
 	while(c->k != k && c != NULL)
    {
	     if(k < c->k)
	        c = c->lijevi;
      	 else
		    c = c->desni;	
    }
    if(c == NULL)
	{
	 	 printf("Ne postoji cvor sa zadatim kljucem!\n");
  	 	 return c;
    }  
    
    return c;
}

Cvor* ObrisiCvor(Cvor* korjen, int k)
{
 	 Cvor* c = korjen;
 	 Cvor* otac;
	 while(c != NULL)
	 {
	     if(c->k == k)
 			  break;
         
		 otac = c;
		 if(k < c->k)
		  	  c = c->lijevi;
		 else
		  	  c = c->desni;	 
     }
	 if(c == NULL)
	 {
	 	  printf("Ne postoji cvor sa zadatim kljucem!\n");
  	 	  return;
  	 }
  	 if(c == korjen)
  	 {
 	      printf("Zabranjeno je brisati korjen stabla\n");
  	  	  return;
     }
     if(c->lijevi == NULL)
      	 if(otac->k < k)
		     otac->lijevi = c->desni;
		 else 
		     otac->desni = c->desni;
	 else if(c->lijevi == NULL)
		 if(otac->k > k)
		     otac->lijevi = c->lijevi;
		 else 
		     otac->desni = c->lijevi; 
	 else
	 {
	  	 Cvor* c1 = c->lijevi;
		 Cvor* otac1 = c;
		 while(c1->desni != NULL)
		 {
		     otac1 = c1;
			 c1 = c1->desni;
			 c->k = c1->k;
			 strcmp(c1->v, c->v);
			 if(otac1 == c)
			 	otac1->lijevi = c1->lijevi;
			 else
			    otac1->desni = c1->lijevi;	 
		 }	 
     }  	 
     return korjen;
}

int main(int argc, char *argv[])
{
 	Cvor* korjen = NULL;
	korjen = UmetniUStablo(korjen, 7, "Darko");		
 	korjen = UmetniUStablo(korjen, 5, "Pero");
 	korjen = UmetniUStablo(korjen, 9, "Milan");
 	korjen = UmetniUStablo(korjen, 8, "Marko");
	
 	printf("%d, %s\n", korjen->k, korjen->v);
 	printf("%d, %s\n", korjen->lijevi->k, korjen->lijevi->v);
 	printf("%d, %s\n", korjen->desni->k, korjen->desni->v);
	printf("%d, %s\n", korjen->desni->lijevi->k, korjen->desni->lijevi->v);
 
 	korjen = ObrisiCvor(korjen, 9);
 	printf("-----------------------\n");
 	printf("%d, %s\n", korjen->k, korjen->v);
 	printf("%d, %s\n", korjen->lijevi->k, korjen->lijevi->v);
 	printf("%d, %s\n", korjen->desni->k, korjen->desni->v);
  
    printf("-----------------------\n");
 	printf("%d, %s\n", NadjiUStablu(korjen, 5)->k, NadjiUStablu(korjen, 5)->v); 
 	printf("-----------------------\n");
 	printf("%d, %s\n", NadjiUStablu(korjen, 9)->k, NadjiUStablu(korjen, 9)->v); 
 	
  	system("PAUSE");	
	return 0;
}