QUESTIONÁRIO 01 – ÁRVORES, CONCEITOS GERAIS

1)   A estrutura de uma árvore é especializada em representar hierarquia. Defina e caracterize de forma completa o conceito da Estrutura Árvore.

Uma árvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:

1. uma estrutura (uma árvore);
2. um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
3. Não Existe árvores vazias, no minímo haverá um nó raiz(que não possui pai)

Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.

2)         O conceito da estrutura árvore é muito importante para as disciplinas de Sistema Operacional e Banco de Dados. Dê exemplos da aplicação prática da estrutura de dados árvore, explicando cada exemplo (pelo menos 3).
Hierarquia de classes: São as classes e subclasses, ou seja, uma classe subordinando a outra;
Ordenação de Valores: São as  Árvore ordenada na esquerda, na  raiz, e na direita;
Organogramas de empresas: É a  hierarquia entre os empregados de uma empresa.

3)         Para compreender o conceito de árvore é necessário entender alguns conceitos básicos. Explique o conceito de raíz, nó filho, nó pai, nó terminal, nó ascendente, nó descendente, grau, altura, nível, profundidade, caminho e floresta.
Os conceitos básicos da estrutura árvore são:

• Raiz – é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8);
• Nós – são todos os itens guardados na árvore;
• Nós Filhos – são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3);
• Nós Pais – são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14);
• Folhas ou nó terminal – são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13);
• Nó Ascendente- Nó acima de um dado nó, em direção a raiz (No caso da figura acima, o nó 8 é ancestral do nó 3, 10 ,1, 6 …, 13);
• Nó Descendente- Nó abaixo de um dado nó (No caso da figura acima, o nó 3 e 10 é ascendente de 8);
• Grau de um nó é o número de nós  filhos do mesmo. Obviamente um nó folha tem grau zero;
• Nível de um nó é o número de nós existentes no caminho entre a raiz e o próprio nó;
• Altura de uma árvore  (também denominada profundidade) é a distância entre x e o seu descendente mais afastado. Mais precisamente, a altura de x é o número de passos do mais longo caminho que leva de x até uma folha somando um;
• caminho da árvore é composto por uma seqüência de nós consecutivos (n₁, n₂, …, n_k-1, n_k) tal que existe sempre a relação n_i é pai de n_i+1;
• Floresta: é um conjunto de zero ou mais árvores disjuntas, ou seja, se for eliminado o nó raiz da árvore, as sub-árvores que restarem chama-se de florestas.

4)         Existem diversas maneiras de representar a estrutura de uma árvore. Demonstre e conceitue a representação Hierárquica, Diagrama de Inclusão, Expressão parametrizada e Expressão não parametrizada.


Representação hierárquica





Representação por conjuntos (diagrama de inclusão)

      Representação por expressão parentetizada (parênteses aninhados)
      Cada conjunto de parênteses correspondentes contém um nodo e seus  filhos.
      Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.

      Representação por expressão não parentetizada
      Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em seguida por esses filhos, representados do mesmo modo.