EstruturaDadosArvores

Estrutura de dados em Arvores Estrutura dadas refletida pelo filtro (indice)

1. Arvore conceitual

2. Organizacao real Armazenamento sem uso de ponteiros

3. Terminologia

ÁRVORE é um conjunto finito de um ou mais nós, tais que:

a)      existe um nó denominado raiz

b)      os demais nós formam

          i.      m >= 0 conjuntos disjuntos (cada nó só pode ter um pai)

          ii.      s1, s2, ... sm, tais que cada um desses conjuntos também é uma árvore (sub-árvore)

RAIZ – nó de origem da árvore;
FOLHAS – nós que não têm filhos;
GRAU DE UM NÓ – número de filhos de cada nó (número de sub-árvores de um nodo);
NÍVEL DE UM NÓ – por definição, é zero para a raiz, e, para os demais nós, é o número de “linhas” que ligam o nó à raiz (é a distância do nodo até o nodo raiz);
ALTURA DA ÁRVORE – é o nível mais alto da árvore;
FLORESTA – conjunto de árvores disjuntas (eliminando-se a raiz de uma árvore, obtém-se a floresta);
GALHOS DE UMA ÁRVORE – quaisquer nodos que não são raiz e nem folhas de árvore;
ARESTA DE UMA ÁRVORE – é a linha que liga dois nodos da árvore;
CAMINHO – diz-se que existe um caminho entre dois nodos A e B de uma árvore, se a partir do nodo A pode-se chegar ao nodo B percorrendo-se as arestas que ligam os nodos intermediários entre A e B;

4. Reprentações As árvores podem ser representadas de diversos modos:
   1. Representação hierárquica;
   2. Representação por conjunto;
   3. Representação por expressão parentetizada;

        ( A ( B ( D ( ) E ( ) ) C ( F ( ) ) ) )

   4. Representação por expressão não parentetizada.

        A 2 B 2 D 0 E 0 C 1 F 0

DETALHES

    * Representação hierárquica melhor VISUALIZAÇÃO
    * Representação parentetizada e não parentetizada são úteis para guardar em arquivos os dados de uma árvore.
    * Por definição (s1, s2, ...sm são disjuntos) cada nós só pode ter um pai.

5. Caminho em arvore É a maneira ordenada de percorrer todos os nodos da árvore (percorrer todos os seus nós, sem repetir nenhum e sem deixar de passar por nenhum).
É utilizada, por exemplo, para consultar ou alterar as informações contidas nos nós.

As três maneiras mais usuais para percorrer os nós são:

   1. Caminhamento Pré-fixado
         1. visita a raiz
         2. percorre a sub-árvore da esquerda
         3. percorre a sub-árvore da direita

   2. Caminhamento In-fixado
         1. percorre a sub-árvore da esquerda
         2. visita a raiz
         3. percorre a sub-árvore da direita

   3. Caminhamento Pós-fixado
         1. percorre a sub-árvore da esquerda
         2. percorre a sub-árvore da direita
         3. visita a raiz

6. Operações em arvore