Buscar

AEDSII_aula_014_arvores

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 61 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 61 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 61 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

¡  Organizam	
  dados	
  de	
  forma	
  hierárquica	
  
¡  Acontecem	
  com	
  frequência	
  na	
  natureza	
  
¡  Fáceis	
  de	
  representar	
  e	
  manipular	
  com	
  
computadores	
  
¡  Úteis	
  para	
  várias	
  tarefas	
  
Raiz	
  
Folhas	
  
Nós	
  internos	
  
Filhos	
  
Pai	
  
Descendentes	
  
Ancestrais	
  
Irmãos	
  
Níveis	
   0 
1 
2 
3 
4 
Caminho	
  
¡  Árvores	
  não	
  contêm	
  ciclos	
  
§  Só	
  existe	
  um	
  caminho	
  entre	
  qualquer	
  par	
  de	
  nós	
  
¡  Qualquer	
  árvore	
  pode	
  ser	
  transformada	
  
numa	
  árvore	
  binária	
  
§  Focaremos	
  em	
  árvores	
  binárias	
  pois	
  elas	
  são	
  mais	
  
fáceis	
  de	
  armazenar	
  e	
  manipular	
  
¡  Uma	
  árvore	
  binária	
  é	
  uma	
  árvore	
  com	
  zero,	
  
um	
  ou	
  dois	
  filhos	
  onde	
  cada	
  filho	
  é	
  também	
  
uma	
  árvore	
  binária	
  
§  Definição	
  é	
  recursiva	
  
§  Veremos	
  que	
  manipulação	
  de	
  árvores	
  é	
  fácil	
  
usando	
  recursão	
  
struct arvore { 
 struct arvore *esq; 
 struct arvore *dir; 
 int dado; 
}; 
¡  Pré-­‐ordem	
  
	
  
¡  Ordem	
  central	
  
	
  
¡  Pós-­‐ordem	
  
3 2 
1 
3 1 
2 
2 1 
3 
void pre_ordem(struct arvore *f) { 
 if(f == NULL) { 
 return; 
 } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 2 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 2 4 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 1 2 4 7 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 2 4 7 A 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 2 4 7 A B 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 2 4 7 A B 3 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
1 2 4 7 A B 3 5 6 8 C 9 
void pre_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 printf(“%d”, f->dado); 
 pre_ordem(f->esq); 
 pre_ordem(f->dir); 
} 
void ordem_central(struct arvore *f) 
{ 
 if(f == NULL) { return; } 
 ordem_central(f->esq); 
 printf(“%d”, f->dado); 
 ordem_central(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
A 
void ordem_central(struct arvore *f){ 
 if(f == NULL) { return; } 
 ordem_central(f->esq); 
 printf(“%d”, f->dado); 
 ordem_central(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
A 7 
void ordem_central(struct arvore *f){ 
 if(f == NULL) { return; } 
 ordem_central(f->esq); 
 printf(“%d”, f->dado); 
 ordem_central(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
A 7 B 
void ordem_central(struct arvore *f){ 
 if(f == NULL) { return; } 
 ordem_central(f->esq); 
 printf(“%d”, f->dado); 
 ordem_central(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
A 7 B 4 
void ordem_central(struct arvore *f){ 
 if(f == NULL) { return; } 
 ordem_central(f->esq); 
 printf(“%d”, f->dado); 
 ordem_central(f->dir); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
A 7 B 4 2 1 5 3 C 8 6 9 
void ordem_central(struct arvore *f){ 
 if(f == NULL) { return; } 
 ordem_central(f->esq); 
 printf(“%d”, f->dado); 
 ordem_central(f->dir); 
} 
 
void pos_ordem(struct arvore *f) 
{ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
A 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
3 2 
1 
4 6 
7 8 9 
A B C
5 
2 
1 
4 
7 
A
A B 
3 2 
1 
4 6 
7 8 
A B C
5 
9 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
A B 7 
3 2 
1 
4 6 
7 8 
A B C
5 
9 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
A B 7 4 
3 2 
1 
4 6 
7 8 
A B C
5 
9 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
A B 7 4 2 
3 2 
1 
4 6 
7 8 
A B C
5 
9 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
A B 7 4 2 5 
3 2 
1 
4 6 
7 8 
A B C
5 
9 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
A B 7 4 2 5 C 
3 2 
1 
4 6 
7 8 
A B C
5 
9 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
A B 7 4 2 5 C 8 9 6 3 1 
3 2 
1 
4 6 
7 8 
A B C
5 
9 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
5 9 8 + 4 6 * * 7 + * 
+5 
*
7 
+ *
9 8 4 
*
6 
void pos_ordem(struct arvore *f){ 
 if(f == NULL) { return; } 
 pos_ordem(f->esq); 
 pos_ordem(f->dir); 
 printf(“%d”, f->dado); 
} 
¡  Até	
  agora	
  consideramos	
  árvores	
  que	
  organizam	
  os	
  dados	
  em	
  
forma	
  hierárquica	
  sem	
  inspecionar	
  os	
  elementos	
  
¡  Árvores	
  de	
  busca	
  mantém	
  uma	
  ordem	
  entre	
  seus	
  elementos	
  
§  Raiz	
  é	
  maior	
  que	
  os	
  elementos	
  na	
  árvore	
  à	
  esquerda	
  
§  Raiz	
  é	
  menor	
  que	
  os	
  elementos	
  na	
  árvore	
  à	
  direita	
  
8 5 
6 
4 B
2 A C
1 3 9 
7 
0 
struct arvore { 
 struct arvore *esq; 
 struct arvore *dir; 
 int dado; 
}; 
 
struct arvore * cria_arvore(void) { 
 struct arvore *novo; 
 novo = malloc(sizeof(struct arvore)); 
 novo->esq = NULL; 
 novo->dir = NULL; 
 novo->dado = 0; 
} 
struct arvore *busca_elemento(struct arvore *t, int D) { 
 if(t == NULL) /* elemento não existente na árvore */ 
 return NULL; 
 else if (D == t->dado)/* encontrou elemento */ 
 return t; 
 else if (D < t->dado) /* busca na árvore esquerda */ 
 return busca_elemento(t->esq, D); 
 else if (D > t->dado) /* busca na árvore direita */ 
 return busca_elemento(t->dir, D); 
} 
 
void acha_menor(arvore *t) { 
 if(t->esq == NULL) { 
 return t; 
 } 
 return acha_menor(t->esq); 
} 
¡  O	
  elemento	
  vai	
  ser	
  inserido	
  como	
  uma	
  folha	
  
da	
  árvore	
  de	
  busca	
  
¡  Vamos	
  procurar	
  o	
  lugar	
  de	
  inserção	
  
navegando	
  da	
  raiz	
  até	
  a	
  folha	
  onde	
  ele	
  será	
  
inserido	
  
8 5 
6 
4 B
2 A C
1 3 9 
7 
4.5 
8 5 
6 
4 B
2 A C
1 3 9 
7 
4.5 
8 5 
6 
4 B
2 A C
1 3 9 
7 4.5 
8 5 
6 
4 B
2 A C
1 3 9 
7 
4.5 
void insere_elemento(struct arvore *t, int D) { 
 if(D < t->dado) { 
 if(t->esq) { insere_elemento(t->esq, D); } 
 else { /* achou local de inserção */ 
 struct arvore *novo = cria_arvore(); 
 novo->dado = D; 
 t->esq = novo; 
 } 
 } else if(D > t->dado) { 
 if(t->dir) { insere_elemento(t->dir, D); } 
 else { 
 struct arvore *novo = cria_arvore(); 
 novo->dado = D; 
 t->dir = novo; 
 } 
 } else { 
 printf(“elemento já existe na árvore\n”); 
 } 
} 
¡  Remover	
  folhas	
  
¡  Remover	
  nós	
  com	
  um	
  filho	
  
¡  Remover	
  nós	
  com	
  
dois	
  filhos	
  
8 5 
6 
4 B
2 A C
1 3 9 
7 
8 5 
6 
4 B
2 A C
1 3 9 
7 
8 5 
6 
B2 
A C1 3 
9 
7 
8 5 
6 
4 B
2 A C
1 3 9 
7 
sucessor 
8 5 
7 
4 B
2 A C
1 3 9 
7 
8 5 
7 
4 B
2 A C
1 3 9 
7 
struct arvore *remove(struct arvore *t, int D) { 
struct arvore *aux; 
 if(t == NULL) { printf(“elemento ausente\n”); } 
 else if(D < t->dado){ t->esq = remove(t->esq, D);} 
 else if(D > t->dado){ t->dir = remove(t->dir, D);} 
 else if(t->esq == NULL && t->dir == NULL) { 
 free(t); return NULL; /* zero filhos */ 
 } 
 else if(t->esq == NULL) { 
 aux = t->dir; free(t); return aux; /* 1 filho */ 
 } 
 else if(t->dir == NULL) { 
 aux = t->esq; free(t); return aux; /* 1 filho */ 
 } else { /* 2 filhos */ 
 struct arvore *suc = acha_menor(t->dir); 
 t->dado = suc->dado; 
 t->dir = remove(t->dir, suc->dado); 
 return t; 
 } 
 return t; 
} 
 
void acha_menor(arvore *t) { 
 if(t->esq == NULL) { 
 return t; 
 } 
 return acha_menor(t->esq); 
}

Outros materiais