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.

R: A estrutura árvore representa uma das estruturas mais importantes da área da computação, principalmente em aplicações. Dentro da estrutura de árvores existe um relacionamento lógico entre os componentes da estrutura, isto é, existe uma hierarquia ou subordinação onde um subconjunto dos componentes é subordinado a outro. A estrutura de árvore é utilizada em casos onde os dados ou objetos a serem representados possuem relações hierárquicas entre si.

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).

R:

• Organogramas de empresas – hierarquia entre os empregados
• Ordenação de Valores – Árvore ordenada. Ex. esquerda / raiz / direita
• Abstração de Composição – um objeto é composto por outros objetos

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.

R: Uma árvore é um conjunto finito A de zero ou mais nós, tais que:

• Caso o número de nós seja maior que zero, existe um nó denominado raiz da árvore, os demais nós formam m >= 0 conjuntos disjuntos S1, S2, ..., Sm, onde cada um destes conjuntos é uma árvore (Si são denominadas sub-árvores).
• Número de nós zero: árvore vazia.
• Cada nó da árvore é a raiz de uma subárvore. 
• Grau de um Nó é o número de subárvores de um nó. Nó de grau zero é denominado nó folha ou nó terminal. 
• Nível de um Nó raiz possui nível zero. Demais nós: é o comprimento do caminho que vai da raiz até o nó.
• Altura de uma Árvore é o maior nível de uma árvore (mais alto).
• Floresta conjunto de zero ou mais árvores disjuntas. Se o nó raiz de uma árvore for eliminado, as subárvores, que restarem serão chamadas de floresta.
• Nó Pai é o pai das raízes de suas subárvores e Nó Filho  possui um nó pai associado.     
• Nós Irmãos são os vários filhos de um nó pai.

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.

R:

Diagrama de inclusão

Representação Hierárquica

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.

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

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.

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