O algorítmo era trabalho de aula, passei pelo menos duas tardes quebrando a cabeça pra tentar desvendar este mistério: como fazer uma árvore binária EDR (Esquerda-Direita-Raíz), ou seja, imprimir na tela os elementos da esquerda, depois os da direita, e então a raíz.
Uma forma "mágica" de fazer isso é modificando a estrutura da árvore, que ganha uma propriedade booleana "visitada", quando setada como false (padrão), significa que esse nodo ainda não foi visitado na busca, quando ela estiver setada como true, verdadeira, é porque já foi visitada, e por isso o iterador não necessita percorrer novamente esta ramo da árvore, isso evita redundância e loops infinitos, tornando o processo dinâmico.
Realmente recomendo você fazer o algorítmo, é um ótimo exercício pra desenvolver o raciocínio e testa suas habilidades, mas caso não consiga segue abaixo o código.
#include<stdio.h>
#include<stdlib.h>
struct arvore
{
int info;
arvore *dir;
arvore *esq;
bool visitado; // a magia do negócio, evita que um nodo seja lido redundantemente e entre em loop infinito
};
arvore *raiz = NULL;
struct pilha //estrutura da pilha
{
arvore *elto ; // ponteiro para elemento do tipo arvore
pilha *prox;
pilha *ant;
};
pilha *topo=NULL, *base=NULL;
arvore *aloca(int valor)
{
arvore *tmp;
tmp = (arvore *) malloc(sizeof(arvore));
tmp->info = valor;
tmp->esq = NULL;
tmp->dir = NULL;
tmp->visitado = false;
return tmp;
}
pilha *alocapilha(arvore *elto)
{
pilha *tmp;
tmp = (pilha *) malloc(sizeof(pilha));
tmp->elto = elto;
tmp->ant = NULL;
tmp->prox = NULL;
return tmp;
}
void insere(int valor)
{
arvore *atual = raiz, *folha = NULL;
if(raiz == NULL)
{
raiz = aloca(valor);
return;
}
/// inicio / inserir na folha
while(atual)
{
folha = atual; /// salva a raiz/nodo anterior
if(valor < atual->info)
{
atual = atual->esq;
}
else
{
atual = atual->dir;
}
}
if(valor < folha->info)
{
folha->esq = aloca(valor);
}
else
{
folha->dir = aloca(valor);
}
}
//retira o topo da pilha
void pop()
{
pilha *tmp;
tmp = topo;
if(topo->elto == raiz)
{
raiz = NULL;
}
else
{
topo = topo->ant;
topo->prox = NULL;
free(tmp);
}
}
void push(arvore *elto)
{
/// aloca na pilha um elemtno pilha q contem ponteiro do elemento da arvore
pilha *tmp = alocapilha(elto);
if (base == NULL)
{
base = topo = tmp;
}
else
{
tmp->ant = topo;
topo->prox = tmp;
topo = tmp;
}
}
void EDR()
{
printf("\nEntrou na funcao");
// r é a variável temporária, troca valores pra fazer as operações
arvore *r = raiz;
while(raiz)
{
/// empilha todos os elementos da esquerda de todas as folhas e raiz
while(r != NULL && r->visitado != true)
{
if(r != NULL)
{
push(r);
}
r = r->esq;
}
r = topo->elto;
while(r->dir == NULL)
{
printf("\n\t-[DESEMPILHOU] %d", topo->elto->info);
topo->elto->visitado = true;
pop();
r = topo->elto;
}
if(r->dir != NULL && r->dir->visitado == false)
{
topo->elto->visitado = true;
r = r->dir;
}
else
{
printf("\n\t-[DESEMPILHOU] %d", topo->elto->info);
pop();
r = topo->elto;
topo->elto->visitado = true;
}
}
}
/*############## RECURSIVA*/
void EDRr(arvore *atual)
{
if(atual != NULL)
{
EDRr(atual->esq);
EDRr(atual->dir);
printf("\n%d", atual->info);
}
}/**/
int main()
{
insere(50);
insere(2);
insere(1);
insere(23);
insere(21);
insere(54);
insere(12);
insere(53);
insere(55);
EDR();
//EDRr(raiz);
system("PAUSE");
}
