Árvores Binárias de Busca

Prévia do material em texto

CURSO: Análise e desenvolvimento de sistemas 
POLO DE APOIO PRESENCIAL: Higienópolis 
SEMESTRE: 3° semestre 
COMPONENTE CURRICULAR / TEMA: BANCO DE DADOS 
NOME COMPLETO DO ALUNO: Flávio Morales 
TIA: 22504907 
NOME DO PROFESSOR: Thiago Donizetti dos Santos 
 
ESTRUTURA DE DADOS – AULA 7 
APLICANDO CONHECIMENTO 
 
1. Indique o percurso Em-ordem, Pré-ordem e Pós-ordem das árvores binárias abaixo: 
 
 
 
 
 
 
2. Desenhe a árvore binária de busca resultante da inserção dos seguintes valores: 
 
 
 
3. Escreva os percursos Em-ordem, Pré-ordem e Pós-ordem da árvore gerada no exercício anterior. 
 
4. Desenhe uma árvore binária de busca de altura = 5 com o menor número possível de nós que uma 
árvore binária de busca com altura = 5 pode ter (invente valores para os nós). 
 
5. Indique o percurso Em-ordem, Pré-ordem e Pós-ordem da árvore binária abaixo: 
A B C 
 
 
 
 
 
 
 
 
6. (a) Desenhe a árvore binária cuja travessia em ordem é DBEAFC e cuja travessia de pré-ordem é 
ABDECF. 
(b) Qual é o percurso pós-ordem desta árvore? 
7. Dada a árvore binária de busca abaixo, indique o resultado da exclusão da raiz (50), de acordo com as 
regras apresentadas no Texto de Apoio: 
 
 
 
 
Respostas: 
1- 
A - Em-ordem: 0010, 0020, 0030, 0040, 0050, 0060, 0070 
 Pré-ordem: 0040, 0020, 0010, 0030, 0060, 0050, 0070 
 Pós-ordem: 0010, 0030, 0020, 0050, 0070, 0060, 0040 
B - Em-ordem: 0010, 0020, 0030, 0040, 0050 
 Pré-ordem: 0030, 0020, 0010, 0040, 0050 
 Pós-ordem: 0010, 0020, 0050, 0040, 0030 
C - Em-ordem: 0010, 0020, 0030, 0040, 0050, 0060, 0070, 0080, 0090 
 Pré-ordem: 0050, 0030, 0020, 0010, 0040, 0080, 0060, 0070, 0090 
 Pós-ordem: 0010, 0020, 0040, 0030, 0070, 0060, 0090, 0080, 0050 
 
 
 
 
 
 
 
 
 
 
2 – 
 
3 – 
Em-ordem: 4, 5, 6, 8, 10, 11, 17, 19, 31, 43, 49 
Pré-ordem: 11, 6, 4, 5, 8, 10, 19, 17, 43, 31, 49 
Pós-ordem: 5, 4, 10, 8, 6, 17, 31, 49, 43, 19, 11 
 
4- 
 
5 – 
Em-ordem: 0015, 0018, 0027, 0042, 0046, 0050, 0052, 0059, 0063, 0069 
 Pré-ordem: 0042, 0015, 0027, 0018, 0059, 0046, 0052, 0050, 0063, 0069 
 Pós-ordem: 0018, 0027, 0015, 0050, 0052, 0046, 0069, 0063, 0059, 0042 
 
 
 
 
 
 
 
 
6- 
 
 
B - Pós-ordem: D, E, B, F, C, A. 
 
7 – 
Para identificar o primeiro sucessor à direita de 50, observe todos os descendentes de 50. Neste caso, à direita 
de 50, encontramos o número 80. Descendo à esquerda de 80, chegamos ao nó 60. Portanto, podemos 
concluir que o primeiro sucessor de 50 é 60. Agora, para efetuar a exclusão do sucessor encontrado da árvore, 
no caso o nó 60, verificamos se ele possui algum filho à direita, que no caso é o nó 70. Portanto, o nó 70 
assumirá a posição anteriormente ocupada pelo nó 60. Isso completa o Passo 3, que consiste em excluir o nó 
desejado (50) e substituí-lo pelo sucessor encontrado (60).