QUESTIONÁRIO 02 – ÁRVORES BINÁRIAS

1 - Uma árvore é um conjunto de 1 ou mais nós, onde existe um nó especial chamado raíz e os demais nós formam conjuntos disjuntos onde cada conjunto é uma árvore (subárvore). O que caracterizaria então uma árvore Binária?

R: É uma estrutura na qual o número máximo de filhos permitido pelo nó é dois. Ou seja, pode ter zero ou no máximo dois filhos.

2 - Uma árvore binária tem por tanto uma subárvore da esquerda e outra subárvore da direita (mesmo que exista uma só ou nenhuma), existe alguma maneira de calcular o número máximo de elementos de uma árvore conhecendo sua altura?

R: Sim. 2n -1.

3 - Nas árvores binárias podemos percorrer os elementos através de alguns percursos, quais são eles?

R: Pré-ordem, In-ordem e Pós-ordem.

4 - A definição do percurso EM-Ordem/IN-Ordem é:

R: In-ordem percorre sua sub-arvore esquerda, visita a raiz e percorre a sua sub-arvore direita em in-ordem.

5 - A definição do percurso PRÉ-Ordem/PRÉ-Fixado é:

R: Pré-ordem visita a raiz, percorre sub-arvore esquerda e percorre sub-arvore direita.

6 - A definição do percurso PÓS-Ordem/PÓS-Fixado é:

R: Pós-ordem percorre sub-arvore esquerda, percorre sub-arvore direita e visita a raiz.

7 - Existe outra maneira de percorrer uma árvore (não obrigatoriamente binária), conhecida como percurso por extensão ou largura. Explique esse processo.

R: O percurso em largura é mais bem compreendido de forma não-recursiva. O percurso em largura de uma árvore visita os nós na ordem dos níveis da árvore. O percurso em largura primeiro visita todos os nós do nível 0, depois todos os nós do nível um, e daí por diante. Os nós são visitados da esquerda para a direita em cada um dos níveis.

8 –

R:

• Pré-ordem ->  A, B, D, G, C, E, H, I, F.
• In-ordem   ->  D, G, B, A, H, E, I, C, F.
• Pós-ordem ->  G, D, B, H, I, E, F, C, A.

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