Árvores

Árvores

Uma árvore binária é uma estrutura de dados formada por um conjunto finito de elementos ou nós. Uma árvore pode estar vazia ou pode ser formada por um nó chamado raiz e dois sub-conjuntos de elementos chamados sub-árvore esquerda e sub-árvore direita. As sub-árvores esquerda e direita são também árvores binárias e podem estar vazias .

A figura abaixo ilustra uma árvore binária :

Na figura:

• O nó raiz A tem duas sub-árvores B e C;
• O nó B tem duas sub-árvores D e E;
• O nó C tem apenas a sub-árvore da direita F;
• O nó E tem apenas a sub-árvore da esquerda G;
• O nó F tem duas sub-árvores H e I;
• Os nós D, G, H e I não tem sub-árvores, portanto, são chamados folhas.

Se A tem duas sub-árvores B e C, diz-se que:

• A é pai de B e C;
• B é filho esquerdo de A;
• C é filho direito de A.
• B é irmão de C.

Profundidade da árvore binária

Numa árvore binária, o nó raiz é considerado como profundidade 0 (zero). As sub-árvores do nó raiz profundidade 1, e assim sucessivamente. No exemplo da figura, a árvore binária tem profundidade 3.

Árvore estritamente binária

Uma árvore é estritamente binária se todo nó que não for folha tenha as sub-árvores direita e esquerda não vazias.

Árvore binária completa

Uma árvore é binária completa se for uma árvore estritamente binária e todas as folhas estiverem na mesma profundidade.

Aplicações das árvores binárias

As árvores binárias são uma estrutura de dados útil quando precisam ser tomadas decisões bi-direcionais em cada ponto do processo. Por exemplo, suponha que queiramos encontrar repetições em uma lista de números. Uma maneira de fazer isto é comparar cada número com todos os que o precedem. Entretanto, isto pode envolver muitas comparações. Outra maneira é utilizar uma árvore binária .

Exemplo

Suponha que temos a seguinte lista de números para verificar repetições:

14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

Neste caso, iniciamos a árvore com o primeiro número da lista como sendo o nó raiz. Na sequência, comparamos o próximo número com o número da raiz, se for igual é uma repetição. Se for menor, comparamos com a sub-árvore da esquerda. Se for maior, comparamos com a sub-árvore da direita. Se a sub-árvore estiver vazia, incluímos o número como filho desta sub-árvore, caso seja menor ou maior, da mesma forma que foi realizado no início.

Veja a árvore que seria construída neste exemplo:

Percorrendo uma árvore

Uma operação importante em uma árvore binária é percorrer todos os seus nós.

Diferentemente de uma lista, na qual os nós são percorridos de maneira linear, numa árvore, existem diferentes ordens para poder percorrê-la.

Todos os métodos para percorrer uma árvore são definidos recursivamente, de modo que percorrer uma árvore envolve visitar a raiz e depois a sub-árvore direita e a esquerda. O que difere cada método é a ordem em que estas operações são realizadas .

Percorrendo uma árvore pela ordem esquerda-raiz-direita

Um método bastante comum para percorrer uma árvore é a ordem chamada esquerda-raiz-direita .

Nesta ordem, percorre-se primeiro a sub-árvore esquerda, na ordem esquerda-raiz-direita. Depois a raiz. E depois a sub-árvore direita, também na ordem esquerda-raiz-direita.

Por exemplo, dada a árvore:

      A
     / \
    B   C
   /   / \
  D   E   F
 / \   \
G   H   I

a de ordem de varredura esquerda-raiz-direita é :

      5
     / \
    3   8
   /   / \
  1   6   9
 / \   \
0   2   7

Implementação de árvores em linguagem C

Cada nó de uma árvore pode ser implementado em linguagem C como uma estrutura com três campos: um campo conteúdo, para guardar a informação deste nó, e dois campos tipo ponteiro que apontam para as sub-árvores direita e esquerda.

Declaração de um nó de uma árvore

typedef struct arvore {
       int    conteudo;
       struct arvore *esq;
       struct arvore *dir;
} arvore;

Referência: .

Note que a declaração do nó da árvore é recursiva, onde os ponteiros *esq e *dir apontam para estruturas do mesmo tipo que está sendo declarada.

Endereço de uma árvore e definição recursiva

O endereço de uma árvore binária é o endereço de sua raiz .

main()
{
  arvore *r; //r é um ponteiro para uma árvore
  ...
}

Uma árvore binária pode ser definida de maneira recursiva, como segue:

Um objeto r é uma árvore binária se:

1. r é NUL ou
2. r->esq e r->dir são árvores binárias.

Percorrer árvore binária na ordem esquerda-raiz-direita

Função recursiva que faz a varredura e-r-d de uma árvore binária:

void erd(arvore *r) {
    if (r != NULL) {
       erd(r->esq);
       printf("%d\n", r->conteudo);
       erd(r->dir); 
    }
}

Inserção em árvores binárias

Vários algoritmos que trabalham com árvores trabalham em duas fases. Primeiro inserem elementos na árvore e depois percorrem a árvore.

Veja um exemplo de classificação de números em ordem crescente. A medida que os números forem sendo lidos, vão sendo inseridos na árvore. Entretanto, ao contrário do algoritmo usado para achar repetições, aqui os números repetidos também são inseridos na árvore. Quando um novo número é comparado com a raiz da árvore, a sub-árvore esquerda é utilizada se o número for menor que o conteúdo do nó e a sub-árvore direita é usada se o número for maior ou igual ao conteúdo do nó.

Função para inserção em árvore binária:

void inserir(arvore *r, int num){
     if(r == NULL){
        r = (arvore *) malloc(sizeof(arvore));
        r->esq = NULL;
        r->dir = NULL;
        r->conteudo = num;
     }else{
         if(num < r->conteudo)  
              inserir(r->esq, num));
         else  
              inserir(r->dir, num));
     }
 }

Referência:

Referências

---

--Evandro.cantu (discussão) 09h43min de 11 de novembro de 2014 (BRST)

---