As árvores da computação têm a tendência de crescer para baixo:
a raiz fica no ar enquanto as folhas se enterram no chão.
— folclore

Árvores binárias

(Veja o verbete Binary tree na Wikipedia.)

Uma árvore binária é uma estrutura de dados mais geral que uma lista encadeada.  Este capítulo introduz as operações mais simples sobre árvores binárias. O capítulo seguinte trata de uma aplicação básica.

Nós e filhos

Uma árvore binária (= binary tree) é um conjunto de registros que satisfaz certas condições.  (As condições não serão dadas explicitamente, mas elas ficarão implicitamente claras no contexto.)  Os registros serão chamados nós (poderiam também ser chamados células).  Cada nó tem um endereço.  Suporemos por enquanto que cada nó tem três campos:  um número inteiro e dois ponteiros para nós.  Os nós podem, então, ser definidos assim:

struct cel { int conteudo; /* conteúdo */ struct cel *esq; struct cel *dir; }; typedef struct cel no; /* nó */

conteudo 999     esq dir

O campo conteudo é a "carga útil" do nó;  os outros dois campos servem apenas para dar estrutura à árvore.  O campo esq de todo nó contém o endereço de outro nó ou NULL.  A mesma hipótese vale para o campo dir.  Se o campo esq de um nó X é o endereço de um nó Y, diremos que Y é o filho esquerdo de X.  Analogamente, se X.dir é igual a &Y então Y é o filho direito de X.

Se um nó Y é filho (esquerdo ou direito) de X, diremos que X é o pai de Y.  Uma folha (= leaf) é um nó que não tem filho algum.

É muito conveniente confundir cada nó com seu endereço.  Assim, se x é um ponteiro para um nó (ou seja, se x é do tipo *no), dizemos simplesmente  "considere o nó x"  em lugar de  "considere o nó cujo endereço é x".

Árvores e subárvores

Suponha que x é (o endereço de) um nó.  Um descendente de x é qualquer nó que possa ser alcançada pela iteração dos comandos   x = x->esq  e  x = x->dir   em qualquer ordem.  (É claro que esses comandos só podem ser iterados enquanto x for diferente de NULL. Estamos supondo que NULL é de fato atingido mais cedo ou mais tarde.)

Um nó x juntamente com todos os seus descendentes é uma árvore binária.  Dizemos que x é a raiz (= root) da árvore.  Se x tiver um pai, essa árvore é uma subárvore de alguma árvore maior.  Se x é NULL, a árvore é vazia.

Para qualquer nó x,  x->esq   é a raiz da subárvore esquerda de  x  e  x->dir  é a raiz da subárvore direita de x.

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

O endereço de uma árvore binária é o endereço de sua raiz.  É conveninente confundir árvores com seus endereços:  dizemos  "considere a árvore r"  em lugar de  "considere a árvore cuja raiz tem endereço r". 

Essa convenção sugere a introdução do nome alternativo arvore para o tipo-de-dados ponteiro-para-nó:

typedef no *arvore; /* árvore */

A convenção permite formular a definição de árvore binária de maneira recursiva:  um objeto r é uma árvore binária se

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

Muitos algoritmos sobre árvores ficam mais simples quando escritos de forma recursiva.

Exercício

Varredura esquerda-raiz-direita

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

1. a subárvore esquerda da raiz, em ordem e-r-d;
2. depois a raiz;
3. depois a subárvore direita da raiz, em ordem e-r-d.

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

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

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

// Recebe a raiz r de uma árvore binária.
// Imprime os conteúdos dos nós em ordem e-r-d.

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

É um excelente exercício escrever uma versão iterativa desta função. Nossa versão usa uma pilha p[0..t-1] de endereços e mais um endereço x que é candidato a entrar na pilha; é como se a pilha fosse

p[0], p[1], . . . , p[t-1], x .

A sequência x, p[t-1], . . . ,  p[0] é uma espécie de "roteiro" daquilo que ainda precisa ser feito:  x representa a instrução "imprima a árvore x"  e  cada p[i] representa a instrução "imprima o nó p[i] e em seguida a árvore p[i]->dir".  Para dimensionar a pilha, suporemos que nossa árvore não tem mais que 100 nós. 

// Recebe a raiz r de uma árvore binária.
// Imprime os conteúdos dos nós em ordem e-r-d.
// Supõe que a árvore não tem mais que 100 nós.

void erd_i( arvore r) {
    no *x, *p[100];
    int t = 0;
    x = r;
    while (x != NULL || t > 0) {
       // a pilha é p[0..t-1]; o índice do topo é t-1
       if (x != NULL) {
          p[t++] = x;
          x = x->esq;
       }
       else {
          x = p[--t];
          printf( "%d\n", x->conteudo);
          x = x->dir;
       }
    }
}

[Note a semelhança entre esse cógido e o código da função que enumera subsequências de 1..n.]

