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.523 ]
Por: Enzo de Brito Ferber em 07/05/2015 | Blog: http://www.maximasonorizacao.com.br
Pesquisa
De todas as operações que podem ser feitas em uma árvore, a pesquisa é a mais simples. O código abaixo:
O código, além de muito simples, é auto-explicativo. Nosso teste de parada de recursão é o mesmo de sempre: if(!raiz). Vale ressaltar que para essa função, se a recursão chegar a um ponto onde o argumento raiz é NULL, significa que o elemento não existe na árvore.
O método de tomada de decisão para pesquisa segue o algoritmo de inserção. Como o algoritmo já foi explicado na seção anterior, não explicarei os detalhes aqui.
Essa é a função de pesquisa. E muito eficiente, por sinal!
Folha procurar (Folha raiz, int info)
{
/* Parada de Recursão
*
* elemento não encontrado!
*/
if (!raiz) return NULL;
if (info > raiz->info) return procurar(raiz->direita, info);
else return procurar (raiz->esquerda, info);
return NULL;
}
O código, além de muito simples, é auto-explicativo. Nosso teste de parada de recursão é o mesmo de sempre: if(!raiz). Vale ressaltar que para essa função, se a recursão chegar a um ponto onde o argumento raiz é NULL, significa que o elemento não existe na árvore.
O método de tomada de decisão para pesquisa segue o algoritmo de inserção. Como o algoritmo já foi explicado na seção anterior, não explicarei os detalhes aqui.
Essa é a função de pesquisa. E muito eficiente, por sinal!
Páginas do artigo
1. Introdução2. Recursividade
3. Inserção
4. Pesquisa
5. Remoção
6. Transversalização
7. Conclusão
8. Código Completo e Comentado
Outros artigos deste autor
Linguagem C - Listas Duplamente Encadeadas
Linguagem C - Funções Variádicas
Leitura recomendada
Linguagem C - Listas Duplamente Encadeadas
Guia de Programação em C/GTK 2 - Construindo uma Calculadora Completa
Comentários
[1] Comentário enviado por fabio em 07/05/2015 - 12:10h
Parabéns pelo trabalho, dissertação completa sobre o assunto.
Parabéns pelo trabalho, dissertação completa sobre o assunto.
[4] Comentário enviado por pmargreff em 09/05/2015 - 21:09h
Primeiramente, parabéns pelo artigo.
Segundo, gostaria de saber que programa utilizou para fazer as imagens. Abraço.
Primeiramente, parabéns pelo artigo.
Segundo, gostaria de saber que programa utilizou para fazer as imagens. Abraço.
[5] Comentário enviado por EnzoFerber em 11/05/2015 - 08:44h
[4] Comentário enviado por pablomrg em 09/05/2015 - 21:09h
Primeiramente, parabéns pelo artigo.
Segundo, gostaria de saber que programa utilizou para fazer as imagens. Abraço.
Bom dia.
Para as imagens usei o primo rico do GIMP! Filho da Adobe!
[]'s
[4] Comentário enviado por pablomrg em 09/05/2015 - 21:09h
Primeiramente, parabéns pelo artigo.
Segundo, gostaria de saber que programa utilizou para fazer as imagens. Abraço.
Bom dia.
Para as imagens usei o primo rico do GIMP! Filho da Adobe!
[]'s
[6] Comentário enviado por dianaluz92 em 12/05/2015 - 15:08h
Parabéns pelo trabalho, a parte conceitual está muito clara da para a estrutura da arvore, mas eu queria tirar um duvida se for possível, como inserir um conjunto de elementos na árvore no caso quando o campo info é um ponteiro que deverá receber elemento tipo inteiro,float e um ponteiro char para nome.
Desde já grata,
Parabéns pelo trabalho, a parte conceitual está muito clara da para a estrutura da arvore, mas eu queria tirar um duvida se for possível, como inserir um conjunto de elementos na árvore no caso quando o campo info é um ponteiro que deverá receber elemento tipo inteiro,float e um ponteiro char para nome.
Desde já grata,
[7] Comentário enviado por EnzoFerber em 12/05/2015 - 16:19h
[6] Comentário enviado por dianaluz92 em 12/05/2015 - 15:08h
Parabéns pelo trabalho, a parte conceitual está muito clara da para a estrutura da arvore, mas eu queria tirar um duvida se for possível, como inserir um conjunto de elementos na árvore no caso quando o campo info é um ponteiro que deverá receber elemento tipo inteiro,float e um ponteiro char para nome.
Desde já grata,
Boa tarde.
Pelo que entendi, você quer usar árvores para armazenar uma estrutura sua, certo?
typedef struct data {
int i;
float f;
char *nome;
} data_t;
Coloque os ponteiros direita e esquerda na estrutura que está usando.
typedef struct data* data_t;
struct data {
int i;
float f;
char *nome;
data_t esquerda, direita;
};
Agora é só modificar as funções inserir(), deletar(), procurar(), imprimir(), etc.
if (!raiz) {
...
} else if (strcmp(raiz->nome, nome_ptr) > 0) raiz->direita = inserir(raiz->direita, nome_ptr);
else if (strcmp(raiz->nome, nome_ptr) < 0 ) raiz->equerda = inserir(raiz->esquerda, nome_ptr);
else {
// strcmp() == 0
// dado existente
printf("dado existente!");
return raiz;
}
return raiz;
Espero ter ajudado,
[]'s
Enzo Ferber
[6] Comentário enviado por dianaluz92 em 12/05/2015 - 15:08h
Parabéns pelo trabalho, a parte conceitual está muito clara da para a estrutura da arvore, mas eu queria tirar um duvida se for possível, como inserir um conjunto de elementos na árvore no caso quando o campo info é um ponteiro que deverá receber elemento tipo inteiro,float e um ponteiro char para nome.
Desde já grata,
Boa tarde.
Pelo que entendi, você quer usar árvores para armazenar uma estrutura sua, certo?
typedef struct data {
int i;
float f;
char *nome;
} data_t;
Coloque os ponteiros direita e esquerda na estrutura que está usando.
typedef struct data* data_t;
struct data {
int i;
float f;
char *nome;
data_t esquerda, direita;
};
Agora é só modificar as funções inserir(), deletar(), procurar(), imprimir(), etc.
if (!raiz) {
...
} else if (strcmp(raiz->nome, nome_ptr) > 0) raiz->direita = inserir(raiz->direita, nome_ptr);
else if (strcmp(raiz->nome, nome_ptr) < 0 ) raiz->equerda = inserir(raiz->esquerda, nome_ptr);
else {
// strcmp() == 0
// dado existente
printf("dado existente!");
return raiz;
}
return raiz;
Espero ter ajudado,
[]'s
Enzo Ferber
[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h
Bom dia Enzo,
Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.
Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.
Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.
Obrigado por compartilhar conosco este material e seu conhecimento!
Bom dia Enzo,
Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.
Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.
Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.
Obrigado por compartilhar conosco este material e seu conhecimento!
[9] Comentário enviado por EnzoFerber em 13/05/2015 - 09:04h
[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h
Bom dia Enzo,
Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.
Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.
Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.
Obrigado por compartilhar conosco este material e seu conhecimento!
Bom dia, Ragen.
Em primeiro lugar, muito obrigado pelos elogios.
Segundo, concordo plenamente com você (Muita gente e eu, na verdade). Uma dessas pessoas é o CEO do StackExchange, que possui um blog muito bom. O nome dele é Joel Spolsky e o blog é o http://www.joelonsoftware.com. Ele escreveu um artigo precisamente sobre a troca de linguagens "mais baixas" pelo Java nas faculdades, e como isto está arruinando o mercado de trabalho e a qualidade dos profissionais. O artigo chama-se "The Perils of JavaSchool". Excelente texto, vale a pena ser lido. (O blog todo, na verdade)
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
Pessoalmente, acredito que todos deveriam ter um semestre em Assembly para entender como a CPU/Memória/HD funcionam e interagem - como tudo realmente acontece "embaixo do capô". Faz uma falta danada!
Sobre Joel: http://www.joelonsoftware.com/AboutMe.html
StackExchange: http://www.stackexchange.com
*
http://blog.codinghorror.com/why-cant-programmers-program/
Artigo muito bom também, falando sobre bacharéis que não conseguem programar programas *simples*! Leitura recomendada!
[]'s
Enzo Ferber
[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h
Bom dia Enzo,
Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.
Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.
Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.
Obrigado por compartilhar conosco este material e seu conhecimento!
Bom dia, Ragen.
Em primeiro lugar, muito obrigado pelos elogios.
Segundo, concordo plenamente com você (Muita gente e eu, na verdade). Uma dessas pessoas é o CEO do StackExchange, que possui um blog muito bom. O nome dele é Joel Spolsky e o blog é o http://www.joelonsoftware.com. Ele escreveu um artigo precisamente sobre a troca de linguagens "mais baixas" pelo Java nas faculdades, e como isto está arruinando o mercado de trabalho e a qualidade dos profissionais. O artigo chama-se "The Perils of JavaSchool". Excelente texto, vale a pena ser lido. (O blog todo, na verdade)
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
Pessoalmente, acredito que todos deveriam ter um semestre em Assembly para entender como a CPU/Memória/HD funcionam e interagem - como tudo realmente acontece "embaixo do capô". Faz uma falta danada!
Sobre Joel: http://www.joelonsoftware.com/AboutMe.html
StackExchange: http://www.stackexchange.com
*
http://blog.codinghorror.com/why-cant-programmers-program/
Artigo muito bom também, falando sobre bacharéis que não conseguem programar programas *simples*! Leitura recomendada!
[]'s
Enzo Ferber
[10] Comentário enviado por Ragen em 13/05/2015 - 18:22h
[9] Comentário enviado por EnzoFerber em 13/05/2015 - 09:04h
[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h
Bom dia Enzo,
Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.
Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.
Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.
Obrigado por compartilhar conosco este material e seu conhecimento!
Bom dia, Ragen.
Em primeiro lugar, muito obrigado pelos elogios.
Segundo, concordo plenamente com você (Muita gente e eu, na verdade). Uma dessas pessoas é o CEO do StackExchange, que possui um blog muito bom. O nome dele é Joel Spolsky e o blog é o http://www.joelonsoftware.com. Ele escreveu um artigo precisamente sobre a troca de linguagens "mais baixas" pelo Java nas faculdades, e como isto está arruinando o mercado de trabalho e a qualidade dos profissionais. O artigo chama-se "The Perils of JavaSchool". Excelente texto, vale a pena ser lido. (O blog todo, na verdade)
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
Pessoalmente, acredito que todos deveriam ter um semestre em Assembly para entender como a CPU/Memória/HD funcionam e interagem - como tudo realmente acontece "embaixo do capô". Faz uma falta danada!
Sobre Joel: http://www.joelonsoftware.com/AboutMe.html
StackExchange: http://www.stackexchange.com
*
http://blog.codinghorror.com/why-cant-programmers-program/
Artigo muito bom também, falando sobre bacharéis que não conseguem programar programas *simples*! Leitura recomendada!
[]'s
Enzo Ferber
Opa Enzo,
Valeu pela dica. Eu já conhecia o StackExchange, mas não conhecia o blog do fundador - estou lendo os links que recomendou, realmente ótima leitura!
Se tiver Linkedin, me adiciona lá: https://www.linkedin.com/profile/view?id=80923831
[9] Comentário enviado por EnzoFerber em 13/05/2015 - 09:04h
[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h
Bom dia Enzo,
Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.
Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.
Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.
Obrigado por compartilhar conosco este material e seu conhecimento!
Bom dia, Ragen.
Em primeiro lugar, muito obrigado pelos elogios.
Segundo, concordo plenamente com você (Muita gente e eu, na verdade). Uma dessas pessoas é o CEO do StackExchange, que possui um blog muito bom. O nome dele é Joel Spolsky e o blog é o http://www.joelonsoftware.com. Ele escreveu um artigo precisamente sobre a troca de linguagens "mais baixas" pelo Java nas faculdades, e como isto está arruinando o mercado de trabalho e a qualidade dos profissionais. O artigo chama-se "The Perils of JavaSchool". Excelente texto, vale a pena ser lido. (O blog todo, na verdade)
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
Pessoalmente, acredito que todos deveriam ter um semestre em Assembly para entender como a CPU/Memória/HD funcionam e interagem - como tudo realmente acontece "embaixo do capô". Faz uma falta danada!
Sobre Joel: http://www.joelonsoftware.com/AboutMe.html
StackExchange: http://www.stackexchange.com
*
http://blog.codinghorror.com/why-cant-programmers-program/
Artigo muito bom também, falando sobre bacharéis que não conseguem programar programas *simples*! Leitura recomendada!
[]'s
Enzo Ferber
Opa Enzo,
Valeu pela dica. Eu já conhecia o StackExchange, mas não conhecia o blog do fundador - estou lendo os links que recomendou, realmente ótima leitura!
Se tiver Linkedin, me adiciona lá: https://www.linkedin.com/profile/view?id=80923831
[11] Comentário enviado por EnzoFerber em 18/07/2015 - 12:15h
Pessoal,
Na página 4 há um erro. Na função pesquisa esqueci de fazer justamente a comparação que identifica o elemento procurado.
Para utilizar a função corretamente, favor fazer a seguinte modificação:
Após a linha "if (!raiz) return NULL;"
Colocar:
else if (raiz->info == info) return raiz;
É isso.
[]'s
Pessoal,
Na página 4 há um erro. Na função pesquisa esqueci de fazer justamente a comparação que identifica o elemento procurado.
Para utilizar a função corretamente, favor fazer a seguinte modificação:
Após a linha "if (!raiz) return NULL;"
Colocar:
else if (raiz->info == info) return raiz;
É isso.
[]'s
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Dicas
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Tópicos
Remoção de propaganda com o programa Comskip[AJUDA] (4)
Instalação do drive do adaptador wiffi (5)
Linux Lite Demorando Muito Para Ligar (1)
Top 10 do mês
-
Xerxes
1° lugar - 71.813 pts -
Fábio Berbert de Paula
2° lugar - 53.916 pts -
Mauricio Ferrari
3° lugar - 16.179 pts -
Andre (pinduvoz)
4° lugar - 15.128 pts -
Alberto Federman Neto.
5° lugar - 14.954 pts -
Daniel Lara Souza
6° lugar - 14.433 pts -
Diego Mendes Rodrigues
7° lugar - 14.178 pts -
Buckminster
8° lugar - 13.337 pts -
edps
9° lugar - 12.088 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
10° lugar - 11.386 pts
Scripts
A maior comunidade GNU/Linux da América Latina! Artigos, dicas, tutoriais, fórum, scripts e muito mais. Ideal para quem busca auto-ajuda.
Site hospedado por:
