Algoritmos recursivos em árvores

Algoritmos recursivos em árvores 1
Algoritmos recursivos em árvores
1. Percurso
Um algoritmo de percurso em uma árvore é algum algoritmo que liste todos os elementos desta árvore, sem repetição. As idéias envolvidas neste tipo de algoritmo podem ser aplicadas a outros algoritmos capazes de responder muitas perguntas importantes, por exemplo:
1. Quantos nós a árvore possui?
2. Quantos nós com uma determinada propriedade a árvore possui? Por exemplo, quantos nós terminais (sem nenhum filho) a árvore possui?
3. Qual é o valor máximo de uma propriedade dos nós na árvore? Por exemplo, qual o número de nós do nó que tem mais nós (grau ou ordem da árvore)?
4. Qual a representação da árvore em alguma forma especial? Por exemplo, a representação
LISP.
Todos estes algoritmos serão definidos e implementados recursivamente de maneira bem mais simples do que iterativamente. Neste capítulo estudaremos as definições recursivas.
O percurso em pré-ordem ou pré-fixado é definido da seguinte maneira: primeiro a raiz é visitada; depois, cada uma de suas sub-árvores da raiz da esquerda para a direita é visitada em préordem.
Observamos que “visitar”, aqui, significa que o nó é impresso na tela ou usado para algum outro fim (por exemplo, calcular alguma coisa). Nesta seção, “visitar” significará imprimir.
Vamos ilustrar o percurso em pré-ordem com alguns exemplos ilustrados abaixo:
Na árvore (1), a definição é imediata: o percurso em pré-ordem é A B C.
Na árvore (2), o percurso em préordem deve ser efetuado da seguinte maneira: primeiro a raiz A; depois a sub-árbvore A1,, em pré-ordem; depois C. Mas a sub-árvore A1 em pré-ordem é B D E. Assim, o percurso em pré-ordem da árvore (2) é A B D E C.
Algoritmos recursivos em árvores 2
Na árvore (3), a determinação do percurso em pré-ordem foi esquematizada ao lado. É preciso decompor as sub-árvores A1, A2 e B2 em pré-ordem. O resultado final é A B D E F G H C
I.
Note que para obter a listagem de uma árvore em