Arvores Binarias

ÁRVORE BINÁRIA Uma arvore binária é uma estrutura de dados que pode ser representada como uma hierarquia onde cada elemento é chamado de nó. O nó inicial ou o primeiro elemento é chamado de raiz. Em uma árvore binária um elemento pode ter um máximo de dois filhos no nível inferior denominados como sub-árvore esquerda e sub-árvore direita. Um nó sem filhos é chamado de folha. A profundidade de um nó é a distância deste nó até a raiz e a distancia entre a folha mais distante e a raiz é a altura da arvore. Um conjunto de nós com a mesma profundidade é denominado, nível da árvore.

PERCURSOS EM ARVORES BINARIAS Percorrer os nós de uma árvore binária é um ato frequente em algoritmos. Em muitos casos, a ordem em que os nós são percorridos é determinante para a correção de um algoritmo. Diferentemente de uma lista linear encadeada, cuja estrutura induz uma ordem natural de percurso, o fato de cada nó de uma árvore binária ser encadeado a dois outros nós deixa espaço para diferentes ordens de percurso.

Percurso em Ordem Como conseqüência da sua definição, as árvores binárias estão intimamente ligadas à noção de recursividade. Vejamos em ordem simétrica, a qual pode ser descrita recursivamente da seguinte forma: se r é a raiz de T, então percorre-se inicialmente, também em ordem simétrica, os nós da sub-árvore esquerda de r, em seguida percorre-se r e, finalmente, percorre-se, novamente em ordem simétrica, os nós da sub-árvore direita de r. Há uma tradução natural desse procedimento em forma de um algoritmo recursivo.
Algoritmo recursivo para percurso em ordem simétrica de uma árvore binária
Chamada simétricaRecursivo(r, visita)
Entrada identificação de NóÁrvoreBinária r, algoritmo visita usado para realizar a computação referente à visita de um nó se r≠λ então simétricaRecursivo(r→esq) visita(r) simétricaRecursivo(r→dir) Exemplo de execução (Ordem Simétrica) A execução para a árvore indicada na Figura (reproduzida abaixo) percorre inicialmente a