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.883 ]
Por: Enzo de Brito Ferber em 07/05/2015 | Blog: http://www.maximasonorizacao.com.br
Transversalização
Esta parte é bem simples e apenas ilustra as funções de transversalização.
Na forma "ordenada", visitamos primeiro a subárvore esquerda, depois a raiz e por último a subárvore direita.
Na forma pré-ordenada, visitamos primeiro a raiz, depois a subárvore esquerda e por último a subárvore direita.
Na forma pós-ordenada, visitamos primeiro a subárvore esquerda, depois a subárvore direita e por último a raiz.
Na forma "ordenada", visitamos primeiro 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 ", info);
ordenada (raiz->direita);
}
Na forma pré-ordenada, visitamos primeiro 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);
}
Na forma pós-ordenada, visitamos primeiro 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);
}
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
Dicas para aprender programação
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
Vale a pena ter mais de uma interface grafica no seu Linux?
Estrutura e Funcionamento de um Ebuild no Gentoo Linux
Instalação e Configuração do Void com Cinnamon
Dicas
Montagem pré automática de HD externo usb em NTFS não funciona no Debian Trixie - Solução
Guia de instalação do Gentoo Linux com Cinnamon (UEFI, LUKS2, Btrfs)
Tópicos
Top 10 do mês
-
Xerxes
1° lugar - 133.266 pts -
Fábio Berbert de Paula
2° lugar - 65.636 pts -
Buckminster
3° lugar - 42.027 pts -
Alberto Federman Neto.
4° lugar - 33.222 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
5° lugar - 22.700 pts -
edps
6° lugar - 21.769 pts -
Daniel Lara Souza
7° lugar - 21.251 pts -
Mauricio Ferrari (LinuxProativo)
8° lugar - 20.136 pts -
Sidnei Serra
9° lugar - 19.356 pts -
Andre (pinduvoz)
10° lugar - 15.960 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:
