Árvore binária de busca, algoritmos de inserção, caminhamento e busca explicados
Publicado por Ewerton Daniel de Lima (última atualização em 14/03/2010)
[ Hits: 36.774 ]
Olá pessoal! Comecei a brincar com árvores em C e acabei de construir algumas rotinas. Comentei cada rotina.
Espero que seja útil pra alguém.
Grande abraço!
#include <stdio.h> #include <string.h> #include <malloc.h> /*Declaração do nó para a árvore, composto de ponteiros da direita e esquerda e de um campo para dado que no caso é o campo char dado[30]; */ struct no { char dado[30]; struct no *direita; struct no *esquerda; }; struct no *raiz; //Ponteiro da raiz struct no *alocar; //Ponteiro para fazer alocação /*Rotina de busca Insere o dado em string e ela retorna o ponteiro em hexa para a região da memória para o qual o ponteiro está apontando. */ struct no * buscar(char *dado) { struct no *ponteiro; ponteiro = raiz; while (ponteiro) { if (strcmp(dado, ponteiro->dado)==0) //Faz a comparação de strings return ponteiro; //Retorna ponteiro se o encontrar if (strcmp(dado, ponteiro->dado)>0) ponteiro = ponteiro->direita; else ponteiro = ponteiro->esquerda; } return NULL; //Retorna o ponteiro nulo } /*Rotina que faz a inserção na árvore binária de busca O Parâmetro dado recebe um ponteiro para string A função não retorna valor nem referência */ void inserir(char *dado) { alocar = (struct no *) malloc(sizeof(struct no)); //Faz alocação na memória if (!alocar) { //Se não for possível a alocação, sai do programa printf("Falta de memória"); exit(0); } strcpy(alocar->dado, dado); //Copia o dado para o novo nó alocado if (!raiz) { //Se não houver elemento ainda na árvore, insere na raiz raiz = alocar; } else //se não... { //ponteiros para busca struct no *ponteiro; struct no *ponteiroAnterior; ponteiro = raiz; //ponteiro inicia na raiz ponteiroAnterior = NULL; //anterior inicial em NULL while (ponteiro) { //Faz a busca do lugar ao qual deve ser inserido o nó ponteiroAnterior = ponteiro; if (strcmp(dado, ponteiro->dado)==0) { printf("\nDado inserido já existe!"); return; } if (strcmp(dado, ponteiro->dado)>0){ ponteiro = ponteiro->direita; } else { ponteiro = ponteiro->esquerda; } } if (strcmp(dado, ponteiroAnterior->dado)>0) { ponteiroAnterior->direita = alocar; //atribui o endereço de alocação ao ponteiro da direita do nó anterior } else { ponteiroAnterior->esquerda = alocar; //atribui o endereço de alocação ao ponteiro da esquerda do nó anterior } } } /*Faz o caminhamento em ordem recursivamente*/ void caminharEmOrdem(struct no *ponteiro) { if (ponteiro) { caminharEmOrdem(ponteiro->esquerda); printf("\n%s", ponteiro->dado); caminharEmOrdem(ponteiro->direita); } } /*Rotina principal com algumas inserções, um caminhamento e uma busca no final */ int main() { char dado[30]; printf("\nInserir: "); gets(dado); inserir(dado); printf("\nInserir: "); gets(dado); inserir(dado); printf("\nInserir: "); gets(dado); inserir(dado); printf("\nInserir: "); gets(dado); inserir(dado); caminharEmOrdem(raiz); printf("\nInserir para buscar: "); gets(dado); printf("%p", buscar(dado)); getchar(); }
Verificador de senhas: Comparando palavras
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Não consigo acessar os modos de desempenho (2)
Ubuntu — tentando iniciar o windows? (0)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba