08 - Percurso em Árvores

Prévia do material em texto

Estruturas de Dados
Aula 08. Percurso em Árvores
Karina Mochetti
2018.1
Karina Mochetti Aula 08. Percurso em Árvores
Relembrando...
Árvores
Raiz e Folha
Árvore Binária
Registro de Árvore em C
Número de nós e altura
Karina Mochetti Aula 08. Percurso em Árvores
Relembrando...
Árvores
Raiz e Folha
Árvore Binária
Registro de Árvore em C
Número de nós e altura
Karina Mochetti Aula 08. Percurso em Árvores
Relembrando...
Árvores
Raiz e Folha
Árvore Binária
Registro de Árvore em C
Número de nós e altura
Karina Mochetti Aula 08. Percurso em Árvores
Relembrando...
Árvores
Raiz e Folha
Árvore Binária
Registro de Árvore em C
Número de nós e altura
Karina Mochetti Aula 08. Percurso em Árvores
Relembrando...
Árvores
Raiz e Folha
Árvore Binária
Registro de Árvore em C
Número de nós e altura
Karina Mochetti Aula 08. Percurso em Árvores
Exercício Aula Passada
Faça um programa que, dado dois nós x e y de uma árvore binária,
retorna 0 se x é pai de y, 1 se y é pai de x e -1 se eles não
relacionados.
int TreeRelation(No* x, No* y) {
if (x != NULL && (x->esq == y || x->dir == y))
return 0;
else if (y != NULL && (y->esq == x || y->dir == x))
return 1;
else
return -1;
}
Karina Mochetti Aula 08. Percurso em Árvores
Árvores
Uma árvore é uma representação de dados de forma hierárquica.
Karina Mochetti Aula 08. Percurso em Árvores
Árvore Binária
Uma Árvore Binária T é um conjunto finito de nós tal que:
T é vazia;
T consiste de um nó raiz e duas subárvores binárias Te e Td.
Karina Mochetti Aula 08. Percurso em Árvores
Árvore Binária
typedef struct no {
int info;
struct no *esq;
struct no *dir;
} No;
typedef No* ArvoreBin;
Karina Mochetti Aula 08. Percurso em Árvores
Percurso
Um percurso é uma operação que percorre cada elemento da árvore
somente uma vez, gerando uma ordenação.
Como árvores binárias são uma estrutura não linear, o percurso
nelas exige um algoritmo mais complexo.
A estrutura recursiva de uma árvore favorece para algoritmos
de percursos recursivos.
Na recursão de uma árvore o caso base sempre será ou a
árvore vazia, ou a árvore trivial.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
void PreOrdem (No* n) {
if (n != NULL) {
printf("%d", n->info);
PreOrdem(n->esq);
PreOrdem(n->dir);
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pré-Ordem
O percurso pré-ordem sempre visita a raiz antes de visitar os filhos.
void PreOrdem (No* n) {
if (n != NULL) {
printf("%d", n->info);
PreOrdem(n->esq);
PreOrdem(n->dir);
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
void PosOrdem (No* n) {
if (n != NULL) {
PosOrdem(n->esq);
PosOrdem(n->dir);
printf("%d", n->info);
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Percurso Pós-Ordem
O percurso pós-ordem sempre visita os filhos antes de visitar a raiz.
void PosOrdem (No* n) {
if (n != NULL) {
PosOrdem(n->esq);
PosOrdem(n->dir);
printf("%d", n->info);
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina MochettiAula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
void InOrdem (No* n) {
if (n != NULL) {
InOrdem(n->esq);
printf("%d", n->info);
InOrdem(n->dir);
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Percurso In-Ordem
O percurso in-ordem sempre visita o filhos esquerdo antes da raiz e
o filho direito depois da raiz.
void InOrdem (No* n) {
if (n != NULL) {
InOrdem(n->esq);
printf("%d", n->info);
InOrdem(n->dir);
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
void Largura (No *n) {
Fila f = InicializaFila();
Push(f, n);
while (!FilaVazia(f)) {
No *p = Pop(f);
if (p != NULL) {
printf("%d", p->info);
Push(f, p->esq);
Push(f, p->dir);
}
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Percurso em Largura
Realiza o percurso através dos níveis da árvore.
void Largura (No *n) {
Fila f = InicializaFila();
Push(f, n);
while (!FilaVazia(f)) {
No *p = Pop(f);
if (p != NULL) {
printf("%d", p->info);
Push(f, p->esq);
Push(f, p->dir);
}
}
return;
}
Complexidade
O(n)
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08.Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética
Uma árvore binária pode representar uma expressão aritmética,
onde toda folha possui um valor e cada nó realiza uma operação
entre seus filhos.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética In-Ordem
A notação infixa é a mais comum utilizada e precisa de
parênteses para determinar a ordem dos operadores.
É utilizada em linguagens de programação e calculadoras
comuns.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética Pré-Ordem
A notação préfixa ou polonesa é muito útil, pois determina a
ordem das operações sem a necessidade de parênteses
Foi criada em 1920 pelo matemático polonês Jan Lukasiewicz.
Karina Mochetti Aula 08. Percurso em Árvores
Exemplo: Árvore de Expressão Aritmética Pós-Ordem
A notação pósfixa ou polonesa necessita de zero de memória
para realizar o cálculo, além de não precisar de parênteses.
Foi popularizada pela HP que a utiliza nas suas calculadoras.
Karina Mochetti Aula 08. Percurso em Árvores
Exercício
Modifique os percursos adicionando a operação raiz quadrada à
árvore de expressão aritmética. Quais as principais diferenças entre
a árvore antiga e a nova?
Karina Mochetti Aula 08. Percurso em Árvores