Projeto de Algoritmos | Índice Remissivo

Varredura e-r-d iterativa

[Enunciado]  Código iterativo da varredura esquerda-raiz-direita de uma árvore binária que manipula a pilha de nós diretamente (e não através das funções empilha e desempilha):

// Recebe a raiz r de uma árvore binária e
// imprime os conteúdos dos seus nós
// em ordem e-r-d.

void erd_i (arvore r) {
    noh *x, *pilha[101];
    int t = 0;
    pilha[t++] = r;
    while (1) {
       // pilha[0..t-1] é uma pilha de nós
       x = pilha[t-1];
       if (x != NULL) 
          pilha[t++] = x->esq;
       else {
          if (t == 0) break;
          x = pilha[--t];
          printf ("%d\n", x->conteudo);
          pilha[t++] = x->dir;
       }
    }
}

Esta versão supõe que a altura da árvore não passa de 100, mas é fácil remover esse restrição alocando uma pilha de tamanho apropriado.

Note a semelhança entre esse código e o código da função que enumera subsequências de 1..n em ordem lexicográfica.