Estrutura de Dados Exercicios

Nome:Erick Massayuki Aoki RGM:1504916-7

Nome:Erick Vinicius Souza da Silva RGM:153124-6

Nome:Felipe Oliveira Cruz RGM:1527272-9

Nome:Leonardo Akira Teixeira Dantas Kamimura RGM:1534560-2

E 7. Escreva a árvore abaixo na notação Newick e na forma de diagrama de inclusão.

[pic 1]

[pic 2]

[pic 3]

E 8. Codifique a representação da árvore abaixo na forma ligada, como feito nos slides para a árvore do exercício 1. Apresente o print da tela com a representação em string e o código.

[pic 4]

E 9. Considere a árvore abaixo para responder às questões

[pic 5]

a) Quais são os ancestrais de P?

M, K e Q

b) Quais são os descendentes de K?

M, P e N.

c) Qual o resultado da impressão por um percurso em em-ordem da árvore?

B, D, J, K, M, N, P, Q, R, T, W, Y

d) Qual o resultado da impressão de um percurso em pós-ordem da árvore?

B, J, N, P, D, M, K, R, W ,Y, T, Q

e) Qual o resultado da impressão de um percurso em pré-ordem da árvore?

Q, K, D, B, J, M, P, N, T, R, Y, W

f) Qual o resultado da impressão de um percurso em nível da árvore?

Q, K, T, D, M, R, Y, B, J, P, W, N

g) Faça a representação em termos de notação de Newick e de diagrama de inclusão para a árvore.

Q ( K (D,( B, J) M(P (N) )), T(R Y(W)))

h) Utilize o código da árvore de nó-N e codifique essa árvore.

Apresente o resultado da impressão.

[pic 6]

E 10. Deduza, através de um diagrama ou porventura de alguma maneira convincente, que o número total de nós n numa árvore binária cheia de altura h é n = 2h+1–1.

Por se tratar de uma árvore binária cheia, todos os nós terão duas sub-árvores associadas, exceto, as folhas. Sendo que todas as folhas estarão no mesmo nível.  Com o diagrama deduzimos a quantidade de nós numa árvore:

[pic 7]

Logo, podemos dizer que o número total de nós numa árvore binária cheia é de 2h+1 - 1 ou 2nivel - 1.

E11.Suponha que numa árvore binária cheia de altura h os filhos sejam enumerados nível a nível e que 0 seja o índice da raiz da árvore. Como na figura abaixo

[pic 8]

a) Qual o índice do nó mais à esquerda no nível k?

        Serão números impares

b) Qual o índice do nó mais à direita no nível k?

Sera um número par

c) Se um nó tem índice k, quais os índices de seus filhos esquerdo e direito?

        Serão índices um par e impar

d) Se um nó tem índice k, qual o índice de seu pai?

        Indice - 2.

e) Quantos nós existem no nível k?

        2k - 1.

E12.Baseado nas regras abaixo, monte a árvore de busca binária solicitada:

a) H é a raiz da árvore

[pic 9]

Inserindo H como raiz

b) N e J são sobrinhos de D

[pic 10]

Inserindo D

c) E e A são netos de H e filhos de D

[pic 11]

Inserindo A e E

d) M e Q são netos de L e bisnetos de H

[pic 12]

Inserindo L

[pic 13]

Inserindo J e N

[pic 14]

Inserindo M e Q

Responda também, justificando

e) é uma árvore binária completa?

É uma arvore binaria completa porque a altura dela é d, no caso, 3 e todos os filhos apresentam pelo menos 2 filhos.

f) é uma árvore estritamente binária?

        Sim pois todos os nós apresentam 2 filhos.

g) Qual o grau da árvore?

h=2, d=2, l=2, n=2, a=0, e=0, j=0, m=0, q=0

h) Qual a altura da árvore?

Altura 3; M e Q são os maiores níveis

E 13. Considere uma BST inicialmente vazia. Insira os elementos F,G,B,C,A,J,K,M,H,D. Em seguida, exclua a raiz da árvore e o elemento J.

a) Desenhe a árvore passo a passo até a inserção de D

[pic 15]

Inserido F como raiz

[pic 16]

Inserindo G

[pic 17]

Inserindo B

[pic 18]

Inserindo C

[pic 19]

Inserindo A

[pic 20]

Inserindo J

[pic 21]

Inserindo K

[pic 22]

Inserindo M

[pic 23]

Inserindo H

[pic 24]

Inserindo D

b) Desenhe a árvore após a remoção da raiz

[pic 25]

Antes da remoção de F

[pic 26]

Removendo F e “pegando” D como nova raiz

[pic 27]

D vira a nova raiz

c) Desenhe a árvore após a remoção de J

[pic 28]

J antes da remoção

[pic 29]

Remove-se J e “pega” H como novo Nó da raiz

[pic 30]

H assume o lugar de J

E14. Dada uma BST, inicialmente vazia, apresente as etapas de inserção até seu estado final após a inserção das 11 primeiras letras diferentes (da esquerda para a direita) do nome completo de um dos integrantes de seu grupo (se não possui 11 letras diferentes, use o nome de outro na sequência.Else, escolha uma sequência que complete as 11 letras). Repita o processo para todos os integrantes.