Árvores binárias

Esta página é parcialmente baseada nas seções 13.1 e 13.2 do capítulo 13 (Trees) do livro de Eric Roberts.

O conceito

Eis uma definição recursiva do conceito: uma árvore binária sobre um conjunto de objetos é

1. vazia ou
2. um objeto juntamente com um par ordenado de árvores binárias.

No item 2 da definição, a primeira árvore binária do par é conhecida como subárvore esquerda e a segunda é conhecida como subárvore direita.

Implementação

Uma árvore binária (= binary tree) é uma estrutura de dados mais geral que uma lista encadeada. Cada uma de seus nós consiste em uma chave e dois ponteiros. Um dos ponteiros contém o endereço do "filho esquerdo" do nó, e o outro contém o endereço do "filho direito".  Uma folha de uma árvore é um nó sem filhos.

Nos nossos exemplos, as chaves serão do tipo string, mas em geral a chave de um nó pode ser qualquer coisa: um int, um float etc.  Nos exemplos que se seguem, cada nó da árvore binária será um objeto do tipo nodeT:

typedef struct nodeT { string key; struct nodeT *left; struct nodeT *right; } nodeT;

Uma árvore binária é, então, um objeto do tipo treeT:

typedef struct nodeT *treeT;

Varredura

Ao contrário de uma lista encadeada, uma árvore binária pode ser percorrida de muitas maneiras diferentes. Uma maneira particularmente importante é a ordem raiz-esquerda-direita (= preorder traversal) ou r-e-d.  Nessa maneira de percorrer a árvore, visitamos

• primeiro a raiz;
• depois a subárvore esquerda, em ordem r-e-d;
• e finalmente a subárvore direita, em ordem r-e-d.

Na figura abaixo, os nós estão numerados na ordem da varredura r-e-d.

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

Eis uma função (recursiva) que imprime as chaves da árvore em ordem r-e-d:

// Recebe uma árvore binária t. // Imprime as chaves dos nós em ordem r-e-d. ivoid PreorderPrint( treeT t) { if (t != NULL) { printf( "%d\n", t->key); PreorderPrint( t->left); PreorderPrint( t->right); } }

Eis uma função (recursiva) que procura encontrar um nó com uma dada chave. A função percorre a árvore em ordem r-e-d:

// Recebe uma árvore binária t e uma string k. // Devolve o endereço de um nó que contém a chave k. treeT FindNode( treeT t, string k) { treeT s; if (t == NULL || strcmp( k, t->key) == 0) return t; s = FindNode( t->left, k); if (s == NULL) s = FindNode( t->right, k) return s; }

Exercícios

1. Escreva uma função que calcule o número de nós de uma árvore binária.

2. Escreva uma função que imprima, em ordem r-e-d, as chaves das folhas de uma árvore binária.

3. Escreva uma versão iterativa da função PreorderPrint.

4. Escreva uma função que imprima os nós de uma árvore binária em ordem e-r-d (= inorder). Faça uma versão recursiva e uma iterativa.

5. Escreva uma função que imprima os nós de uma árvore binária em ordem e-d-r (= postorder). Faça uma versão recursiva e uma iterativa.

6. Escreva uma função que imprima as chaves de uma árvore binária com recuos de margem proporcionais ao nível do nó. Por exemplo, a árvore

   555 / \ 333 888 / \ \ 111 444 999

   
   deve se representada assim:

            555       
               333
                  111
                     -
                     -
                  444
                     -
                     -
               888
                  -
                  999
                     -
                     -
   

   onde os caracteres '-' representam NULL.

A altura de uma árvore

A altura de um nó x em uma árvore binária é a "distância" entre x e o seu descendente mais afastado. Por exemplo, a altura de uma folha é 0.

A altura de uma árvore é a altura da raiz da árvore.  Uma árvore com um único nó tem altura 0. Por convenção, a altura de uma árvore vazia é -1.  A árvore da figura tem altura 3.

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

Eis como a altura de uma árvore com raiz r pode ser calculada:

// Esta função devolve a altura da árvore // binária cuja raiz é r. int Height( treeT t) { if (t == NULL) return -1; else { int lH, rH; lH = Height( t->left); rH = Height( t->right); if (lH < rH) return rH + 1; else return lH + 1; } }

Qual a relação entre o número de nós, digamos n, de uma árvore binária e a altura, digamos h, da árvore? Resposta:

n-1  >  h  >  lg(n) .

Para ser mais exato, h > chão(lg(n)). É claro que lg é o logaritmo na base 2.

Que cara tem uma árvore binária com h = n-1? Uma tal árvore é um "tronco sem galhos": cada nó tem no máximo um filho. Agora considere o outro extremo: que cara tem uma árvore binária com h = chão(lg(n))?  Numa tal árvore a maioria dos nós que não são folhas têm ambos os filhos:

              H             
                            
          /       \          
                            
      D               K     
    /   \           /   \   
                            
  B       F       J       L 
 / \     / \     /          
A   C   E   G   I           

Árvores balanceadas

Uma árvore binária é balanceada (ou equilibrada) se, em cada um de seus nós, as subárvores esquerda e direita tiverem aproximadamente a mesma altura. Uma árvore binária balanceada com n nós tem altura próxima de lg(n). Convém trabalhar com árvores balanceadas sempre que possível. Mas isso não é fácil se a árvore aumenta e diminui ao longo da execução do seu programa.

Exercícios

7. Desenhe uma árvore binária que tenha chaves 1, . . . , 17 e a menor altura possível. Repita com a maior altura possível.

8. Escreva uma função iterativa que calcule a altura de uma árvore binária.

9. A profundidade (= depth) de um nó x em uma árvore binária com raiz t é a "distância" entre x e t. Mais precisamente, a profundidade de x é o comprimento do (único) caminho que vai de t até x. Por exemplo, a profundidade de t é 0 e a profundidade de t->left é 1.  Escreva uma função que determine a profundidade de um nó em relação à raiz da árvore.