QUESTIONÁRIO 02 – ÁRVORES BINÁRIAS

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: Uma árvore binaria deve conter no máximo 2 filhos(nós), e nela possuem grau zero ou um.

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, isso acontece através da Formula: 2n – 1 = Numero máximo de elementos de uma árvore binária.

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 no meio das 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: Percurso por Extensão ou Largura: Os nós são visitados na ordem dos níveis da árvore, isto é: primeiramente são visitados os nós do nível 0, depois do nível 1, depois do nível 2 eassim por diante; os nós são visitados da esquerda para a direita em cada um dos níveis.



Ordem de Processamento: A B E C F G D H

Exercício do Slide

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

PRÉ-ORDEM (RED) – A B D G C E H I F 

IN/EM-ORDEM (ERD) – D G B A H E I C F

PÓS-ORDEM (EDR) – G D B H I E F C A