Estrutura de dados - árvores

Nomenclatura

- Raiz: é o nó de mais alto nível da árvore (primeiro nó da árvore);
- Folha: nó com grau igual a zero;
- Nível: é o número de nós que vai da raiz até um determinado nó;
- Altura: Nível mais alto da árvore;
- Pai: a raiz de uma subárvore é pai das raízes de suas subárvores;
- Filho: os nós-raízes de uma subárvore; e
- Irmão:  nós raízes das subárvores de mesmo nível.

"Especialistas em produtividade dizem que as soluções são obtidas pensando-se de maneira não-linear."

Afinal, o que significa não-linear já tão defendido por especialistas?

São relacionamentos organizacionais mais ricos que simples relações do "antes" e "depois" entre objetos em uma sequencia.

Atalho na organização de dados: permitem implementar uma série de algoritmos de forma mais rápida do que usando estruturas de dados lineares, tais como listas, vetores ou sequencias.

OS RELACIONAMENTOS PODEM SER HIERÁRQUICOS

Ex: árvores genealógicas.

TIPO ABSTRATO DE DADOS ÁRVORE

Uma árvore é um tipo abstrato de dados que armazena elementos de maneira hierárquica. Com excessão do elemento do topo (raiz), cada elemento da árvores tem um elemento pai e zero ou mais elementos filhos.

Estrutura de dados contendo um número finito de elementos que pode estar vazia ou particionada em subconjuntos. O primeiro subconjunto contém um único elemento chamado raiz. Os outros subconjuntos são, em si mesmo árvores, chamados subárvores. Essa é um definição recursida de árvore.

árvore > raiz + árvores

                    > raiz + árvores                       

                                    > ...

PROPRIEDADES BASICAS E TERMINOLOGIA

Uma árvore T é um conjunto de nós que armazena elementos em relacionamentos pai-filho com as seguintes propriedades:

* T tem um nó especial r, chamado de raiz de T;

* Cada nó v e T diferente de r tem um nó pai u.

Propriedades:

* Se um nó u é pai de nó v, então dizemos que v é filho de u;

* Dois nós que são filhos do mesmo pai são irmãos;

* Um nó é externo se não tem filhos e são conhecidos com folhas;

* Um nó é interno se tem um ou mais filhos;

Na maioria dos sistemas operacionais, os arquivos são organizados de forma hierárquica utilizando o conceito de diretório ou pasta. As pastas, nessa árvore hierárquica de diretório, representam os nós internos, enquanto que os arquivos são os nós externos.

* Uma subárvore de T enraizada no nó v é a árvore formada por todos os descendentes de v em T (incluindo o próprio v);

* O ancestral de um nó é qualquer nó acima de sua hierarquia que possui relação de pai como seu pai ou o pai dele e assim sucessivamente;

* O descendente segue o mesmo conceito de forma inversa

A relação de herança entre classes de um programa java forma uma árvore. A classe java.lang.Object é ancestral de todas as demais classes.

* Uma árvore é ordenada se existe uma ordem linear definida para os filhos de cada nó, ou seja, se podemos identificar os filhos de um nó como sendo o primeiro, segundo, terceiro e assim por diante. tal ordenação é determinada pelo uso que se quer dar a árvore;

*  Uma árvore binária é uma árvore ordenada na qual todo nó tem, no máximo dois filhos:

 

+ uma árvore binária é própria se cada um dos seus nós tiver zero ou dois filhos;

+ para cada nó interno de uma árvore binária, nomeamos cada filho como filho da esquerda e filho da direita;

+ as subárvores enraizadas no filho da esquerda ou da direta. são chamadas de subárvore esquerda e subárvore direita, respectivamente.

árvore de decisão sobre escolaridade

árvore de decisão sobre expressão aritmética

MÉTODOS DE ÁRVORES

O TAD árvore armazena elementos em posições, como as de uma lista, que são definidas em relação às posições de seus vizinhos. As posições de uma árvore são seus nós, e o posicionamento pela vizinhança satisfaz as relações pai-filho que definem uma árvore válida. Como as posições de uma lista, um objeto posição para uma árvore suporta os métodos:

elemento(): retorna o objeto nesta posição

entrada: nenhuma

saida: objeto

raiz(): retorna a raiz da árvores

entrada: nenhuma

saída: posição

filhos(): retorna um iterador sobre os filhos do nó v.

entrada: posição

saída: iterador de posição

Além dos métodos de acesso fundamental acima, pode-se apresentar os seguintes métodos de consultas:

ehinterno(): testa se um nó v é interno

entrada: posição

saída: booleano

ehexterno(): testa se um nó v é externo

entrada: posição

saída: booelano
 

ehraiz(): testa um nó v é raiz

entrada: posição

saída: booleano

INTERFACE SIMPLES de uma árvore em java

public interface arvore {

 

// método de acesso

               public No raiz();

               public No pai(No v);

               public No filhos (No v);

// métodos de consulta

              public boolean ehInterno();

              public boolean ehExterno();

              public boolean ehRaiz()

}