Baixe o app para aproveitar ainda mais
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); }
Compartilhar