Aula 13 - Árvores - parte 2

Prévia do material em texto

Árvores 
SCC 202/502 – Algoritmos e Estruturas 
de Dados I 
Prof. Robson L. F. Cordeiro 
Material original editado: Prof. Thiago A. S. Pardo 
Árvores binárias 
n  Árvores com grau 2, ou seja, cada nó pode 
ter 2 filhos, no máximo 
A 
B C 
D E 
Raiz 
F 
Terminologia: 
•  filho esquerdo 
•  filho direito 
•  informação 
2 
Árvores binárias 
n  Declaração 
 
typedef char elem; 
 
typedef struct bloco { 
 elem info; 
 struct bloco *esq, *dir; 
} no; 
 
typedef struct { 
 no *raiz; 
} Arvore; 
3 
Árvores binárias 
n  Representação dinâmica e encadeada de 
uma árvore binária 
D 
A 
F B 
C G 
Raiz 
Raiz 
AB vazia 
4 
Árvores binárias 
n  Implementar o TAD árvore binária: dinâmico e encadeado 
n  Já fizemos em aula anterior 
n  Criar árvore 
n  Verificar se a árvore está vazia 
n  Buscar um elemento 
5 
Relembrando 
6 
void cria(Arvore *A) { 
 A->raiz=NULL; 
} 
int IsEmpty(Arvore *A) { 
 if (A->raiz==NULL) 
 return 1; 
 else return 0; 
} 
no* busca(no *p, elem *x) { 
 no *aux; 
 if (p==NULL) 
 return(NULL); 
 else if (p->info==*x) 
 return(p); 
 else { 
 aux=busca(p->esq,x); 
 if (aux==NULL) 
 aux=busca(p->dir,x); 
 return(aux); 
 } 
} 
Árvores binárias 
n  Implementar o TAD árvore binária: dinâmico e encadeado 
n  Buscar pai de um elemento 
n  Inserir elemento à esquerda de outro elemento 
n  Inserir elemento à direita de outro elemento 
n  Imprimir elementos da árvore 
n  Finalizar árvore 
n  Determinar altura da árvore 
7 
Árvores binárias 
n  Exercício 
n  Simulação da execução da função de cálculo de altura de 
uma árvore 
n  Considere uma árvore simples para simular a execução 
8 
Exercício para pensar em casa 
n  Em duplas 
n  Esquematize/desenhe/explique como seria a 
função de remoção de um elemento da árvore 
n  Implemente a função de remoção 
9