Arvore

Algoritmos que usam árvores binárias procedem em duas fases. A primeira constrói uma árvore binária e a segunda percorre a árvore. Como exemplo podemos usar o método de classificação em que é dada uma lista de números num arquivo de entrada, e queremos imprimi-los em ordem ascendente. Esses números são inseridos na árvore binária, onde os valores repetidos também são colocados na árvore. Quando um número for menor que o conteúdo do nó, é usada uma ramificação esquerda, e uma ramificação direita de o número for maior ou igual ao conteúdo do nó. Dessa forma, se a lista de entrada for:
14 15 4 9 7 18 3 5 16 4 20 17 9 14 5
Será produzida a árvore binária da Figura 0.0.
Figura 0.0 Uma árvore binária construída para classificar. Uma árvore binária com essa propriedade é chamada árvore de busca binária. Se uma árvore de busca binária for percorrida em ordem simétrica e o conteúdo de cada nó for impresso à medida que o nó for visitado, os números serão impressos em ordem ascendente. Como outra aplicação das árvores binárias, examine o método de representar uma expressão contendo operandos e operadores binários por uma árvore estritamente binária. Figura 0.0. A raiz da árvore contem um operador que deve ser aplicado aos resultados das expressões representadas pelas subárvores esquerda e direita. Um nó representando um operador é um nó que não é folha, enquanto um nó representando um operando é uma folha.
Figura 0.0 Vejamos o que acontece quando essas árvores de expressões binárias são percorridas. Atravessar uma árvore desse tipo em ordem pré-ordem significa que o operador precede seus dois operandos. Resultando na forma prefixa da expressão: + A * B C De modo semelhante, o percurso em pós-ordem colocará um operador depois de seus dois operandos, de modo a produzir a forma posfixa da expressão: A B + C * O percurso em ordem, a raiz é visitada depois dos nós da subárvore esquerda e antes dos nós da subárvore direita.