Jump to content
kripton2007

Dúvida Travessia de árvore binária

Recommended Posts

kripton2007

Boas,

Será que alguém me pode mostrar um algoritmo de travessia de uma árvore binária (iterativo)?

Tenho aqui uns exemplos, mas todos recorrem a funções auxiliares que não estão presentes.

Obrigado. :P

Share this post


Link to post
Share on other sites
Localhost

Podes fazer uma BFS para percorrer a árvore. Basicamente vais ter que ter uma queue (não sei se sabes o que é - google it) tens o seguinte algoritmo:

queue q // declaração de uma queue chamada q

q.push (root) // inseres na queue a root da árvore
enquanto q.empty () == false // enquanto a queue não estiver vazia
   j = q.front () // retira informações do nó actual
   q.pop () // elimina da queue o nó actual
   para cada nó i adjacente a j // adiciona à queue todos os vizinhos do nó actual
      q.push (i)

óbvio que substituías aquele ciclo por apenas duas inserções na queue (vizinho da direita e vizinho da esquerda, se existirem).


here since 2009

Share this post


Link to post
Share on other sites
KTachyon

Para uma árvore binária, a abordagem normal é utilizares uma stack (ou pilha, basicamente uma First-In Last-Out), se o que pretendes é percorrer a árvore de forma ordenada.

Basicamente, pegas num nó e vês se tem elementos à esquerda. Se tem, colocas o nó na stack e passas para o nó da esquerda. Quando não houverem nós à esquerda, fazes o que tens a fazer com o nó que tens e começas a verificar à esquerda desse nó.

Termina quando não houverem nós à esquerda do nó actual e a stack estiver vazia.

Sem descrever a implementação da stack, e, muito rapidamente, a implementação seria qualquer coisa deste género:

//stack *node_stack
node *current = root;
int stackSize = 0;

do {
    if (current->left != NULL) {
        stackSize = push(node_stack, current);
        current = current->left;
    }
    else {
        // faz o que precisas com o nó (current)
        if (current->right != NULL) {
            current = current->right;
        }
        else {
            stackSize = pop(node_stack, current);
        }
    }
} while (stackSize > 0 || current->right != NULL)


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.