Percurso em níveis
Neste tipo de percurso os nós são visitados de cima para baixo e da esquerda para a direita. Em relação ao exemplo, a ordem de visita dos nós seria:
A B C D E F G H I.
O algoritmo que será apresentado utiliza uma fila. A idéia é colocar a raiz da árvore binária na fila e, a partir daí, visitar o nó do início da fila, ao mesmo tempo em que se colocam seus filhos no final da mesma. O algoritmo é mostrado a seguir, onde a raiz da árvore é T e a fila usada é Fil.
Percurso_Nivel;
Início:
Esvazia Fil;
Enfila (T);
Enquanto (f <> 0), efetuar:
Desenfila (p);
Visita (p);
Enfila (p.le ); Enfila (p.ld );
Fe;
Fim;
Esse algoritmo tem, evidentemente, complexidade O(n). Neste e nos próximos algoritmos, fica subentido que o enfilamento ou empilhamento de um nó só é feito quando o nó não é nulo. Vejamos, para o exemplo anterior, a situação da fila Fil ao início do loop:
A visita em níveis fornece uma maneira fácil de se determinar distâncias de caminhos na árvore e por isso tem importância específica em muitos problemas. Para a determinação de distâncias, basta se colocar, também na fila, as distâncias, que são calculadas de maneira bem simples.
As próximas formas de percurso da árvore seguem o procedimento sistemático de visitar a raiz, a subárvore esquerda e a subárvore direita. A diferenciação estará na prioridade dada à visita da raiz em relação às subárvores. A subárvore esquerda é visitada sempre antes da direita.
Percurso em pré-ordem.
Neste tipo de percurso visita-se prioritariamente a raiz, em seguida a subárvore da esquerda e, depois, a subárvore da direita. Para o exemplo adotado, a ordem de visita seria:
A B D C E F G H I.
O algoritmo que será apresentado utiliza uma pilha. A idéia é colocar a raiz na pilha e, a partir daí, visitar o nó do topo da pilha, ao mesmo tempo em que se empilham a raiz da subárvore direita e da subárvore esquerda. O algoritmo é mostrado a seguir, onde a raiz da árvore é T e a pilha usada é Pil.
Percurso_Pre_Ordem; Início: Esvazia Pil; PUSH (T); Enquanto (topo 0), efetuar: POP (p); Visita (p); PUSH (p.ld); PUSH (p.le); Fe; Fim;
Esse algoritmo também tem complexidade O(n). Vejamos, para o exemplo anterior, a situação da pilha Pil ao início do loop:
Arquivo:BDA-PercursoPreOrdem.xls
Esta forma de visita tem muitas aplicações. Uma delas é que, se a árvore representa uma expressão aritmética, a visita em pré-ordem fornece a notação polonesa para a expressão. Para o exemplo de árvore binária do ítem a, teríamos:
+ A * B + - C D / E F