Questionário 03 - Árvores Binária de Busca

1- Uma Árvore binária e uma arvore onde cada nó tem no máximo 2 filhos . Uma árvore binária de busca é uma árvore e binária de onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raiz . Portanto explique como serão inseridos os elementos 10,20,15,18,30,40 e 13 numa árvore binária de busca.

R:

2 - Sabendo que podemos inserir elementos numa árvore binária e que isso é uma operação básica das árvores, indique e explique quais são as operações básicas de uma árvore binária?

R: Busca : A operação para buscar um elemento na árvore explora a propriedade de ordenação da árvore, tendo um desempenho computacional proporcional a sua altura (0(logn) para o caso de árvore balanceada.

Inserção: A operação de inserção adiciona um elemento na árvore na posição correta para que a propriedade fundamental seja mantida.

Remoção : Essa operação é um pouco mais complexa que a de inserção. Existe três situações possíveis . A primeira , e mais simples, é quando se deseja retirar um elemento que é folha da árvore . Neste caso , basta retirar o elemento da árvore e atualizar o pai, pois seu filho não existe mais.

3 - Sabendo que as árvores binárias podem ser cheias e completas e que uma árvore otimal é uma árvore completa que a operação de inserção segue a regra de inserção por ordem das chaves. Como as inserções sempre ocorrem à nível de folha, deve-se primeiro inserir as chaves que ficarão mais perto da raíz. Se temos um conjunto de chaves {c1,..,ci} tal que c1<...

R: 8,4,12,2,14,10,6

4- Uma das operações mais úteis das ABB é a localização, outra característica desse tipo de árvore são os chamados percursos que mostram os elementos que a árvore contém e que são classificados em pré-fixado/pré-ordem, pós-fixado/pós-ordem e in-ordem/em ordem. Explique como funciona o procedimento para realizar cada percurso considerando as subárvores. Existe alguma diferençacom relação às árvores binárias comuns?

R: Em pre ordem :

Visita a raiz;

Percorre sua subárvore esquerda, em pré-ordem;

Percorre sua subárvore direita, em pré-ordem;

Percurso em pré-ordem

In-ordem

• Percorrer sua subárvore esquerda, em in-ordem;

• Visitar a raiz;

• Percorrer sua subárvore direita, em in-ordem;

Pós-ordem

• Percorrer sua subárvore esquerda, em pós-ordem;

• Percorrer sua subárvore direita, em pós-ordem;

• Visitar a raiz;

QUESTIONÁRIO 2 - ÁRVORES BINÁRIAS + EXERCÍCIO DO SLIDE

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 : Árvore binária como o próprio nome sugere e um tipo especifico de estrutura na qual o numero máximo de filhos permitindo por nó e dois . Ou seja , um nó pode ter zero , um 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. 2ⁿ -1.

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

R: EM-Ordem/IN-Ordem

PRÉ-Ordem/PRÉ-fixado

PÓS-Ordem/PÓS-Fixado

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

R: 1- percorrer sua sub-árvore esquerda, em in-ordem

2- visitar a raiz

3- percorrer sua sub-árvore direita, em in-ordem

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

R:1- visitar a raiz

2- percorrer sua sub-árvore, em pré-ordem

3- percorrer sua sub-árvore, em pré-ordem

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

R: 1- percorrer sua sub-árvore esquerda em pós-ordem

2- percorrer sua sub-árvore direita em pós-ordem

3- visitar 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: Sim . 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.
------------------------------------------------------------------------------------------------------------------

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

R: Pré-ordem

ABDGCEHIF

In-ordem

OGBAHEICF

Pós-ordem

GBAHIEFCA