Árvores Binárias e Estruturas de Dados

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL 
INSTITUTO DE INFORMÁTICA 
Bacharelado em Ciência da Computação e 
Engenharia da Computação 
INF 01203 – Estruturas de Dados 
Árvores Binárias 
 
Nomes: ______________________________________________________________ 
 ______________________________________________________________ 
 ______________________________________________________________ 
 
1 - Converter a árvore apresentada a seguir em árvore binária. 
 
 
 
 
 
 
 
2 - Considerando a árvore binária resultante da solução do exercício anterior, execute as 
seguintes operações e desenhe a árvore resultante. 
• Inserir o nodo X como filho à direita de A 
• Inserir o nodo Y como filho à esquerda de X 
• Inserir o nodo Z como filho à direita de X 
• Inserir o nodo P como filho à esquerda de Z 
• Inserir o nodo Q como filho à direita de Z 
• Excluir o nodo O 
• Excluir o nodo M 
• Inserir o nodo R como filho à esquerda de L 
• Inserir o nodo S como filho à direita de L 
• Inserir o nodo V como filho à esquerda de C 
 
 
 
 
 
 
 
 
 
3 - Converter a árvore gerada no exercício anterior (2) para uma árvore n-ária equivalente. 
 
 
 
 
 
 
 
 
 
 
4 - Para a figura apresentada a seguir, qual a ordem de exibição dos nodos, 
considerando: 
 
 
a) Caminhamento por níveis (também conhecido como abrangência ou amplitude) 
 
________, ________, ________, ________, ________, ________, ________, ________ 
 
b) Caminhamento em profundidade 
 
________, ________, ________, ________, ________, ________, ________, ________ 
 
c) Caminhamento central à esquerda 
________, ________, ________, ________, ________, ________, ________, ________ 
 
d) Caminhamento central à direita 
 
________, ________, ________, ________, ________, ________, ________, ________ 
 
e) Caminhamento pré-fixado à esquerda 
 
________, ________, ________, ________, ________, ________, ________, ________ 
 
f) Caminhamento pré-fixado à direita 
 
________, ________, ________, ________, ________, ________, ________, ________ 
 
g) Caminhamento pós-fixado à esquerda 
 
________, ________, ________, ________, ________, ________, ________, ________ 
 
h) Caminhamento pós-fixado à direita 
 
________, ________, ________, ________, ________, ________, ________, ________ 
5 – Ache a raiz de cada uma das seguintes árvores binárias: 
a) Árvore com percurso pós-fixado a esquerda: F C B D G 
 Raiz: ___________ 
 
b) Árvore com percurso pré-fixado a esquerda I B C D F E N 
 Raiz: ___________ 
 
c) Árvore com percurso central esquerda (assuma que é uma árvore binária cheia): C B I 
D F G E 
 Raiz: ___________ 
 
6 – Responda. Para qual ordem de inserção dos elementos o caminhamento pré-fixado à 
esquerda se iguala ao caminhamento central à esquerda? 
 
 
 
 
 
7 – Considerando a estrutura de dados apresentada abaixo, explique resumidamente o que faz o 
trecho de código apresentado a seguir: 
 
 
 
 
 
struct TNodoA{ 
 char info; 
 struct TNodoA *esq; 
 struct TNodoA *dir; 
}; 
 
typedef struct TNodoA pNodoA; 
int OQueSeraE(pNodoA *a) 
{ 
 int Calc_Esq, Calc_Dir; 
 if (a == NULL) 
 return 0; 
 else 
 { 
 Calc_Esq = OQueSeraE(a->esq); 
 Calc_Dir = OQueSeraE(a->dir); 
 if (Calc _Esq > Calc_Dir) 
 return (1 + Calc_Esq); 
 else 
 return (1 + Calc_Dir); 
 } 
}