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: 50.398 ]
Por: Enzo de Brito Ferber em 07/05/2015 | Blog: http://www.maximasonorizacao.com.br
Inserir(elemento) { Se (elemento <= raiz) Inserir (arvore esquerda) Senão Inserir (arquivo direita) }
typedef struct folha* Folha; struct folha { int info; Folha esquerda; Folha direita; };
/* @ 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 arvore = NULL; arvore = inserir(arvore, 4); ... // as chamadas subsequentes a inserir serão: inserir (arvore, 4);
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) malloc (sizeof(struct 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); return raiz;
raiz->direita = inserir (raiz->direita, info);
raiz->esquerda = inserir (raiz->esquerda, info);
Linguagem C - Funções Variádicas
Linguagem C - Listas Duplamente Encadeadas
Guia de Programação em C/GTK 2 - Construindo uma Calculadora Completa
Análise dos Métodos de Ordenação usados em Algoritmos Computacionais
Atenção a quem posta conteúdo de dicas, scripts e tal (1)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
Erro ao converter string para inteiro (6)
Diferença entre formas de instalar o Samba [RESOLVIDO] (4)
Dongle Bluetooth 5.0 não funciona no Pop Os 22.04 (0)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (24)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba