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

// tree-021.cpp
// cria‡Æo de  rvore bin ria de busca usando ponteiros da linguagem C
// travessia da  rvore por procedimentos recursivos

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

FILE *pf;
int avail, tamanho;

typedef struct nodetype *NODEPTR;
struct nodetype {
       struct dataarea info;
       NODEPTR left, right, father;
       };


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

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

//pf = fopen("arq9504.txt","r");
pf=fopen("..\\DADOS\\arq9504.dat","r");
// clrscr();
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,p->info.nome) != 0 && q != NULL) {
    p = q;
     if ( strcmp(currarea.nome,p->info.nome) < 0)
	 q = p->left;
       else
	 q = p->right;
     /* getch();*/
    }   /*  end while (strcmp....    */
  if  (strcmp(currarea.nome,p->info.nome) == 0)
       printf("Registro duplicado: %s\n", currarea.nome);
    else
       if  (strcmp(currarea.nome,p->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 folhas\n\n");
ztrav(ptree);

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

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

p = getnode();

if (p == NULL) {
   *poverflow = TRUE;
   return(p);
   }
  else {
p->info  = *pa;
p->left  = NULL;
p->right = NULL;
*poverflow = FALSE;
return(p);
   }
}  /*  end maketree   */

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

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

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

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

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


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

NODEPTR getnode(void)
{
NODEPTR p;
p = (NODEPTR)malloc(sizeof(struct nodetype));
return(p);
}  /*  end getnode  */

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

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

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


void pretrav(NODEPTR ptree)
{
if (ptree != NULL)  {
    printf("%s\n",ptree->info.nome);
    pretrav(ptree->left);
    pretrav(ptree->right);
    }   /*  end if   */
}   /*  end pretrav   */
/*****************************************************************/


void intrav(NODEPTR ptree)
{
if (ptree != NULL)  {
    intrav(ptree->left);
    printf("%s\n",ptree->info.nome);
    intrav(ptree->right);
    }   /*  end if   */
}   /*  end intrav   */

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

void posttrav(NODEPTR ptree)
{
if (ptree != NULL)  {
    posttrav(ptree->left);
    posttrav(ptree->right);
    printf("%s\n",ptree->info.nome);
    }   /*  end if   */
}   /*  end posttrav   */

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

void ztrav(NODEPTR ptree)
{
if (ptree != NULL)  {

	if ((ptree->left == NULL) && (ptree->right == NULL)) {
         printf("%s\n",ptree->info.nome);
	}
    ztrav(ptree->left);
    ztrav(ptree->right);
    
    }   /*  end if   */
}   /*  end zttrav   */