#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <graphics.h>
#include <ctype.h>
#include <dos.h>

#define raza 15

typedef struct nod
 {
	 int cheie;
	 struct nod *st,*dr;
 }Tnod;
typedef Tnod *ref;

ref radacina,q;
int N,x;
char op;
int timp=1000;

void Tip(ref anod, int nivel, int x1, int x2, int c1,int c2,char *s)
	{
		setcolor(WHITE);
		settextstyle(SMALL_FONT, HORIZ_DIR,0.5);
		line((x1+x2)/2,40*nivel+raza,c1,c2);
		pieslice((x1+x2)/2,40*nivel+raza,0,360,raza);
		setcolor(BLACK);
		sprintf(s,"%d",anod->cheie);
		outtextxy((x1+x2)/2,40*nivel+raza,s);
		delay(timp);
	}/*Tip*/
void Inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
	{
		static char s[10];
		if(rad!=NULL)
			{
			 Inordine(rad->st,nivel+1,x1,(x1+x2)/2,(x1+x2)/2,nivel*40+raza);
			 Tip(rad,nivel,x1,x2,c1,c2,s);
			 Inordine(rad->dr,nivel+1,(x1+x2)/2,x2,(x1+x2)/2,nivel*40+raza);
			}
	}/*Inordine*/
void Preordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
	{
		static char s[10];
		if (rad!=NULL)
			{
			 Tip(rad,nivel,x1,x2,c1,c2,s);
			 Preordine(rad->st,nivel+1,x1,(x1+x2)/2,(x1+x2)/2,nivel*40+raza);
			 Preordine(rad->dr,nivel+1,(x1+x2)/2,x2,(x1+x2)/2,nivel*40+raza);
			}
	}/*Preordine*/
void Postordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
	{
		static char s[10];
		if (rad!=NULL)
			{
			 Postordine(rad->st,nivel+1,x1,(x1+x2)/2,(x1+x2)/2,nivel*40+raza);
			 Postordine(rad->dr,nivel+1,(x1+x2)/2,x2,(x1+x2)/2,nivel*40+raza);
			 Tip(rad,nivel,x1,x2,c1,c2,s);
			}
	}/*Postordine*/
void Initializare(void)
	{
		int graphdriver=DETECT,grafmode,errorcode;
		initgraph(&graphdriver, &grafmode, "C:\\BorlandC\\BGI");
		errorcode = graphresult();
		if (errorcode != grOk)
			{
			 printf("Eroare la initializarea modului grafic:%s\n", grapherrormsg(errorcode));
			 getch();
			 exit(1);
			}
	}/*Initializare*/
void InArbore(int x, ref *t)
	{
		if(*t==NULL)
		 {
			*t=(ref)malloc(sizeof(Tnod));
			(*t)->cheie=x;
			(*t)->st=NULL;
			(*t)->dr=NULL;
		 }
		 else
			 if(x<(*t)->cheie)
				 InArbore(x,&((*t)->st));
				 else InArbore(x,&((*t)->dr));
	}  /*InArbore*/
void Creare(void)
	{
		char c;
		radacina=NULL;
		printf("Doriti sa introduceti un nou nod? (d/n):");
		fflush(stdin); scanf("%c",&c); c=toupper(c);
		while (c=='D')
		 {
			printf("Introduceti informatia: "); scanf("%d",&x);
			InArbore(x,&radacina);
			printf("Mai introduceti noduri? (d/n): ");
			fflush(stdin); scanf("%c",&c); c=toupper(c);
		 }
	}  /*Creare*/
void Suprimafd(ref *r)
	{
	 if((*r)->dr!=NULL)
		 Suprimafd(&((*r)->dr));
		 else
			 {
				q->cheie=(*r)->cheie;
				q=*r;
				*r=q->st;
			 }
	}
void Suprimare(int x,ref *p)
	{
	 if((*p)==NULL)
		 printf("Nodul nu se afla in arbore!\n");
		 else
			 if(x<(*p)->cheie)
				 Suprimare(x,&((*p)->st));
				 else
					 if(x>(*p)->cheie)
						 Suprimare(x,&((*p)->dr));
						 else
							 {
								q=*p;
								if(q->dr==NULL)
									(*p)=q->st;
									else
										if(q->st==NULL)
											(*p)=q->dr;
											else Suprimafd(&((*p)->st));
								free(q);
							 }
	}
void main(void)
	{
	 char c;
	 clrscr();
	 radacina=NULL;
	 do{
			clrscr();
			printf("\nCrearea si vizualizarea naturala a unui arbore binar si ordonat:");
			printf("\nC - Creare");
			printf("\nP - Preordine ");
			printf("\nI - Inordine ");
			printf("\nS - Postordine");
			printf("\nD - Suprimare nod");
			printf("\nE - Iesire");
			printf("\nIntrodu optiunea: ");
			fflush(stdin); scanf("%c",&op); op=toupper(op);
			switch (op)
				{
				 case 'C':if(radacina==NULL)
										Creare();
										else
											{
											 printf("Arborele exista! Doriti sa creati un alt arbore? (d/n)");
											 fflush(stdin); scanf("%c",&c);c=toupper(c);
											 if(c=='D')
												 {
													radacina=NULL;
													Creare();
												 }
											}
									break;
				 case 'P':if(radacina==NULL)
										printf("Arborele este vid!\n");
										else
											{
											 printf("Arborele perfect echilibrat in Inordine simetrica: \n");
											 Initializare();
											 delay(timp);
											 Preordine(radacina,0,0,getmaxx(),getmaxx()/2,raza);
											 getch();
											 closegraph();
											}
									break;
				 case 'I':if(radacina==NULL)
										printf("Arborele este vid!\n");
										else
											{
											 printf("Arborele perfect echilibrat in Inordine simetrica: \n");
											 Initializare();
											 delay(timp);
											 Inordine(radacina,0,0,getmaxx(),getmaxx()/2,raza);
											 getch();
											 closegraph();
											}
									break;
				 case 'D':if(radacina==NULL)
										printf("Arborele este vid!\n");
										else
											{
											 printf("Dati cheia:");scanf("%d",&x);
											 Suprimare(x,&radacina);
											}
									break;
				 case 'S':if(radacina==NULL)
										printf("Arborele este vid!\n");
										else
											{
											 printf("Arborele perfect echilibrat in Inordine simetrica: \n");
											 Initializare();
											 delay(timp);
											 Postordine(radacina,0,0,getmaxx(),getmaxx()/2,raza);
											 getch();
											 closegraph();
											}
									break;
				 case 'E':break;
				} /*switch*/
		 }while(op!='E');
	}/*main*/