Linguagem C - Árvores Binárias
Neste artigo, falarei sobre o que é e como implementar uma estrutura de dados chamada Árvore Binária. Com tempos de pesquisa, inserção e remoção expressivamente melhores que de listas encadeadas, esta estrutura é usada principalmente em bancos de dados e sistemas de arquivos.
[ Hits: 51.357 ]
Por: Enzo de Brito Ferber em 07/05/2015 | Blog: http://www.maximasonorizacao.com.br
/* arvore.c * * Linguagem C - Árvores Binárias * Viva O Linux * * Enzo Ferber * 2015 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #define FOLHA (Folha)malloc(sizeof(struct folha)) #define CMDSTR 500 typedef struct folha* Folha; struct folha { int info; Folha esquerda; Folha direita; }; Folha inserir (Folha, int), deletar (Folha, int), procurar (Folha, int); void imprimir_arvore (Folha, int); void ordenada(Folha), preordenada(Folha), posordenada(Folha); void cmd (void), help (void); /* @ Folha inserir (Folha raiz, int info) * * Argumentos * ---------- * raiz ponteiro para 'struct folha', estrutura de dado básica para * construção da árvore * info nova informação a ser inserida * * Retorno * ------- * NULL em caso de erro * Folha em caso de sucesso (nó 'raiz') */ Folha inserir (Folha raiz, int info) { if (!raiz) { /* significa que o ponteiro é nulo, e que está é a posição * para inserção. * * 1. Alocar e checar memória */ if (!(raiz = FOLHA)) { perror("inserir:malloc()"); return NULL; } /* 2. Cópia da Informação * 3. Ponteiros de referência * 4. Retorno da nova folha */ raiz->info = info; raiz->esquerda = raiz->direita = NULL; return raiz; } else if (info > raiz->info) raiz->direita = inserir (raiz->direita, info); else raiz->esquerda = inserir (raiz->esquerda, info); /* retorna o ponteiro raiz * * Isso é necessário pois a função inserir é recursiva, e seu retorno * é sempre atribuido ao mesmo ponteiro passado como argumento 'raiz', * * raiz->esquerda = inserir(raiz->esquerda,info) * raiz->direita = inserir(raiz->direta, info) */ return raiz; } /* @ Folha deletar (Folha raiz, int info) * * Argumentos * ---------- * raiz raiz principal da arvore * info informação procurada para deletar * * Retorno * ------- * raiz em ambos os casos */ Folha deletar (Folha raiz, int info) { /* para deletar um nó, é necessário que esse nó exista. * Então, vamos procurar pelo nó. * * A remoção de folhas em uma árvore é um pouco mais detalhada que sua * similar para listas encadeadas. * * Existem alguns pontos a se considerar para remover uma folha: * 1. A folha é também uma raiz (contém subárvores)? * 2. */ Folha filho, n_raiz; /* se chegou ao final da arvore e nao encontrou nada para deletar.... */ if (!raiz) return NULL; /* primeira comparação do programa: * Achamos a informação procurada? */ if (raiz->info == info) { /* 1. Existe uma raiz direita? * (uma raiz direita contém todos os elementos MAIORES que * a raiz que estamos excluindo). * * 2. Caso ela exista, ela será a nova raiz. * 3. Os atuais elementos *menores* deverão ser anexados nos * menores elementos da nova raiz (segundo passo). */ if (raiz->direita) { /* 2. a nova raiz é a subárvore da direita, que contem * todos os elementos MAIORES que a raiz a ser removida */ n_raiz = filho = raiz->direita; /* 3. a subárvore esquerda da nova raíz é percorrida * até onde não houverem mais elementos. Isso nos dará * o menor elemento maior que a folha esquerda de nossa * raiz a ser removida. */ while(filho->esquerda) filho = filho->esquerda; /* o menor elemento maior que a raiz * torna-se * raiz de todos os elementos menores que a raiz * removida */ filho->esquerda = raiz->esquerda; /* libera a memória do ponteiro */ free (raiz); /* 1 + 2: nova raiz */ return n_raiz; } else { /* caso não haja uma raiz direita (elementos MAIORES) * que nossa raiz, a nova raiz da árvore seja o único * elemento restante: a subárvore esquerda da árvore, * ou os antigos elementos menores que a raiz removida. */ n_raiz = raiz->esquerda; /* libera a memória do ponteiro */ free (raiz); /* retorno da nova raiz */ return n_raiz; } } else if (info > raiz->info) { /* Caso a informação procurada seja maior que a informação na * raiz, devemos então procurar pela informação na subárvore * da direita (esta operação deverá ser congruente em todo o * seu programa. * * Você não pode ordenar a inserção de um jeito e a remoção de * outro! */ raiz->direita = deletar(raiz->direita, info); } else { /* Caso a informação seja menor que a raiz, procuraremos por ela * nas subárvores da esquerda. */ raiz->esquerda = deletar(raiz->esquerda, info); } /* Lembre-se que as árvores binárias são estruturas de dados recursivas, * e por esse motivo, é sempre bom saber o que se está retornando. * * Assim como na função de inserção, as chamadas recursivas à deletar() * esperam como retorno uma raíz! Para onde a raiz->esquerda vai * apontar quando a função retornar? * * 1. Se ela não for excluida, vai ser a própria raiz->esquerda * 2. Caso seja excluída, será determinada pelo algoritmo no bloco * if(raiz->info == info). * * Aqui, no final do escopo da função, significa que é um retorno de * chamadas recursivas à deletar (já que o bloco raiz->info == info) * retorna por si só. Já que este é um retorno das chamadas recursivas, * deve retornar a raiz na qual foi chamada. */ return raiz; } Folha procurar (Folha raiz, int info) { /* como todas as funções relativas a arvores binárias são recursivas, * todas necessitam de um parametro de "parada de recursão", então, * sempre que acharmos um nó NULO, retornamos (até porque não dá pra * imprimir informações de um nó que não existe. */ if (!raiz) return NULL; if (info > raiz->info) return procurar(raiz->direita, info); else return procurar (raiz->esquerda, info); /* falhas, compilação, etc */ return NULL; } void imprimir_arvore (Folha raiz, int level) { register int i; /* como todas as funções relativas a arvores binárias são recursivas, * todas necessitam de um parametro de "parada de recursão", então, * sempre que acharmos um nó NULO, retornamos (até porque não dá pra * imprimir informações de um nó que não existe. */ if (!raiz) return ; /* essa função é uma derivação da ordenação 'inorder', onde primeiro * a arvore é percorrida até seu elemento mais esquerdo, e então é * impressa a informação da raiz, e então é percorrida suas subárvores * direitas. * * para imprimir de forma 'didática', essa função viaja primeiro pelas * folhas direitas, imprime a raiz e então percorre as subárvores * esquerdas. */ imprimir_arvore (raiz->direita, level + 1); for (i = 0; i < level * 2; i++ ) putchar(' '); printf("%d ", raiz->info); imprimir_arvore (raiz->esquerda, level + 1); } /* @ void ordenada (Folha raiz) * * Transversalização Ordenada * -------------------------- * Primeiro é visitada a subárvore esquerda, depois a raiz e por último a * subárvore direita. */ void ordenada (Folha raiz) { if (!raiz) return ; ordenada (raiz->esquerda); printf ("%d ", raiz->info); ordenada (raiz->direita); } /* @ void preordenada (Folha raiz) * * Transversalização Pré-Ordenada * ------------------------------ * Primeiro é visitada a raiz, depois a subárvore esquerda e por último a * subárvore direita. */ void preordenada (Folha raiz) { if (!raiz) return ; printf ("%d ", raiz->info); preordenada (raiz->esquerda); preordenada (raiz->direita); } /* @ void posordenada (Folha raiz) * * Transversalização Pós-Ordenada * ------------------------------ * Primeiro é visitada a subárvore esquerda, depois a subárvore direita e por * último a raiz. */ void posordenada (Folha raiz) { if (!raiz) return; posordenada (raiz->esquerda); posordenada (raiz->direita); printf ("%d ", raiz->info); } /****************************************************************************** * Aqui termina todo o código relacionado às árvores binárias e começa o código * relative à interface. * */ void cmd (void) { char cmd[CMDSTR], *arg; Folha raiz = NULL; help(); while (1) { printf ("ArvoreBinaria> "); fgets (cmd, CMDSTR, stdin); if (!cmd) continue; switch (*cmd) { case 'i': arg = &cmd[2]; arg = strtok(arg, " "); while (arg) { if (!raiz) raiz = inserir (raiz, atoi(arg)); else inserir (raiz, atoi(arg)); arg = strtok (NULL, " "); } break; case 'd': arg = &cmd[2]; arg = strtok(arg, " "); while (arg) { raiz = deletar (raiz, atoi(arg)); arg = strtok (NULL, " "); } break; case 'm': imprimir_arvore (raiz, 0); break; case 'o': ordenada(raiz); puts(""); break; case 'r': preordenada(raiz); puts(""); break; case 'p': posordenada(raiz); puts(""); break; case 's': exit(0); case 'h': help(); break; default: printf("Comando nao reconhecido. "); break; } memset (cmd, 0x0, CMDSTR); } } /* @ void help (void) * * i 20 vai inserir o elemento 20 na árvore * d 20 vai remover o elemento 20 da árvore * m vai mostrar a árvore na tela * o transversalização ordenada * r transversalização pré-ordenada * p transversalização pós-ordenada * s sai do programa * h mostra a ajuda */ void help (void) { printf (" | Arvores Binarias "); printf (" | Implementacao em C para o Viva O Linux "); printf (" | "); printf (" | Autor: Enzo Ferber "); printf (" | 2015 "); printf (" | "); printf (" Lista de comandos "); printf (" ----------------- "); printf (" i %%d - Inserir um elemento "); printf (" d %%d - Deletar um elemento "); printf (" m - Mostrar a arvore lateralmente "); printf (" o - Transversalizacao Ordenada "); printf (" r - Transversalizacao Pre-Ordenada "); printf (" p - Transversalizacao Pos-Ordenada "); printf (" s - Sair do programa "); printf (" h - Mostra a ajuda "); } int main (void) { cmd (); return 0; }
Linguagem C - Funções Variádicas
Linguagem C - Listas Duplamente Encadeadas
Guia de Programação em C/GTK 2 - Construindo uma Calculadora Completa
Linguagem C - Listas Duplamente Encadeadas
Dicas para aprender programação
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (15)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)
Pendrive não formata de jeito nenhum (4)