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.356 ]
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 - Listas Duplamente Encadeadas
Linguagem C - Funções Variádicas
Dicas para aprender programação
Guia de Programação em C/GTK 2 - Construindo uma Calculadora Completa
Análise dos Métodos de Ordenação usados em Algoritmos Computacionais
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)