Árvores Binárias

Links relacionados: DAS5102 Fundamentos da Estrutura da Informação

Conteúdo

• Conteúdo Abdala
• Apresentação

Arquivo arvore.c

 1#include "stdlib.h"
 2#include "arvore.h"
 3
 4typedef struct no No;
 5
 6struct no
 7{
 8    int conteudo;
 9    No* pai;
10    No* filhoEsquerda;
11    No* filhoDireita;
12};
13
14struct arvore
15{
16    No* raiz;
17    int tamanho;
18};
19
20Arvore* arvore_criar()
21{
22    Arvore *a = (Arvore*) malloc(sizeof(Arvore));
23    a->raiz = NULL;
24    a->tamanho = 0;
25    return a;
26}
27
28No* no_criar(int valor)
29{
30    No* no = (No*) malloc(sizeof(No));
31    no->conteudo = valor;
32    no->pai = NULL;
33    no->filhoEsquerda = NULL;
34    no->filhoDireita = NULL;
35    return no;
36}
37
38int arvore_recursivo(Arvore* a, No* local, No* novo)
39{
40    if (novo->conteudo == local->conteudo)
41    {
42        free(novo);
43        return 1;
44    }
45    if (novo->conteudo < local->conteudo)
46    {
47        if (local->filhoEsquerda == NULL)
48        {
49            local->filhoEsquerda = novo;
50            return 0;
51        }
52        return arvore_recursivo(a, local->filhoEsquerda, novo);
53    }
54    if (local->filhoDireita == NULL)
55    {
56        local->filhoDireita = novo;
57        return 0;
58    }
59    return arvore_recursivo(a, local->filhoDireita, novo);
60}
61
62int arvore_eh_repetido(Arvore* a, int valor)
63{
64    No* no = no_criar(valor);
65    if (a->raiz == NULL)
66    {
67        a->raiz = no;
68        a->tamanho++;
69        return 0;
70    }
71    return arvore_recursivo(a, a->raiz, no);
72}

Arquivo arvore.h

1#ifndef ARVORE_H_INCLUDED
2#define ARVORE_H_INCLUDED
3
4typedef struct arvore Arvore;
5
6Arvore* arvore_criar();
7int arvore_eh_repetido(Arvore* a, int valor);
8
9#endif // ARVORE_H_INCLUDED

Arquivo main.c

 1#include <stdio.h>
 2#include <stdlib.h>
 3#include "arvore.h"
 4
 5int main()
 6{
 7    int i;
 8    int vet[9] = { 4, 3, 6, 5, 4, 9, 9, 1, 2};
 9    Arvore* arvore = arvore_criar();
10
11    for (i = 0; i < 9; i++)
12    {
13        int repetido = arvore_eh_repetido(arvore, vet[i]);
14        if (repetido)
15        {
16            printf("%d eh repetido\n", vet[i]);
17        }
18        else
19        {
20            printf("%d nao eh repetido\n", vet[i]);
21        }
22    }
23    return 0;
24}

Roteiro

Objetivos

• Fixar o conceito de árvores binárias via exercícios práticos;
• Exercitar a descrição da funcionalidade de funções;

Atividade

1. Baseado no exemplo, tente refazer a função sem utilizar recursividade. Faça uma função para navegar na árvore e outra para apagar os nós sem recursividade.

2. Crie uma TAD que implemente uma árvore binária com as seguintes características:

• A árvore deve ser dinâmica;
• Os nós devem ser alocados de maneira dinâmica (usando malloc);
• Programe a estrutura de dados necessária para a implementação da árvore binária (visto em sala de aula);
• Escreva uma função para a criação da TAD árvore binária;
• Implemente a seguinte interface para esta TAD:

 1#ifndef ARVORE_H
 2#define ARVORE_H
 3
 4Arvore* arvore_criar();
 5void arvore_destruir(Arvore *a)
 6void arvore_inserir_esquerda(Arvore *a, int info);
 7void arvore_inserir_direita(Arvore *a, int info);
 8No *arvore_remover_esquerda(Arvore *a);
 9No *arvore_remover_direita(Arvore *a,
10arvore *arvore_merge(Arvore *esquerda, arvore *direita);
11int arvore_tamanho(Arvore *a);
12No *arvore_raiz(Arvore *a);
13Arvore *arvore_esquerda(Arvore *a);
14Arvore *arvore_direita(Arvore *a);
15
16#endif /* ARVORE_H */

• No início de cada função, inclua um comentário descrevendo o que cada uma das funções acima deve fazer. Utilize o bom senso, discuta com os colegas de equipe e então valide com o professor de lab. o que cada uma das funções deve fazer.