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

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

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

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

struct node {
	struct no_arv elemento;
	struct node *next;
	};

typedef struct node *NODEPTR;

struct stack {
       NODEPTR top;
       };

struct no_arv currarea;
struct stack s;
int overflow, underflow;

FILE *pf;
int avail;

NODEPTR maketree(struct dataarea *, int *);
void setright(NODEPTR, struct dataarea *, int *);
void setleft(NODEPTR, struct dataarea *, int *);
NODEPTR getnode(void);
void freenode(NODEPTR);
void printtree(NODEPTR, int);
void pretrav2(NODEPTR);
void intrav2(NODEPTR);
void posttrav2(NODEPTR);
int empty(struct stack *);
void push(struct stack *, struct no_arv *, int *);
void pop(struct stack *, struct no_arv *, int *);

void main()
{
NODEPTR ptree, p, q;

overflow = FALSE;

pf=fopen("..\\DADOS\\arq9504.dat","r");
//pf = fopen("arq9504.dat","r");

//clrscr();
fscanf(pf,"%s\n",&(currarea.info.nome));
currarea.info.nome[10] = 0;
printf("\t\t\tRegistro lido: %s\n",currarea.info.nome);
ptree = maketree(&currarea.info,&overflow);
while (fscanf(pf,"%s\n",&(currarea.info.nome)) != EOF)  {
  currarea.info.nome[10] = 0;
  printf("\t\t\tRegistro lido: %s\n",currarea.info.nome);
  p = q = ptree;
  while (strcmp(currarea.info.nome,p->elemento.info.nome) != 0 && q != NULL) {
    p = q;
     if ( strcmp(currarea.info.nome,p->elemento.info.nome) < 0)
	 q = p->elemento.left;
       else
	 q = p->elemento.right;
     /* getch();*/
    }   /*  end while (strcmp....    */
  if  (strcmp(currarea.info.nome,p->elemento.info.nome) == 0)
       printf("Registro duplicado: %s\n", currarea.info.nome);
    else
       if  (strcmp(currarea.info.nome,p->elemento.info.nome) < 0)
	   setleft(p,&currarea.info,&overflow);
	 else
	   setright(p,&currarea.info,&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");

pretrav2(ptree);
getch();

printf("\n\n\t\t\tArvore obtida\n\n");
printtree(ptree,1);
printf("\n\n\t\t\tTravessia infixa\n\n");
intrav2(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");
posttrav2(ptree);

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

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

p = getnode();

if (p == NULL) {
   *poverflow = TRUE;
   return(p);
   }
  else {
p->elemento.info  = *pa;
p->elemento.left  = NULL;
p->elemento.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->elemento.left != NULL)
	printf("O n¢ j  tem filho mais novo\n");
      else {
	p->elemento.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->elemento.right != NULL)
	printf("O n¢ j  tem filho mais novo\n");
      else {
	p->elemento.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 node));
return(p);
}  /*  end getnode  */

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

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

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

void intrav2(NODEPTR ptree)
{
NODEPTR p;

s.top = NULL;
p = ptree;
// currarea.info = p->elemento.info;

do {  /* Avan‡ar para a esquerda tanto quanto poss¡vel, armazenando */
      /* ponteiros para os n¢s visitados   */
     while (p != NULL) {
       currarea = p->elemento;
       push(&s,&currarea,&overflow);
       if (overflow) {
	  }
       p = p->elemento.left;
       }  /* end while  */
    /*  verifica‡Æo de t‚rmino em folha   */
     if (!empty(&s)) {
       /* neste ponto a sub-arvore da esquerda est  vazia  */
	 pop(&s,&currarea,&underflow);
	 if (underflow)  {
	    }
	 printf("%s\n",currarea.info.nome);  /* visita … raiz  */
	 p =currarea.right;    /*  travessia da sub- rvore direita  */
	 }  /*  end if   */
   } while (!empty(&s) || p != NULL);
}  /*  end intrav2   */

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

void pretrav2(NODEPTR ptree)
{
NODEPTR p;

s.top = NULL;
p = ptree;

while (TRUE) {
     while (p != NULL) {
       currarea = p->elemento;
       printf("%s\n",p->elemento.info.nome);
       push(&s,&currarea,&overflow);
       if (overflow) {
	  }
       p =p->elemento.left;
       }  /* end while  */
    /*  verifica‡Æo de t‚rmino em folha   */
     if (empty(&s))
	 return;
     pop(&s,&currarea,&underflow);
     if (underflow)  {
	    }

     p =currarea.right;    /*  travessia da sub- rvore direita  */

   } /*  end while (TRUE);    */
}  /*  end pretrav2   */

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

void posttrav2(NODEPTR ptree)
{
NODEPTR p;
char *str1 = "          ";

s.top = NULL;
p = ptree;

strcpy(currarea.info.nome,str1);
currarea.visitado = FALSE;
currarea.left = NULL;
currarea.right = NULL;

push(&s,&currarea,&overflow);
  if (overflow) {
	  }

while (TRUE) {
     while (p != NULL) {
       currarea = p->elemento;
       currarea.visitado = FALSE;
	       /* sub- rvore ainda nÆo foi atravessada  */
       push(&s,&currarea,&overflow);
       if (overflow) {
	  }
       p =p->elemento.left;
       }  /* end while (p != NULL)  */
    /*  verifica‡Æo de t‚rmino em folha   */
     if (empty(&s))
	 return;
     do {
	 pop(&s,&currarea,&underflow);
	 if (underflow)  {
	     return;
	     }
	 p->elemento = currarea;
	 if (currarea.visitado)
	     printf("%s\n",currarea.info.nome);
	 }while (currarea.visitado);

     currarea.visitado = TRUE;

     push(&s,&currarea,&overflow);
     if (overflow) {
	  }

     p =currarea.right;

   } /*   while (TRUE);  */
}  /*  end posttrav2   */

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

int empty(struct stack *ps)
 {
 return((ps->top == NULL) ? TRUE : FALSE);
 }  /*  end empty  */

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

void push(struct stack *p, struct no_arv *px, int *poverflow)
{
NODEPTR q;

q = getnode();
if (p == NULL) {
    *poverflow = TRUE;
    return;
    }
*poverflow = FALSE;
q->elemento = *px;
q->next = p->top;
p->top = q;
return;
}  /*  end push   */

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

void pop(struct stack *p, struct no_arv *px, int *punderflow)
{
NODEPTR q;

if (empty(p)) {
    *punderflow = TRUE;
    return;
    }

*punderflow = FALSE;
*px = p->top->elemento;
q = p->top;
p->top = p->top->next;
freenode(q);
return;
}   /*  end pop  */

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

void freenode(NODEPTR p)
{
free(p);
}   /*  end freenode  */

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