/****************************************************************************
PROGRAMA:	Bisetree.c
AUTOR:		F‚lix Garc¡a
FECHA:		1993
FINALIDAD:	Busqueda, Inserci¢n y Borrado en  rboles binarios de busqueda
HISTORIA:	Adaptado y documentado. Kiko. 12.07.94
BIBLIOGRAFIA:
MODO DE UTILIZACION:	El programa es autoexplicativo.
****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define CR	'\n'

typedef struct nodo {
	char info;
	struct nodo *left;
	struct nodo *right;
} arbol;

arbol *root = NULL;
/*--------------------------------------------------------------------------*/
void insert(char c)
{
	arbol *p, *q;

	p = root;
	q = NULL;
	while (p != NULL) {
		q = p;
		if (p->info < c)
			p = p->right;
		else
			if (p->info > c)
				p = p->left;
			else
				return; /* Ya est  en el  rbol */
	} /* while ... */
	p = (arbol *)malloc(sizeof(arbol));
	p->info = c;
	p->left = p->right = NULL;
	if (q != NULL) { /* No era el primer nodo insertado */
		if (q->info < c)
			q->right = p;
		else
			q->left = p;
	} else
		root = p;
} /* insert */
/*--------------------------------------------------------------------------*/
void displayTree(arbol *r, int d)
{
	int i;

	if (r != NULL) {
		displayTree(r->right, d + 1);
		for (i = 0; i < d; i++)
			printf(" ");
		printf("%c\n", r->info);
		displayTree(r->left, d + 1);
	}
} /* displayTree */
/*--------------------------------------------------------------------------*/
arbol *buscar(char c)
{
	arbol *p;

	p = root;
	while (p != NULL) {
		if (p->info > c)
			p = p->left;
		else
			if (p->info < c)
				p = p->right;
			else
				return p;
	} /* while ... */
	return NULL;
} /* buscar */
/*--------------------------------------------------------------------------*/
int delete(char c, arbol *p)
{
	arbol *q, *pd, *d;

	q = NULL;
	while (p != NULL) {
		if (c < p->info) {
			q = p;
			p = p->left;
		} else {
			if (c > p->info) {
				q = p;
				p = p->right;
			}
			else {
				if (p->right == NULL) { /* no tiene hijo derecho */
					if (q != NULL) { /* No era la ra¡z */
						if (c < q->info)
							q->left = p->left;
						else
							q->right = p->left;
					} else	/* Era la ra¡z */
						root = root->left;
					free(p);
				} /* if ... */
				else
					if (p->left == NULL) { /* no tiene hijo izquierdo */
						if (q != NULL) {
							if (c < q->info)
								q->left = p->right;
							else
								q->right = p->right;
						} else /* Era la ra¡z */
							root = root->right;
						free(p);
					} /* else if ... */
					else { /* dos hijos, buscar el mayor del sub rbol izquierdo */
						/* se podr¡a utilizar el menor del sub rbol derecho */
						pd = p;
						d = p->left;
						while (d->right != NULL) {
							pd = d;
							d = d->right;
						} 
						p->info = d->info;
						if (pd == p)
							p->left = d->left;
						else
							pd->right = d->left;
						free(d);
					} /* else */
					return 1;
			} /* else */
		} /* del else del primer if */
	} /* primer while ... */
	printf("\nNo est  en el  rbol\n");
	return 0;
} /* delete */
/*--------------------------------------------------------------------------*/
void main()
{
	char c;
	arbol *p;
	int result;

	printf("\nIntroduzca caracteres y RETURN para acabar: ");
	do {
		c = (char)getchar();
		insert(c);
	} while (c != CR);
	printf("------------------------------\n");
	displayTree(root, 0);
	do {
		printf("buscar ");
		c = (char)getche();
		p = buscar(c);
		if (p != NULL)
			printf(" %c\n", p->info);
		else
			printf("Car cter no encontrado\n");
	} while (p != NULL);
	printf("------------------------------\n");
	do {
		displayTree(root, 0);
		printf("Introduzca caracter a borrar: ");
		c = (char)getche();
		result = delete(c, root);
		if (result != 0)
			printf(" %c\n", p->info);
		else
			printf("Car cter no encontrado\n");
	} while (result != 0);
exit(0);
} /* main */