Uma árvore é um conjunto finito de nós interligados
hierarquicamente, tal que existe um nó denominado RAIZ, como na figura.
Nela existem "relações de parentesco" entre os nós. Por exemplo: A é PAI de
B e C, que são irmãos. O porquê dessa relação é obvio. Existem também os
nós denominados "nós-folha", que são aqueles que não têm filhos como, por
exemplo, C e D.
Teoricamente, uma árvore pode ser composta por nós de 3, 4 ou até
mais filhos, ou seja, árvores ternárias, quaternárias... Mas isso é inútil.
O que nos interessa são as árvores binárias.
Cada nó de uma árvore binária é composto por:
Estrutura Nó:
. Dado
. Link Esquerdo (ou Menor)
. Link Maior (ou Maior)
fim
onde "Dado" é a informação que queremos guardar na estrutura e "Link
Esquerdo" e "Link Direito" são apontadores para os filhos do nó. Esse lance
de "Maior" ou "Menor" tem a ver com o tipo de organização adotada para a
árvore. Geralmente, à esquerda de cada nó ficam todos os nós com informação
de valor menor que a sua, e à direita os de informação maior. Os de
informação igual, tanto faz, é uma questão de escolha na hora da
implementação. Essa comparação de informações (maior ou menor) depende do
tipo de dado que está sendo guardado. Por exemplo, se for um inteiro, ela
pode ser direta. Se não, é necessário criar uma chave a partir da informação
que está sendo manipulada e fazer essa comparação.
Vamos ver como ficaria uma árvore para guardar os seguintes valores
inteiros: 5, 8, 4, 1:
Percebe-se que a ordem com que se coloca os dados na árvore
influencia no seu aspecto final. Vejamos como acorre a manipulação dos dados
de uma árvore binária na segunda parte desse documento:
Para saber mais...
------> Árvores Binárias - parte #2
------> Pilhas
------> Recursividade
