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.427 ]
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
Guia de Programação em C/GTK 2 - Construindo uma Calculadora Completa
Análise dos Métodos de Ordenação usados em Algoritmos Computacionais
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
Como atualizar sua versão estável do Debian
Cirurgia para acelerar o openSUSE em HD externo via USB
Void Server como Domain Control
Dicas
Quer auto-organizar janelas (tiling) no seu Linux? Veja como no Plasma 6 e no Gnome
Copiando caminho atual do terminal direto para o clipboard do teclado
Script de montagem de chroot automatica
Tópicos
Top 10 do mês
-
Xerxes
1° lugar - 150.427 pts -
Fábio Berbert de Paula
2° lugar - 67.978 pts -
Buckminster
3° lugar - 23.620 pts -
Mauricio Ferrari
4° lugar - 20.947 pts -
Alberto Federman Neto.
5° lugar - 20.354 pts -
edps
6° lugar - 18.944 pts -
Daniel Lara Souza
7° lugar - 18.268 pts -
Andre (pinduvoz)
8° lugar - 16.797 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
9° lugar - 15.868 pts -
Jesuilton Montalvão
10° lugar - 15.235 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:
