Estruturas de Dados - Árvores: Conceitos e Implementação em C

Estruturas de Dados PUCRio 121 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 sub diretórios e arquivos Por sua vez dentro dos subdiretórios podemos armazenar outros subdiretórios e arquivos e assim por diante recursivamente A Figura 131 mostra uma imagem de uma árvore de diretório no Windows 2000 Figura 131 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 132 exemplifica a estrutura de uma árvore Figura 132 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 subárvores Estruturas de Dados PUCRio 122 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 131 Árvores binárias 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 36415 é ilustrada na Figura 133 Figura 133 Árvore da expressão 36 41 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 134 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 1 4 6 3 5 Estruturas de Dados PUCRio 123 Figura 134 Representação esquemática da definição da estrutura de árvore binária A Figura 135 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 135 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 á r v o r e d a F i g u r a 1 3 5 é r e p r e s e n t a d a p o r abdcef 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 136 são distintas Figura 136 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 f e d a b a b raiz sad sae vazia Estruturas de Dados PUCRio 124 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 135 é 2 e a altura das árvores da Figura 136 é 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 h1 nós e no máximo 2h1 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 PUCRio 125 Arv inicializavoid 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 criachar c Arv sae Arv sad Arv pArvmallocsizeofArv pinfo c pesq sae pdir 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 criacsaesad 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 135 O exemplo da figura pode ser criada pela seguinte seqüência de atribuições Arv a1 criadinicializainicializa subárvore com d Arv a2 criabinicializaa1 subárvore com b Arv a3 criaeinicializainicializa subárvore com e Arv a4 criafinicializainicializa subárvore com f Arv a5 criaca3a4 subárvore com c Arv a criaaa2a5 árvore com raiz a Alternativamente a árvore poderia ser criada com uma única atribuição seguindo a sua estrutura recursivamente Arv a criaa criab inicializa criad inicializa inicializa criac criae inicializa inicializa criaf inicializa inicializa 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 PUCRio 126 int vaziaArv a return aNULL 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 void imprime Arv a if vaziaa printfc ainfo mostra raiz imprimeaesq mostra sae imprimeadir mostra sad Exercício a simule a chamada da função imprime aplicada à arvore ilustrada pela Figura 135 para verificar que o resultado da chamada é a impressão de a b d c e f b Repita a experiência executando um programa que crie e mostre a árvore usando o seu compilador de C favorito Exercício Modifique a implementação de imprime de forma que a saída impressa reflita além do conteúdo de cada nó a estrutura da árvore usando a notação introduzida a n t e r i o r m e n t e A s s i m a s a í d a d a f u n ç ã o s e r i a abdcef Uma outra operação que pode ser acrescentada é a operação para liberar a memória alocada pela estrutura da árvore Novamente usaremos uma implementação recursiva Um cuidado essencial a ser tomado é que as subárvores devem ser liberadas antes de se liberar o nó raiz para que o acesso às subárvores não seja perdido antes de sua remoção Neste caso vamos optar por fazer com que a função tenha como valor de retorno a árvore atualizada isto é uma árvore vazia representada por NULL Arv libera Arv a if vaziaa liberaaesq libera sae liberaadir libera sad freea libera raiz return NULL Devemos notar que a definição de árvore por ser recursiva não faz distinção entre árvores e subárvores Assim cria pode ser usada para acrescentar enxertar uma subárvore em um ramo de uma árvore e libera pode ser usada para remover podar uma subárvore qualquer de uma árvore dada Exemplo Considerando a criação da árvore feita anteriormente Estruturas de Dados PUCRio 127 Arv a criaa criab inicializa criad inicializa inicializa criac criae inicializa inicializa criaf inicializa inicializa Podemos acrescentar alguns nós com aesqesq criax criayinicializainicializa criazinicializainicializa E podemos liberar alguns outros com adiresq liberaadiresq Deixamos como exercício a verificação do resultado final dessas operações É importante observar que análogo ao que fizemos para a lista o código cliente que chama a função libera é responsável por atribuir o valor atualizado retornado pela função no caso uma árvore vazia No exemplo acima se não tivéssemos feito a atribuição o endereço armazenado em rdiresq seria o de uma área de memória não mais em uso Exercício Escreva uma função que percorre uma árvore binária para determinar sua altura O protótipo da função pode ser dado por int alturaArv a Uma outra função que podemos considerar percorre a árvore buscando a ocorrência de um determinado caractere c em um de seus nós Essa função tem como retorno um valor booleano um ou zero indicando a ocorrência ou não do caractere na árvore int busca Arv a char c if vaziaa return 0 árvore vazia não encontrou else return ainfoc buscaaesqc buscaadirc Note que esta forma de programar busca em C usando o operador lógico ou faz com que a busca seja interrompida assim que o elemento é encontrado Isto acontece porque se cainfo for verdadeiro as duas outras expressões não chegam a ser avaliadas Analogamente se o caractere for encontrado na subárvore da esquerda a busca não prossegue na subárvore da direita Podemos dizer que a expressão return cainfo buscaaesqc buscaadirc é equivalente a Estruturas de Dados PUCRio 128 if cainfo return 1 else if buscaaesqc return 1 else return buscaadirc Finalmente considerando que as funções discutidas e implementadas acima formam a interface do tipo abstrato para representar uma árvore binária um arquivo de interface arvbinh pode ser dado por typedef struct arv Arv Arv inicializa void Arv cria char c Arv e Arv d int vazia Arv a void imprime Arv a Arv libera Arv a int busca Arv a char c Ordens de percurso em árvores binárias A programação da operação imprime vista anteriormente seguiu a ordem empregada na definição de árvore binária para decidir a ordem em que as três ações seriam executadas Entretanto dependendo da aplicação em vista esta ordem poderia não ser a preferível podendo ser utilizada uma ordem diferente desta por exemplo imprimeaesq mostra sae imprimeadir mostra sad printfc ainfo mostra raiz Muitas operações em árvores binárias envolvem o percurso de todas as subárvores executando alguma ação de tratamento em cada nó de forma que é comum percorrer uma árvore em uma das seguintes ordens préordem trata raiz percorre sae percorre sad ordem simétrica percorre sae trata raiz percorre sad pósordem percorre sae percorre sad trata raiz Para função para liberar a árvore por exemplo tivemos que adotar a pósordem liberaaesq libera sae liberaadir libera sad freea libera raiz Na terceira parte do curso quando tratarmos de árvores binárias de busca apresentaremos um exemplo de aplicação de árvores binárias em que a ordem de percurso importante é a ordem simétrica Algumas outras ordens de percurso podem ser definidas mas a maioria das aplicações envolve uma dessas três ordens percorrendo a sae antes da sad Exercício Implemente versões diferentes da função imprime percorrendo a árvore em ordem simétrica e em pósordem Verifique o resultado da aplicação das duas funções na árvore da Figura 135 Estruturas de Dados PUCRio 129 132 Árvores genéricas Nesta seção vamos discutir as estruturas conhecidas como árvores genéricas Como vimos numa árvore binária o número de filhos dos nós é limitado em no máximo dois No caso da árvore genérica esta restrição não existe Cada nó pode ter um número arbitrário de filhos Essa estrutura deve ser usada por exemplo para representar uma árvore de diretórios Como veremos as funções para manipularem uma árvore genérica também serão implementadas de forma recursiva e serão baseadas na seguinte definição uma árvore genérica é composta por um nó raiz e zero ou mais subárvores Estritamente segundo essa definição uma árvore não pode ser vazia e a árvore vazia não é sequer mencionada na definição Assim uma folha de uma árvore não é um nó com subárvores vazias como no caso da árvore binária mas é um nó com zero sub árvores Em qualquer definição recursiva deve haver uma condição de contorno que permita a definição de estruturas finitas e no nosso caso a definição de uma árvore se encerra nas folhas que são identificadas como sendo nós com zero subárvores Como as funções que implementaremos nesta seção serão baseadas nessa definição não será considerado o caso de árvores vazias Esta pequena restrição simplifica as implementações recursivas e em geral não limita a utilização da estrutura em aplicações reais Uma árvore de diretório por exemplo nunca é vazia pois sempre existe o diretório base o diretório raiz Como as subárvores de um determinado nó formam um conjunto linear e são dispostas numa determinada ordem faz sentido falarmos em primeira subárvore sa1 segunda subárvore sa2 etc Um exemplo de uma árvore genérica é ilustrado na Figura 137 Figura 137 Exemplo de árvore genérica Nesse exemplo podemos notar que o a árvore com raiz no nó a tem 3 subárvores ou equivalentemente o nó a tem 3 filhos Os nós b e g tem dois filhos cada um os nós c e i tem um filho cada e os nós d e h e j são folhas e tem zero filhos Estruturas de Dados PUCRio 1210 De forma semelhante ao que foi feito no caso das árvores binárias podemos representar essas árvores através de notação textual seguindo o padrão raiz sa1 sa2 san Com esta notação a árvore da Figura 137 seria representada por a a b c d e f g h i j Podemos verificar que a representa a árvore do exemplo seguindo a seqüência de definição a partir das folhas a1 d a2 c a1 c d a3 e a4 b a2 a3 b c d e a5 f a6 h a7 j a8 i a7 i j a9 g a6 a8 g h i j a a a4 a5 a9 a b c d e f g h i j Representação em C Dependendo da aplicação podemos usar várias estruturas para representar árvores levando em consideração o número de filhos que cada nó pode apresentar Se soubermos por exemplo que numa aplicação o número máximo de filhos que um nó pode apresentar é 3 podemos montar uma estrutura com 3 campos para apontadores para os nós filhos digamos f1 f2 e f3 Os campos não utilizados podem ser preenchidos com o valor nulo NULL sendo sempre utilizados os campos em ordem Assim se o nó n tem 2 filhos os campos f1 e f2 seriam utilizados nessa ordem para apontar para eles ficando f3 vazio Prevendo um número máximo de filhos igual a 3 e considerando a implementação de árvores para armazenar valores de caracteres simples a declaração do tipo que representa o nó da árvore poderia ser struct arv3 char val struct no f1 f2 f3 A Figura 138 indica a representação da árvore da Figura 137 com esta organização Como se pode ver no exemplo em cada um dos nós que tem menos de três filhos o espaço correspondente aos filhos inexistentes é desperdiçado Além disso se não existe um limite superior no número de filhos esta técnica pode não ser aplicável O mesmo acontece se existe um limite no número de nós mas esse limite será raramente alcançado pois estaríamos tendo um grande desperdício de espaço de memória com os campos não utilizados Estruturas de Dados PUCRio 1211 a b c d f e h g j i Figura 138 Árvore com no máximo três filhos por nó Uma solução que leva a um aproveitamento melhor do espaço utiliza uma lista de filhos um nó aponta apenas para seu primeiro prim filho e cada um de seus filhos exceto o último aponta para o próximo prox irmão A declaração de um nó pode ser struct arvgen char info struct arvgen prim struct arvgen prox A Figura 139 mostra o mesmo exemplo representado de acordo com esta estrutura Uma das vantagens dessa representação é que podemos percorrer os filhos de um nó de forma sistemática de maneira análoga ao que fizemos para percorrer os nós de uma lista simples Estruturas de Dados PUCRio 1212 a b c d f e h g j i Figura 139 Exemplo usando lista de filhos Com o uso dessa representação a generalização da árvore é apenas conceitual pois concretamente a árvore foi transformada em uma árvore binária com filhos esquerdos apontados por prim e direitos apontados por prox Naturalmente continuaremos a fazer referência aos nós nos termos da definição original Por exemplo os nós b f e g continuarão a ser considerados filhos do nó a como indicado na Figura 137 mesmo que a representação usada na Figura 139 os coloque a distâncias variáveis do nó pai Tipo abstrato de dado Para exemplificar a implementação de funções que manipulam uma árvore genérica vamos considerar a criação de um tipo abstrato de dados para representar árvores onde a informação associada a cada nó é um caractere simples Nessa implementação vamos optar por armazenar os filhos de um nó numa lista encadeada Podemos definir o seguinte conjunto de operações cria cria um nó folha dada a informação a ser armazenada insere insere uma nova subárvore como filha de um dado nó imprime percorre todos os nós e imprime suas informações busca verifica a ocorrência de um determinado valor num dos nós da árvore libera libera toda a memória alocada pela árvore A interface do tipo pode então ser definida no arquivo arvgenh dado por typedef struct arvgen ArvGen ArvGen cria char c void insere ArvGen a ArvGen sa void imprime ArvGen a int busca ArvGen a char c void libera ArvGen a Estruturas de Dados PUCRio 1213 A estrutura arvgen que representa o nó da árvore é definida conforme mostrado anteriormente A função para criar uma folha deve alocar o nó e inicializar seus campos atribuindo NULL para os campos prim e prox pois tratase de um nó folha ArvGen cria char c ArvGen a ArvGen mallocsizeofArvGen ainfo c aprim NULL aprox NULL return a A função que insere uma nova subárvore como filha de um dado nó é muito simples Como não vamos atribuir nenhum significado especial para a posição de um nó filho a operação de inserção pode inserir a subárvore em qualquer posição Neste caso vamos optar por inserir sempre no início da lista que como já vimos é a maneira mais simples de inserir um novo elemento numa lista encadeada void insere ArvGen a ArvGen sa saprox aprim aprim sa Com essas duas funções podemos construir a árvore do exemplo da Figura 137 com o seguinte fragmento de código cria nós como folhas ArvGen a criaa ArvGen b criab ArvGen c criac ArvGen d criad ArvGen e criae ArvGen f criaf ArvGen g criag ArvGen h criah ArvGen i criai ArvGen j criaj monta a hierarquia inserecd inserebe inserebc insereij inseregi inseregh insereag insereaf insereab Para imprimir as informações associadas aos nós da árvore temos duas opções para percorrer a árvore préordem primeiro a raiz e depois as subárvores ou pósordem primeiro as subárvores e depois a raiz Note que neste caso não faz sentido a ordem simétrica uma vez que o número de subárvores é variável Para essa função vamos optar por imprimir o conteúdo dos nós em préordem void imprime ArvGen a ArvGen p printfc ainfo for paprim pNULL ppprox imprimep Estruturas de Dados PUCRio 1214 A operação para buscar a ocorrência de uma dada informação na árvore é exemplificada abaixo int busca ArvGen a char c ArvGen p if ainfoc return 1 else for paprim pNULL ppprox if buscapc return 1 return 0 A última operação apresentada é a que libera a memória alocada pela árvore O único cuidado que precisamos tomar na programação dessa função é a de liberar as sub árvores antes de liberar o espaço associado a um nó isto é usar pósordem void libera ArvGen a ArvGen p aprim while pNULL ArvGen t pprox liberap p t freea Exercício Escreva uma função com o protótipo ArvGen copiaArvGena para criar dinamicamente uma cópia da árvore Exercício Escreva uma função com o protótipo int igualArvGena ArvGenb para testar se duas árvores são iguais