Á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.756 ]
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(); }
Script para calcular raizes de uma equacao do 2 grau
Tipos de ordenação - BubbleSort - SelectSort - Shellsort - Mergesort
Como agendar um backup automático do PostgreSQL no Cron evitando o problema de senha
Como preparar o Vim/Neovim para corrigir ortografia em português
Dark Web e Malwares na internet, quanto custa?
Configuração básica do Conky para mostrar informações sobre a sua máquina no Desktop
Como verificar o hash de um arquivo baixado da Internet e como criar um hash
Debian 12 - IPTABLES - removendo NFTABLES
OverWatch 2 - Abrindo portas do jogo no Iptables.
Como instalar o adaptador wifi USB Intelbras ACtion A1200 no Linux Mint
Como normalizar seus arquivos MP3 para que fiquem no mesmo volume
Como Incorporar o Áudio no Executável ? (1)
O que você está ouvindo agora? [2] (130)
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba
[Shell Script] Tire screenshots com Scrot facilmente com Zscrot
[Shell Script] DioPSI - Script multidistro para instalar programas
[Shell Script] ARS Vídeos - Cortador de vídeos e webcam shooter