Para a árvore sugerida na figura acima, a pilha p evolui como indicado na tabela abaixo. Cada linha da tabela resume o estado de coisas no início de uma iteração: à esquerda estão os nós que já foram impressos; à direita está a pilha  x, p[t-1], . . . ,  p[0].  O valor NULL está indicado por N.

                                 5
                               3 5
                             1 3 5
                           0 1 3 5
                         N 0 1 3 5
         0                 N 1 3 5
         0 1                 2 3 5
         0 1               N 2 3 5
         0 1 2               N 3 5
         0 1 2 3               4 5
         0 1 2 3             N 4 5
         0 1 2 3 4             N 5
         0 1 2 3 4 5             8
         0 1 2 3 4 5           6 8
         0 1 2 3 4 5         N 6 8
         0 1 2 3 4 5 6         7 8
         0 1 2 3 4 5 6       N 7 8
         0 1 2 3 4 5 6 7       N 8
         0 1 2 3 4 5 6 7 8       9
         0 1 2 3 4 5 6 7 8     N 9
         0 1 2 3 4 5 6 7 8 9     N

(Os exercícios abaixo discutem duas outras políticas de varredura de uma árvore binária:  a varredura r-e-d (= preorder traversal), que percorre a árvore em ordem raiz-esquerda-direita,  e a varredura e-d-r (= postorder traversal), que percorre a árvore em ordem esquerda-direita-raiz.)

Exercícios

Primeiro e último nós

Considere o seguinte problema: encontrar o endereço do primeiro nó na ordem e-r-d. É claro que o problema só faz sentido se a árvore não é vazia, ou seja, se r é diferente de NULL. Eis uma função que resolve o problema:

// Recebe uma árvore binária não vazia r.
// Devolve o primeiro nó da árvore na ordem e-r-d.

no *primeiro( arvore r) {  
    while (r->esq != NULL) 
       r = r->esq;
    return r;
}

Não é difícil fazer uma função análoga que encontre o último nó na ordem e-r-d.

Exercícios

Altura

A altura de um nó x em uma árvore binária é a distância entre x e o seu descendente mais afastado. Mas precisamente, a altura de x é o número de passos do mais longo caminho que leva de x até uma folha. Os caminhos a que essa definição se refere são os obtido pela iteração dos comandos x = x->esq e x = x->dir, em qualquer ordem.

A altura de uma árvore é a altura da raiz da árvore.  Uma árvore com um único nó tem altura 0. 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:

// Devolve a altura da árvore binária cuja raiz é r.

int altura( arvore r) {
   if (r == NULL) 
      return -1; // altura de árvore vazia é -1
   else {
      int he = altura( r->esq);
      int hd = altura( r->dir);
      if (he < hd) return hd + 1;
      else return he + 1;
   }
}

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

n-1   ≥   h   ≥   lg(n) ,

onde  lg(n)  denota  ⌊log₂ n⌋,  ou seja, piso de log₂ n .

n	lg(n)
4	2
5	2
6	2
10	3
64	6
100	6
128	7
1000	9
1024	10
1000000	19

Uma árvore binária com h = n-1 é um "tronco sem galhos": cada nó tem no máximo um filho.  No outro extremo, uma árvore com h = lg(n) é "quase completa": todos os "níveis" estão lotados exceto talvez o último.

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

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

Nós com campo pai

Em algumas aplicações (veja seção seguinte) é conveniente ter acesso imediato ao pai de qualquer nó. Para isso, é preciso acrescentar um campo pai a cada nó:

struct cel { int conteudo; struct cel *pai; struct cel *esq; struct cel *dir; }; typedef struct cel no;

esq pai esq       999     esq dir

É um bom exercício escrever uma função que preencha o campo pai de todos os nós de uma árvore binária.

Exercícios

Nó seguinte e anterior (sucessor e predecessor)

Digamos que x é o endereço de um certo nó de uma árvore binária. Nosso problema:  calcular o endereço do nó seguinte na ordem e-r-d.

Para resolver o problema, é necessário que os níos tenham um campo pai.  Eis uma função que resolve o problema. É claro que a função só deve ser chamada com x diferente de NULL. A função devolve o endereço do nó seguinte a x ou devolve NULL se x é o último nó. (Note que a função não precisa saber onde está a raiz da árvore.)

// Recebe o endereço de um nó x. Devolve o endereço 
// do nó seguinte na ordem e-r-d.
// A função supõe que x != NULL.

no *seguinte( no *x) {  
    if (x->dir != NULL) {
       no *y = x->dir; 
       while (y->esq != NULL) y = y->esq;
       return y;                                 // *
    }
    while (x->pai != NULL && x->pai->dir == x)   // ** 
       x = x->pai;                               // **
    return x->pai;
}

Comentários: Na linha *, y é o endereço do primeiro nó, na ordem e-r-d, da subárvore que tem raiz x->dir. As linhas ** fazem com que x suba na árvore enquanto for filho direito de alguém.

Exercícios