Introdução
Last updated
Was this helpful?
Last updated
Was this helpful?
Em muitos casos, pesquisadores utilizam estruturas da natureza como embasamento para suas descobertas. O movimento das formigas já foi objeto de estudos para algoritmos de definição de rotas (caminhos), o DNA e o processo de reprodução foram base para um dos principais métodos para cálculo do melhor (menor) caminho. As árvores são muito utilizadas na representação genealógica, pois sua estrutura de ramificações é ideal para a representação das conexões familiares e ou hierárquicas.
Na computação, existem diversas aplicações que necessitam de estruturas mais complexas que as listas estudadas até agora para disposição dos seus elementos. A representação hierárquica dos funcionários de uma empresa pode ser associada a uma árvore invertida:
A presidência seria a raiz, os diretores o caule e a primeira ramificação e os demais cargos, representados nas outras ramificações até o nível das folhas. Inúmeros problemas do cotidiano podem ser modelados através de modelos de árvores.
As árvores utilizam uma estrutura de nós, mas são conceitualmente diferentes das listas encadeadas. Nas listas, os elementos (nós) são ligados sequencialmente, já nas árvores os elementos estão dispostos de forma hierárquica. A estrutura das árvores é composta por:
raiz: elemento principal;
ramos ou filhos; e
folha ou nó terminal.
A raiz é ligada aos ramos ou filhos. Estes são ligados a outros elementos que também possuem outros ramos. O elemento da extremidade, que não possui ramos, é chamado folha ou nó terminal.
Representação gráfica de uma árvore:
Definições:
Nós folhas: são aqueles que não têm filhos. Exemplo: {B, G , H, E, I}
Ramos ou filhos: são aqueles que possuem 1 ou mais descendentes. Ex: {A, C, D, F}, ou seja, não são nós folhas.
Exemplo de representação em árvore: expressão aritmética a + (b * (c / d) – e):
Nível (profundidade) e altura de um nó:
O nível ou profundidade de um nó “n” é o número de nós existente entre a raiz até o nó “n”. Portanto, o nível da raiz é 0.
A altura de um nó “n” é o número de nós no maior caminho de “n” até um de seus descendentes. As folhas têm altura 0.
O grau de um nó é o número total de filhos. Da árvore, é o máximo filhos de um nó. No exemplo acima, a árvore tem grau 2 (dois).
Uma árvore pode ser representada e implementada com base na disposição de seus nós (elementos) na memória através da i) representação por adjacência e ii) representação encadeada.
Neste tipo de representação, os nós são armazenados sequencialmente, de acordo com uma convenção predeterminada.
Essa representação é muito útil para armazenamento permanente, mas ineficiente para manipular árvores dinâmicas (que necessitam de operações de inserções e remoções de nós).
Os valores representam a quantidade de filhos que cada nó possui. Assim, “A” possui dois filhos, os nós “B” e “C”. “B” não possui nenhum filho e “C” possui 3 filhos: “D” (que possui 2 filhos: “G” e “H”), “E” que não possui filhos e “F” que possui 1 filho (“I”).
Este tipo de representação emprega os conceitos de listas encadeadas onde cada nó (elemento) contém:
As informações do nó; e
Referências aos ramos do nó (ponteiro para cada um dos seus nós filhos).
A desvantagem desta representação é a grande quantidade de referências a subárvores nulas.
Na árvore acima, temos o nó raiz “ligado” aos nós “B” e “C” e o nó “B” não possui filhos. Já o nó “C” possui ligação aos nós “D”, “E” e “F”. Nesta representação, deve-se definir inicialmente a quantidade máxima de filhos que cada nó pode possuir, que, neste exemplo, é 3. Assim, ao se implementar cada nó, a quantidade de ponteiros deve ser determinada.
Para as implementações das árvores, nos itens a seguir, utilizaremos a representação encadeada.
