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: 53.907 ]
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
Análise dos Métodos de Ordenação usados em Algoritmos Computacionais
Dicas para aprender programação
Linguagem C - Listas Duplamente Encadeadas
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
Boas Práticas e Padrões Idiomáticos em Go e C
Vale a pena ter mais de uma interface grafica no seu Linux?
Estrutura e Funcionamento de um Ebuild no Gentoo Linux
Dicas
[Resolvido] Google Chrome reclamando de perfil em uso após mudar hostname
Instalando o Tema de Ícones Tela Circle
Copiar Para e Mover Para no menu de contexto do Nautilus e Dolphin
Dotando o Thunar das opcoes Copiar para e Mover para no menu de contexto
Tópicos
Instalação Dual Boot Linux+Windows 11 (4)
No Ubuntu 26.04, sudo passou a mostrar os asteriscos ao digitar por pa... (5)
Como instalar Warsaw no Gentoo? (0)
Como insiro e excluo um elemento XML e JSON ao código Javascript (1)
Top 10 do mês
-
Xerxes
1° lugar - 128.823 pts -
Fábio Berbert de Paula
2° lugar - 65.830 pts -
Buckminster
3° lugar - 39.735 pts -
Alberto Federman Neto.
4° lugar - 34.124 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
5° lugar - 23.253 pts -
edps
6° lugar - 22.080 pts -
Daniel Lara Souza
7° lugar - 20.996 pts -
Mauricio Ferrari (LinuxProativo)
8° lugar - 19.876 pts -
Sidnei Serra
9° lugar - 19.709 pts -
Andre (pinduvoz)
10° lugar - 16.063 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:
