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

/*
PROGRAM: arbol_binario.cpp
DESCRIPCIÓN: Implementación de un árbol binario de busqueda
AUTOR: F.J.H.L.
Fecha Inicial: 11/Sept/2014
Fecha Actualización: 23/Sept/2014
*/

typedef struct _nodoArbol{
	int dato;
	struct _nodoArbol *izq;
	struct _nodoArbol *der;
}tipoNodoArbol;

void insertar(tipoNodoArbol **raiz,int x);
void preorden(tipoNodoArbol *raiz);
void inorden(tipoNodoArbol *raiz);
void postorden(tipoNodoArbol *raiz);

int main(void){
	tipoNodoArbol *raiz=NULL;//El árbol está vacío

	insertar(&raiz,50);
	insertar(&raiz,30);
	insertar(&raiz,60);
	insertar(&raiz,20);
	insertar(&raiz,100);
	insertar(&raiz,70);

	printf("\nPre-Orden: ");
	preorden(raiz);

	printf("\nIn-Orden: ");
	inorden(raiz);

	printf("\nPost-Orden: ");
	postorden(raiz);

	/*Como ejercicios (Siguiendo el archivo sesion6_ArbolesBinarios_Busqueda.pdf), 
	pueden implementar:
	1. Una función que inserte de forma recursiva un elemento en el ABB (ver slide 6)
	2. Una función que busque un elemento en el ABB (ver slide 9)
	3. Una función de busqueda de forma recursiva (ver slide 10)
	4. Una función para eliminar un elemento del ABB (ver slide 12)
	5. Una función que elimine de forma recursiva un elemento del ABB (ver slide 14)
	
	Nota: Darse cuenta de la diferencia entre los resultados de 4 y 5, al momento
	de desplegar todos los elementos del árbol...
	*/

	system("pause");
	return(0);
}

void insertar(tipoNodoArbol **raiz,int x){
	//Crear Memoria
	tipoNodoArbol *nodo_nuevo,*auxiliar;
	nodo_nuevo=(tipoNodoArbol *)malloc(sizeof(tipoNodoArbol));
	nodo_nuevo->dato=x;
	nodo_nuevo->der=NULL;
	nodo_nuevo->izq=NULL;

	if(*raiz==NULL){
		//printf("\nEl árbol está vacío...");
		*raiz=nodo_nuevo;
	}
	else{
		int ban_insertar=0;//1-->Si se insertó el dato
		auxiliar=*raiz;
		while(ban_insertar==0){
			if(x>auxiliar->dato){
				if(auxiliar->der!=NULL){
					auxiliar=auxiliar->der;
				}
				else{//insertamos el elemento nuevo
					auxiliar->der=nodo_nuevo;
					ban_insertar=1;
				}
			}
			else{
				if(auxiliar->izq!=NULL){
					auxiliar=auxiliar->izq;	
				}
				else{
					auxiliar->izq=nodo_nuevo;
					ban_insertar=1;
				}
			}
		}
	}
}

void preorden(tipoNodoArbol *raiz){
	if(raiz!=NULL){
		printf("%d, ",raiz->dato);
		preorden(raiz->izq);
		preorden(raiz->der);
	}
}
void inorden(tipoNodoArbol *raiz){
	if(raiz!=NULL){
		inorden(raiz->izq);
		printf("%d, ",raiz->dato);
		inorden(raiz->der);
	}
}
void postorden(tipoNodoArbol *raiz){
	if(raiz!=NULL){
		postorden(raiz->izq);
		postorden(raiz->der);
		printf("%d, ",raiz->dato);
	}
}