/*
 Implementación de un árbol binario
 Fraga 24/10/2017
*/
#include <stdio.h>
#include <stdlib.h>

struct nodo {
	char c;
	struct nodo *pizq, *pder;
};

typedef struct nodo NODO;

NODO * crea_nodo( char caracter )
{
	NODO *p;

	p = (NODO *)malloc( sizeof( NODO ) );

	if( p == NULL )
		return NULL;

	p->pizq = NULL;
	p->pder = NULL;
	p->c = caracter;
	return p;
}

void recorrer_en_orden( NODO *p )
{
	if ( p == NULL )
		return;

	if( p->pizq != NULL )
		recorrer_en_orden( p->pizq );

	// Procesamos la raiz
	printf("%c ", p->c );
	if( p->c == '*' )
		printf( "( " );

	if( p->pder != NULL )
		recorrer_en_orden( p->pder );

	if( p->c == '*' )
		printf( ") " );
}

void recorrer_post_orden( NODO *p )
{
	if ( p == NULL )
		return;

	if( p->pizq != NULL )
		recorrer_post_orden( p->pizq );

	if( p->pder != NULL )
		recorrer_post_orden( p->pder );

	// Procesamos la raiz
	printf("%c ", p->c );
}

void recorrer_pre_orden( NODO *p )
{
	if ( p == NULL )
		return;

	// Procesamos la raiz
	printf("%c ", p->c );

	if( p->pizq != NULL )
		recorrer_pre_orden( p->pizq );

	if( p->pder != NULL )
		recorrer_pre_orden( p->pder );
}

void borra_arbol( NODO *p )
{
	if ( p == NULL )
		return;

	if( p->pizq != NULL )
		borra_arbol( p->pizq );

	if( p->pder != NULL )
		borra_arbol( p->pder );

	// Proceso la raíz
	free( p );
}

void checar( NODO * arbol, NODO *p )
{
	if ( p == NULL ){
		fprintf( stderr, "No hay memoria\n" );
		borra_arbol( arbol );
		// Tendríamos que borrar el árbol ya creado
		exit(1);
	}
}


int main( )
{
	NODO *arbol1;
	NODO *paux;

	arbol1 = crea_nodo( '*' );
	checar( arbol1, arbol1 );

	paux = crea_nodo( 'c' );
	checar( arbol1, paux );
	arbol1->pizq = paux;

	paux = crea_nodo( '-' );
	checar( arbol1, paux );
	arbol1->pder = paux;

	paux = crea_nodo( 'a' );
	checar( arbol1, paux );
	arbol1->pder->pizq = paux;

	paux = crea_nodo( 'b' );
	checar( arbol1, paux );
	arbol1->pder->pder = paux;

	recorrer_en_orden( arbol1 );
	printf("\n");

	recorrer_post_orden( arbol1 );
	printf("\n");

	recorrer_pre_orden( arbol1 );
	printf("\n");

	// Borramos el árbol ya creado
	borra_arbol( arbol1 );
	return 0;
}