/****************************************************************************
PROGRAMA:	Constree.c
AUTOR:		F‚lix
FECHA:		1993
FINALIDAD:	Construcci¢n de un Arbol binario PERFECTAMENTE EQUILIBRADO
				de N elementos
HISTORIA: Adaptado y documentado. Kiko: 12.07.94
BIBLIOGRAFIA:
MODO DE UTILIZACION:	Se necesita un fichero de texto en el que se almacene
			en primer lugar el n£mero de nodos del  rbol, y a
			continuaci¢n las claves (n£meros) correspondientes a
			cada nodo, poniendo una en cada l¡nea del fichero de
			texto.
			El fichero CONSTREE.TXT es adecuado para utilizarlo.
****************************************************************************/
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>

typedef struct nodo {
	int clave;  								/* Informaci¢n del Nodo */
	struct nodo *left, *right;	/* Punteros a Hijos Izquierdo y Derecho */
} arbol;
/************************ PROTOTIPOS DE FUNCIONES ***************************/
arbol *construir(int n);
void imprimir_arbol(arbol *p, int margen);


arbol *raiz = NULL; /* Raiz del Arbol */
FILE *fp;
/*--------------------------------------------------------------------------*/
void main() {
	char filename[13];
	int N;       /* N£mero de Nodos del  rbol */

	printf("\nIntroduzca Nombre de Fichero: ");
	scanf("%s", filename);
	if ((fp = fopen(filename, "r")) == NULL) {
		printf("\nERROR en la apertura del fichero %s", filename);
		exit(1);
	}
	fscanf(fp, "%d\n", &N);	/* Lectura del N£mero de Nodos */
	raiz = construir(N);
	fclose(fp); /* Cerrar Fichero */
	printf("\n");
	imprimir_arbol(raiz, 0);
} /* main */
/*--------------------------------------------------------------------------*/
arbol *construir(int n)
/* Construye un  rbol perfectamente equilibrado de n nodos */
{
	int ni, nd;
	int clave;
	arbol *nodo_nuevo;

	if (n == 0)
		return(NULL);
	else {	/* Calcular N£mero de Nodos de los hijos */
		ni = n / 2;
		nd = n - ni - 1;
		/* Leer Clave de este Nodo */
		fscanf(fp, "%d\n", &clave);
		if ((nodo_nuevo = (arbol *)malloc(sizeof(arbol))) == NULL) {
			printf("\nOUT OF MEMORY");
			exit(1);
		}
		nodo_nuevo->clave = clave;
		nodo_nuevo->left = construir(ni);
		nodo_nuevo->right = construir(nd);
		return(nodo_nuevo);
	}
}
/*--------------------------------------------------------------------------*/
void imprimir_arbol(arbol *p, int margen) {
/* Imprimir el  rbol "p" con un margen "margen" */

	int i;

	if (p != NULL) {
		imprimir_arbol(p->left, margen + 1);
		for (i = 0; i < margen; i++)
			printf("   ");
		printf("%d\n", p->clave);
		imprimir_arbol(p->right, margen + 1);
	}
}
/*--------------------------------------------------------------------------*/

/*
	CONSTREE.DAT                           SALIDA

			 8                                          4
			 1                                      3
			 2                                  2
			 3                                      5
			 4                              1
			 5                                      7
			 6                                  6
			 7                                      8
			 8

	 PREORDEN            INORDEN            POSTORDEN
			 1                  4                   4
			 2                  3                   3
			 3                  2                   5
			 4                  5                   2
			 5                  1                   7
			 6                  7                   8
			 7                  6                   6
			 8                  8                   1
*/