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.