QUESTIONÁRIO 02 – ED II

QUESTIONÁRIO  02 – ÁRVORES BINÁRIAS

EXERCÍCIO - PERCURSO ÁRVORE BINÁRIA.

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

Resposta:
A árvore binária deve conter até no máximo dois filhos (nós), ou seja, os nós de uma árvore binária possuem graus zero, um ou dois. Outra característica é a recursividade, que nada mais é, que a utilização da recursão nas operações binárias.

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?

Resposta:
Sim, por que além da raiz cada nó poderá ter até dois novos nós.

Formula 2ⁿ – 1 = Numero máximo de elementos de uma árvore binária.
       (*n - Altura da árvore)

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

Resposta:
IN-Ordem, PRÉ-Ordem, PÓS-Ordem.

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

Resposta:

A raiz fica entre as sub-arvores esquerda e direita.

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

Resposta:

A raiz vem antes das sub-arvores esquerda e direita.

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

Resposta:

A raiz vem depois das sub-arvores esquerda e direita.

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

Resposta:

Um percurso em extensão é visitar cada nó começando do menor nível e move-se para os níveis mais altos, nível após nível, percorrendo cada nó da esquerda para a direita. Sua implementação é direta quando uma fila é utilizada. Depois que um nó é percorrido, seus filhos, se houver algum, são colocados no final da fila e o nó no início da fila é percorrido. Assim, os nós do nível n+1 serão visitados somente depois de ter percorrido todos os nós do nível.

Percurso em largura ou em nível (breadth-first): percorre a árvore em ordem crescente de seus níveis e, em cada nível, da esquerda para a direita. Uma fila é usada para realizar este percurso.

 - Faça o percurso em pré-ordem, in-ordem e pós-ordem da seguinte árvore:

Respostas:

PRÉ-ORDEM: (R E D)

A  B  D  G  C  E  F  H  I 

IN-ORDEM: (E R D)

D  G  B  A  H  E  I  C  F

PÓS-ORDEM: (E D R)

G  D  B  H  I  E  F  C  A