Imprimir InOrder

[sinomen]

Uma nova dúvida para quem me conseguir ajudar.

Alguma dica para eu imprimir de uma arvore binaria ? A arvore está ordenada por "nome pessoa"

Imprimir de forma recursiva todo o conteúdo era facil bastava algo do genero:

void imprimirInOrder(Autor *aut,int n){
if(aut != NULL){
  imprimirInOrder(aut->esquerda,n);
  printf("%s\n");
  imprimirInOrder(aut->direita,n);
}
}

Como fazer a mesma coisa mas imprimir apenas os n primeiros nomes(neste caso n passado como parametro)

Por exemplo caso n=2 entao imprimir Amelia e Ana apenas.

[Flinger]

usa uma stack como estrutura auxiliar. Também creio ser a única forma de percorrer a àrvore de forma iterativa.

Uma forma é percorreres a lista toda pelo lado esquerdo, adicionando cada nó à stack. Quando chegares a uma folha voltas atrás (fazendo pop), e tratas o nó da direita como sendo uma nova àrvore (voltando a fazer push sempre pela esquerda).

Para adicionares um contador é fácil, é só contar os pop's.

Qualquer coisa como:

push Luis

push Ana

push Amélia;

pop Amélia;

pop Ana;

pop Luis;

push Pedro;

Pop Pedro;

[HappyHippyHippo]

no stack ... (não foi testado mas parece ok)

int imprimirInOrder(Autor *aut, int max, int printed){
 if(aut != NULL && printed < max) {
   // processar o ramo da esquerda
   printed += imprimirInOrder(aut->esquerda, max, printed);

   // processar este nó
   if (printed < max) {
     printf("%s\n");
     printed++;
   }

   // processar o ramo da direita
   if (printed < max) {
     printed += imprimirInOrder(aut->direita, max, printed);
 }

 return printed;
}

imprimirInOrder(aut, 3, 0);

no stack ... (não foi testado mas parece ok)

int imprimirInOrder(Autor *aut, int max, int printed){
 if(aut != NULL && printed < max) {
   // processar o ramo da esquerda
   printed += imprimirInOrder(aut->esquerda, max, printed);

   // processar este nó
   if (printed < max) {
     printf("%s\n");
     printed++;
   }

   // processar o ramo da direita
   if (printed < max) {
     printed += imprimirInOrder(aut->direita, max, printed);
 }

 return printed;
}

imprimirInOrder(aut, 3, 0);

[Flinger]

no stack ... (não foi testado mas parece ok)

int imprimirInOrder(Autor *aut, int max, int printed){
 if(aut != NULL && printed < max) {
// processar o ramo da esquerda
printed += imprimirInOrder(aut->esquerda, max, printed);

// processar este nó
if (printed < max) {
  printf("%s\n");
  printed++;
}

// processar o ramo da direita
if (printed < max) {
  printed += imprimirInOrder(aut->direita, max, printed);
 }

 return printed;
}

imprimirInOrder(aut, 3, 0);

No stack, but no iterative 😄

[HappyHippyHippo]

era para ser iterativo ? desculpa, não li no post inicial ...

[Flinger]

Quer dizer, o tópico original era, mas entretanto o OP reformulou a coisa. Na volta só queria iterativo por causa do contador. Se for esse o caso, então a tua resposta está perfeitamente correcta.

[sinomen]

nao tem de ser iterativo.

Assim, no primeiro teste o resultado nao me pareceu consistente.

Resolvido. Muito Obrigado aos dois.

Edited March 12, 2014 at 02:32 PM by sinomen