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
Percurso em ordem simétrica.
Neste tipo de percurso visita-se prioritariamente a subárvore da esquerda, em seguida a raiz e, finalmente, a subárvore da direita. No exemplo, teríamos:
B D A E C H I G F.
O algoritmo que será apresentado também utiliza uma pilha. A idéia é colocar, sucessivamente, a raiz da subárvore esquerda na pilha até se chegar a um link nulo, quando então se visita o topo da pilha, repetindo-se o processo para a subárvore da direita. O algoritmo é mostrado a seguir, onde a raiz da árvore é T e a pilha usada é Pil.
Percurso_Ordem_Simétrica; Início:
Esvazia Pil; p <- T; Enquanto ( p Nil ) Ou ( topo 0 ), efetuar: Enquanto ( p Nil ), efetuar:
PUSH (p); p <- p.le;
Fe; POP (p); Visita ( p );
p <- p.ld; Fe; Fim;
Esse algoritmo também tem complexidade O(n). Vejamos, para o exemplo anterior, a situação da pilha Pil no início do segundo loop:
Arquivo:BDA-PercursoOrdemSimetrica.xls
Esta forma de visita tem muitas aplicações. Uma delas será vista no próximo capítulo que trata das árvores de busca.
Percurso em pós-ordem.
Neste tipo de percurso visita-se prioritariamente a subárvore da esquerda, em seguida a subárvore da direita e, por fim, a raiz. Para o exemplo adotado, a ordem de visita seria:
D B E I H G F C A.
O algoritmo que será apresentado utiliza uma pilha e é um algoritmo de difícil entendimento, devendo ser verificado cuidadosamente. Cada nó é colocado na pilha duas vezes. A primeira quando se está empilhando ramos à esquerda da árvore; a segunda quando o empilhamento é pela direita. Um nó só é visitado quando ele é o topo da pilha e foi a segunda vez que entrou na mesma. O algoritmo é mostrado a seguir, onde a raiz da árvore é T e a pilha usada é Pil.
Percurso_Pos_Ordem; Início:
Esvazia Pil; p <- T; Enquanto ( p Nil ) Ou ( topo 0 ), efetuar: Enquanto ( p Nil ), efetuar:
PUSH (p, 1); p <- p.le;
Fe; Enquanto ( p = Nil ) e ( topo 0 ), efetuar: POP (p, vez); Se (vez = 1) e (p.ld Nil) Então PUSH ( p, 2 ); p <- p.ld;
Senão Visita ( p ); p <- Nil;
Fe;
Fe; Fim;
Esse algoritmo também tem complexidade O(n). Vejamos, para o exemplo anterior, a situação da pilha Pil a cada mudança, indicando, também, o valor da vez:
Arquivo:BDA-PercursoPosOrdem.xls
Esta forma de visita também tem aplicações. Uma delas é que, se a árvore representa uma expressão aritmética, a visita em pós-ordem fornece a notação polonesa reversa para a expressão. Para o exemplo de árvore binária do ítem a, teríamos:
A B C D - E F / + * +
- Exemplos de código: