(Parte 1 de 3)

Estruturas de Dados – PUC-Rio12-1

13. Árvores W. Celes e J. L. Rangel

Nos capítulos anteriores examinamos as estruturas de dados que podem ser chamadas de unidimensionais ou lineares, como vetores e listas. A importância dessas estruturas é inegável, mas elas não são adequadas para representarmos dados que devem ser dispostos de maneira hierárquica. Por exemplo, os arquivos (documentos) que criamos num computador são armazenados dentro de uma estrutura hierárquica de diretórios (pastas). Existe um diretório base dentro do qual podemos armazenar diversos subdiretórios e arquivos. Por sua vez, dentro dos sub-diretórios, podemos armazenar outros sub-diretórios e arquivos, e assim por diante, recursivamente. A Figura 13.1 mostra uma imagem de uma árvore de diretório no Windows 2000.

Figura 13.1: Um exemplo de árvore de diretório.

Neste capítulo, vamos introduzir árvores, que são estruturas de dados adequadas para a representação de hierarquias. A forma mais natural para definirmos uma estrutura de árvore é usando recursividade. Uma árvore é composta por um conjunto de nós. Existe um nó r, denominado raiz, que contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente a r. Esses nós raízes das sub-árvores são ditos filhos do nó pai, r.

Nós com filhos são comumente chamados de nós internos e nós que não têm filhos são chamados de folhas, ou nós externos. É tradicional desenhar as árvores com a raiz para cima e folhas para baixo, ao contrário do que seria de se esperar. A Figura 13.2 exemplifica a estrutura de uma árvore.

Figura 13.2: Estrutura de árvore.

Observamos que, por adotarmos essa forma de representação gráfica, não representamos explicitamente a direção dos ponteiros, subentendendo que eles apontam sempre do pai para os filhos.

nó raiz sub-árvores nó raiz

Estruturas de Dados – PUC-Rio12-2

O número de filhos permitido por nó e as informações armazenadas em cada nó diferenciam os diversos tipos de árvores existentes. Neste capítulo, estudaremos dois tipos de árvores. Primeiro, examinaremos as árvores binárias, onde cada nó tem, no máximo, dois filhos. Depois examinaremos as chamadas árvores genéricas, onde o número de filhos é indefinido. Estruturas recursivas serão usadas como base para o estudo e a implementação das operações com árvores.

Um exemplo de utilização de árvores binárias está na avaliação de expressões. Como trabalhamos com operadores que esperam um ou dois operandos, os nós da árvore para representar uma expressão têm no máximo dois filhos. Nessa árvore, os nós folhas representam operandos e os nós internos operadores. Uma árvore que representa, por exemplo a expressão (3+6)*(4-1)+5 é ilustrada na Figura 13.3.

Figura 13.3: Árvore da expressão: (3+6) * (4-1) + 5.

Numa árvore binária, cada nó tem zero, um ou dois filhos. De maneira recursiva, podemos definir uma árvore binária como sendo: • uma árvore vazia; ou

• um nó raiz tendo duas sub-árvores, identificadas como a sub-árvore da direita (sad) e a sub-árvore da esquerda (sae).

A Figura 13.4 ilustra a definição de árvore binária. Essa definição recursiva será usada na construção de algoritmos, e na verificação (informal) da correção e do desempenho dos mesmos.

Estruturas de Dados – PUC-Rio12-3

Figura 13.4: Representação esquemática da definição da estrutura de árvore binária.

A Figura 13.5 a seguir ilustra uma estrutura de árvore binária. Os nós a, b, c, d, e, f formam uma árvore binária da seguinte maneira: a árvore é composta do nó a, da subárvore à esquerda formada por b e d, e da sub-árvore à direita formada por c, e e f. O nó a representa a raiz da árvore e os nós b e c as raízes das sub-árvores. Finalmente, os nós d, e e f são folhas da árvore.

Figura 13.5: Exemplo de árvore binária

Para descrever árvores binárias, podemos usar a seguinte notação textual: a árvore vazia é representada por <>, e árvores não vazias por <raiz sae sad>. Com essa notação, a árvore da Figura 13.5 é representada por: <a<b<><d<><>>><c<e<><>><f<><>>>>.

Pela definição, uma sub-árvore de uma árvore binária é sempre especificada como sendo a sae ou a sad de uma árvore maior, e qualquer das duas sub-árvores pode ser vazia. Assim, as duas árvores da Figura 13.6 são distintas.

Figura 13.6: Duas árvores binárias distintas.

Isto também pode ser visto pelas representações textuais das duas árvores, que são, respectivamente: <a <b<><>> <> > e <a <> <b<><>> >.

a b c fed ab a b raiz sadsae vazia

Estruturas de Dados – PUC-Rio12-4

Uma propriedade fundamental de todas as árvores é que só existe um caminho da raiz para qualquer nó. Com isto, podemos definir a altura de uma árvore como sendo o comprimento do caminho mais longo da raiz até uma das folhas. Por exemplo, a altura da árvore da Figura 13.5 é 2, e a altura das árvores da Figura 13.6 é 1. Assim, a altura de uma árvore com um único nó raiz é zero e, por conseguinte, dizemos que a altura de uma árvore vazia é negativa e vale -1.

Exercício: Mostrar que uma árvore binária de altura h tem, no mínimo, h+1 nós, e, no máximo, 2h+1 –1.

Representação em C

Análogo ao que fizemos para as demais estruturas de dados, podemos definir um tipo para representar uma árvore binária. Para simplificar a discussão, vamos considerar que a informação que queremos armazenar nos nós da árvore são valores de caracteres simples. Vamos inicialmente discutir como podemos representar uma estrutura de árvore binária em C. Que estrutura podemos usar para representar um nó da árvore? Cada nó deve armazenar três informações: a informação propriamente dita, no caso um caractere, e dois ponteiros para as sub-árvores, à esquerda e à direita. Então a estrutura de C para representar o nó da árvore pode ser dada por:

struct arv { char info; struct arv* esq; struct arv* dir; };

Da mesma forma que uma lista encadeada é representada por um ponteiro para o primeiro nó, a estrutura da árvore como um todo é representada por um ponteiro para o nó raiz.

Como acontece com qualquer TAD (tipo abstrato de dados), as operações que fazem sentido para uma árvore binária dependem essencialmente da forma de utilização que se pretende fazer da árvore. Nesta seção, em vez de discutirmos a interface do tipo abstrato para depois mostrarmos sua implementação, vamos optar por discutir algumas operações mostrando simultaneamente suas implementações. Ao final da seção apresentaremos um arquivo que pode representar a interface do tipo. Nas funções que se seguem, consideraremos que existe o tipo Arv definido por:

typedef struct arv Arv;

Como veremos as funções que manipulam árvores são, em geral, implementadas de forma recursiva, usando a definição recursiva da estrutura.

Vamos procurar identificar e descrever apenas operações cuja utilidade seja a mais geral possível. Uma operação que provavelmente deverá ser incluída em todos os casos é a inicialização de uma árvore vazia. Como uma árvore é representada pelo endereço do nó raiz, uma árvore vazia tem que ser representada pelo valor NULL. Assim, a função que inicializa uma árvore vazia pode ser simplesmente:

Estruturas de Dados – PUC-Rio12-5

Arv* inicializa(void) { return NULL; }

Para criar árvores não vazias, podemos ter uma operação que cria um nó raiz dadas a informação e suas duas sub-árvores, à esquerda e à direita. Essa função tem como valor de retorno o endereço do nó raiz criado e pode ser dada por:

Arv* cria(char c, Arv* sae, Arv* sad){ Arv* p=(Arv*)malloc(sizeof(Arv)); p->info = c; p->esq = sae; p->dir = sad; return p; }

As duas funções inicializa e cria representam os dois casos da definição recursiva de árvore binária: uma árvore binária (Arv* a;) é vazia (a = inicializa();) ou é composta por uma raiz e duas sub-árvores (a = cria(c,sae,sad);). Assim, com posse dessas duas funções, podemos criar árvores mais complexas.

Exemplo: Usando as operações inicializa e cria, crie uma estrutura que represente a árvore da Figura 13.5.

O exemplo da figura pode ser criada pela seguinte seqüência de atribuições.

Arv* a2= cria('b',inicializa(),a1);/* sub-árvore com 'b'
Arv* a5= cria('c',a3,a4);/* sub-árvore com 'c'
Arv* a = cria('a',a2,a5 );/* árvore com raiz 'a'

Arv* a1= cria('d',inicializa(),inicializa()); /* sub-árvore com 'd' */ */ Arv* a3= cria('e',inicializa(),inicializa()); /* sub-árvore com 'e' */ Arv* a4= cria('f',inicializa(),inicializa()); /* sub-árvore com 'f' */ */ */

Alternativamente, a árvore poderia ser criada com uma única atribuição, seguindo a sua estrutura, “recursivamente”:

cria('b',
inicializa(),
cria('d', inicializa(), inicializa())
),
cria('c',
cria('e', inicializa(), inicializa()),
cria('f', inicializa(), inicializa())
)
);

Arv* a = cria('a',

Para tratar a árvore vazia de forma diferente das outras, é importante ter uma operação que diz se uma árvore é ou não vazia. Podemos ter:

Estruturas de Dados – PUC-Rio12-6 int vazia(Arv* a) { return a==NULL; }

Uma outra função muito útil consiste em exibir o conteúdo da árvore. Essa função deve percorrer recursivamente a árvore, visitando todos os nós e imprimindo sua informação. A implementação dessa função usa a definição recursiva da árvore. Vimos que uma árvore binária ou é vazia ou é composta pela raiz e por duas sub-árvores. Portanto, para imprimir a informação de todos os nós da árvore, devemos primeiro testar se a árvore é vazia. Se não for, imprimimos a informação associada a raiz e chamamos (recursivamente) a função para imprimir os nós das sub-árvores.

printf("%c ", a->info); /* mostra raiz */
imprime(a->esq); /* mostra sae */
imprime(a->dir); /* mostra sad */

void imprime (Arv* a) { if (!vazia(a)){ }

(Parte 1 de 3)

Comentários