arvores binarias

Árvores binárias

1

Árvores binárias
1. Árvores ordenadas
Conceitualmente, dividimos as árvores em ordenadas e não ordenadas. Nas árvores não ordenadas, os filhos de cada nó são equivalentes, isto é, sua ordem não importa. Nas árvores ordenadas, a ordem dos filhos, usualmente contada da esquerda para a direita, é importante. No diagrama a seguir, as duas árvores são iguais se forem consideradas como árvores não ordenadas e diferentes se forem consideradas como árvores ordenadas:

De fato, nestas duas árvores, os nós têm os mesmo filhos e portanto, vistas como árvores não ordenadas, ambas são a mesma árvore. No entanto, a posição dos filhos é diferente. Na primeira árvore, D é o primeiro filho de C, mas na segunda árvore D é o terceiro filho de C. Assim, vistas como árvores ordenadas, estas árvores são diferentes.

2. Árvores binárias
Árvores binárias são arvores ordenadas cujos nós têm no máximo dois filhos, ou seja, a ordem ou grau de uma árvore binária é 0, 1 ou 2. Em uma árvore binária, identificamos os filhos de uma árvore como “direito” e “esquerdo”.
Na figura ao lado, temos uma árvore binária.
Nesta árvore, o nó A tem o filho direito (B) e o filho esquerdo (C). O nó B tem apenas o filho esquerdo (D) e o nó C tem apenas o filho direito (E), e as linhas pontilhadas representam os filhos inexistentes. As nós D e E são terminais, portanto não tem nem o filho direito nem o filho esquerdo.
(Observação, em geral, não desenharemos mais linhas pontilhadas para representar filhos inexistentes.)
É comum definirmos alguns tipos especiais de árvores binárias:
1. Árvore estritamente binária é aquela cujos nós tem 0 ou 2 filhos. Ou seja, é uma árvore binária em que nenhum nó tem apenas 1 filho.
2. Árvore cheia é uma árvore estritamente binária (ver definição acima) em que todos os nós terminais estão no último nível.
3. Árvore completa é uma árvore estritamente binária em que todos os nós terminais estão no último ou no penúltimo nível.