#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define NUMNODES               50
#define TRUE			1
#define FALSE			0


//              tree_031.cpp
// Cria‡Æo de uma  rvore bin ria de busca utilizando ponteiros inteiros
// travessia da  rvore por procedimentos recursivos
//

struct dataarea {
	char nome[10+1];
	} ;

struct no_arv {
	struct dataarea info;
	int left, right, father;
	};


struct nodetype {
	struct no_arv elemento;
	int next;
	};

FILE *pf;
int avail, tamanho;

struct nodetype node[NUMNODES];

int maketree(struct dataarea *, int *);
void setright(int, struct dataarea *, int *);
void setleft(int, struct dataarea *, int *);
void create_avail(void);
int getnode(void);
void freenode(int);
void printtree(int, int);
void pretrav(int);
void intrav(int);
void posttrav(int);
void ztrav(int);

void main()
{
int ptree, p, q;
struct dataarea currarea;
int overflow;
overflow = FALSE;

//pf = fopen("arq9504.dat","r");
pf=fopen("..\\DADOS\\arq9504.dat","r");
//clrscr();
create_avail();
fscanf(pf,"%s\n",&(currarea.nome));
currarea.nome[10] = 0;
printf("\t\t\tRegistro lido: %s\n",currarea.nome);
ptree = maketree(&currarea,&overflow);
while (fscanf(pf,"%s\n",&(currarea.nome)) != EOF)  {
  currarea.nome[10] = 0;
  printf("\t\t\tRegistro lido: %s\n",currarea.nome);
  p = q = ptree;
  while (strcmp(currarea.nome,node[p].elemento.info.nome) != 0 && q != -1) {
    p = q;
     if ( strcmp(currarea.nome,node[p].elemento.info.nome) < 0)
	 q = node[p].elemento.left;
       else
	 q = node[p].elemento.right;
     /* getch();*/
    }   /*  end while (strcmp....    */
  if  (strcmp(currarea.nome,node[p].elemento.info.nome) == 0)
       printf("Registro duplicado: %s\n", currarea.nome);
    else
       if  (strcmp(currarea.nome,node[p].elemento.info.nome) < 0)
	   setleft(p,&currarea,&overflow);
	 else
	   setright(p,&currarea,&overflow);
}   /*  end while (fscanf.....    */

getch();
printf("\n\n\t\t\tArvore obtida\n\n");
printtree(ptree,1);
getch();
printf("\n\n\t\t\tTravessia pr‚-fixa\n\n");
pretrav(ptree);
getch();
printf("\n\n\t\t\tArvore obtida\n\n");
printtree(ptree,1);
printf("\n\n\t\t\tTravessia infixa\n\n");
intrav(ptree);
getch();
printf("\n\n\t\t\tArvore obtida\n\n");
printtree(ptree,1);
printf("\n\n\t\t\tTravessia p¢s-fixa\n\n");
posttrav(ptree);
printf("\n\n\t\t\tTravessia soh de folhas\n\n");
ztrav(ptree);

getch();
}   /*  end main  */
/*****************************************************************/

int maketree(struct dataarea *pa, int *poverflow)
{
int p;

p = getnode();

if (p == -1) {
   *poverflow = TRUE;
   return(p);
   }
  else {
node[p].elemento.info  = *pa;
node[p].elemento.left  = -1;
node[p].elemento.right = -1;
*poverflow = FALSE;
return(p);
   }
}  /*  end maketree   */

/*****************************************************************/

void setleft(int p, struct dataarea *pa, int *overflow)
{

if (p == -1)
    printf("InclusÆo de n¢ sem valor\n");
  else
    if (node[p].elemento.left != -1)
	printf("O n¢ j  tem filho mais novo\n");
      else {
	node[p].elemento.left = maketree(pa,overflow);
	if (*overflow) {
	   printf("Sem espa‡o para grava‡Æo\n");
	   }
	   }
}  /*   end setleft     */

/*****************************************************************/

void setright(int p, struct dataarea *pa, int *overflow)
{
if (p == -1)
    printf("InclusÆo de n¢ sem valor\n");
  else
    if (node[p].elemento.right != -1)
	printf("O n¢ j  tem filho mais novo\n");
      else {
	node[p].elemento.right = maketree(pa,overflow);
	if (*overflow) {
	   printf("Sem espa‡o para grava‡Æo … direita\n");
	   }
	   }
}/*   end setright     */

/*****************************************************************/

void printtree(int p, int n)
{
int i;
if (p != -1)  {
    printtree(node[p].elemento.right,n+1);
    for (i = 1;i <= n;i++)
	 printf("%c",' ');
    printf("%s\n",node[p].elemento.info.nome);
    printtree(node[p].elemento.left,n+1);
    }  /* end if  */
}   /*  end printtree  */

/*****************************************************************/


void pretrav(int ptree)
{
if (ptree != -1)  {
    printf("%s\n",node[ptree].elemento.info.nome);
    pretrav(node[ptree].elemento.left);
    pretrav(node[ptree].elemento.right);
    }   /*  end if   */
}   /*  end pretrav   */
/*****************************************************************/


void intrav(int ptree)
{
if (ptree != -1)  {
    intrav(node[ptree].elemento.left);
    printf("%s\n",node[ptree].elemento.info.nome);
    intrav(node[ptree].elemento.right);
    }   /*  end if   */
}   /*  end intrav   */

/*****************************************************************/

void posttrav(int ptree)
{
if (ptree != -1)  {
    posttrav(node[ptree].elemento.left);
    posttrav(node[ptree].elemento.right);
    printf("%s\n",node[ptree].elemento.info.nome);
    }   /*  end if   */
}   /*  end posttrav   */

/*****************************************************************/

void create_avail(void)
{
int i;
avail = 0;
for (i = 0; i < NUMNODES-1; i++)
     node[i].next = i+1;

node[NUMNODES-1].next = -1;
return;
}   /*  end create_avail   */

/*****************************************************************/

int getnode(void)
{
int p;
if (avail == -1) {
   return(avail);
    }
p = avail;
avail = node[avail].next;
return(p);
}  /*  end getnode  */

/*****************************************************************/

void freenode(int p)
{
node[p].next = avail;
avail = p;
return;
} /*  end freenode  */

/*****************************************************************/

void ztrav(int ptree)
{
if (ptree != -1)  {
	    if ((node[ptree].elemento.left == -1) &&
	       (node[ptree].elemento.right == -1)) {
	             printf("%s\n",node[ptree].elemento.info.nome);
				}
    ztrav(node[ptree].elemento.left);
    ztrav(node[ptree].elemento.right);
    }   /*  end if   */
}   /*  z pretrav   */
/*****************************************************************/