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.
Nenhum comentário:
Postar um comentário