Árvore de busca binária com frequência de consultas
Publicado por Danilo Azevedo (última atualização em 25/07/2014)
[ Hits: 3.354 ]
Segue anexo no arquivo .zip com instruções e informações do programa.
#include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> #define zero 0 #define op2 2 typedef struct arvore{ int numero; int freq; struct arvore *dir; struct arvore *esq; }No; No *inserir(No **Raiz, int numero); void listarpornivel(No **Raiz, int nivel); No *consulta_nodo(No *Raiz, int numero); void OrdemCrescente(No *Raiz); void OrdemDecrescente(No *Raiz); void imprimeArvore2(No *Raiz); No *iniciaArvore(No **Raiz); void imprimeArvore(No *Raiz); int maior(int a, int b); int altura(No *pRaiz); void listarpornivel2(No **Raiz, int nivel); void imprimeFreqc(No *Raiz, int k); void ValidarArvoreEsq(No *Raiz); void ValidarArvoreDir(No *Raiz); void limpastring(char stringtext[]); int main(){ No *lista = NULL, *listaux = NULL; int dado=0, i, j; char entrada[31], aux[31]; while(entrada[0] != 'e'){ fflush(stdin);gets(entrada); limpastring(aux); switch(entrada[0]){ case 'i': { i = 2; j = 0, dado = 0; while(entrada[i]!='{FONTE}'){ aux[j]=entrada[i]; j++; i++; } aux[j] = '{FONTE}'; dado = atoi(aux); listaux = (consulta_nodo(lista,dado)); if((consulta_nodo(lista,dado)) == NULL) inserir(&lista,dado); } break; case 'c': { i=2; j=0; while(entrada[i]!='{FONTE}'){ aux[j] = entrada[i]; j++; i++; } aux[j] = '{FONTE}'; dado = atoi(aux); listaux = consulta_nodo(lista,dado); if((consulta_nodo(lista,dado)) == NULL) printf("nao existe no com chave: %d\n",dado); else{ listaux->freq++; printf("existe no com chave: %d\n",listaux->numero); //ValidarArvoreDir(lista); //ValidarArvoreEsq(lista); } } break; case 'p': switch (entrada[op2]){ case 'c':OrdemCrescente(lista); break; case 'd':OrdemDecrescente(lista); break; default: break; } printf("\n"); break; case 'd':imprimeArvore(lista); break; case 'f': { i=2; j=0; while(entrada[i]!='{FONTE}'){ aux[j]=entrada[i]; j++; i++; } aux[j] = '{FONTE}'; dado = atoi(aux); listaux = consulta_nodo(lista,dado); if(listaux != NULL) printf("%d\n",listaux->freq); else printf("\n"); } break; case 'n': { i=2; j=0; while(entrada[i]!='{FONTE}'){ aux[j]=entrada[i]; j++; i++; } aux[j] = '{FONTE}'; dado = atoi(aux); if(dado >= 1) listarpornivel(&lista,dado); else printf("\n"); } break; case 'k': { i=2; j=0; while(entrada[i]!='{FONTE}'){ aux[j]=entrada[i]; j++; i++; } aux[j] = '{FONTE}'; dado = atoi(aux); if(dado >= 1) imprimeFreqc(lista,dado); else printf("\n"); } break; default: break; printf("\n"); } } return 0; } void limpastring(char stringtext[]){ int i , value = (strlen(stringtext)); for(i = 0; i < value; i++){ stringtext[i] = '{FONTE}'; } } No *inserir(No **Raiz, int numero){ if(*Raiz == NULL){ *Raiz = (No *) malloc(sizeof(No)); (*Raiz)->esq = NULL; (*Raiz)->dir = NULL; (*Raiz)->numero = numero; (*Raiz)->freq = zero; return (*Raiz); }else{ if(numero < (*Raiz)->numero) return inserir(&(*Raiz)->esq, numero); else return inserir(&(*Raiz)->dir, numero); } } No *consulta_nodo(No *Raiz, int numero){ if (Raiz == NULL) return NULL; if(Raiz->numero == numero) return Raiz; if(numero < Raiz->numero) return consulta_nodo(Raiz->esq,numero); else return consulta_nodo(Raiz->dir,numero); } void OrdemCrescente(No *Raiz){ if(Raiz != NULL){ OrdemCrescente(Raiz->esq); printf("\n%d %d",Raiz->numero,Raiz->freq); OrdemCrescente(Raiz->dir); } } void OrdemDecrescente(No *Raiz){ if(Raiz != NULL){ OrdemDecrescente(Raiz->dir); printf("\n%d %d",Raiz->numero,Raiz->freq); OrdemDecrescente(Raiz->esq); } } void imprimeArvore(No *Raiz){ if(Raiz != NULL){ imprimeArvore(Raiz->esq); printf("\nchave: %d",Raiz->numero); if(Raiz->esq != NULL ) printf(" filho esquerdo: %d",Raiz->esq->numero); else printf(" filho esquerdo: nil"); if(Raiz->dir != NULL ) printf(" filho direito: %d\n",Raiz->dir->numero); else printf(" filho direito: nil\n"); imprimeArvore(Raiz->dir); } } void listarpornivel(No **Raiz, int nivel){ // printf("ok"); if ((nivel == 1)&&(*Raiz !=NULL)) { // printf("ok"); printf("%d %d\n",(*Raiz)->numero, (*Raiz)->freq); } else { if ((*Raiz)->esq != NULL) { listarpornivel(&(*Raiz)->esq ,nivel-1); } if ((*Raiz)->dir != NULL) { listarpornivel(&(*Raiz)->dir ,nivel - 1); } } } void listarpornivel2(No **Raiz, int nivel){ //printf("ok"); if ((nivel == 1)&&(*Raiz !=NULL)) { imprimeArvore2((*Raiz)); } else { if ((*Raiz)->esq != NULL) { listarpornivel2(&(*Raiz)->esq ,nivel-1); } if ((*Raiz)->dir != NULL) { listarpornivel2(&(*Raiz)->dir ,nivel - 1); } } } void imprimeArvore2(No *Raiz){ if(Raiz != NULL){ imprimeArvore2(Raiz->esq); printf("\nchave: %d",Raiz->numero); imprimeArvore2(Raiz->dir); } } void imprimeFreqc(No *Raiz, int k){ if(Raiz != NULL){ imprimeFreqc(Raiz->esq, k); if(Raiz->freq == k || Raiz->freq > k) printf("\n%d",Raiz->numero); imprimeFreqc(Raiz->dir, k); } } void ValidarArvoreEsq(No *Raiz){ int tpnum=0, tpfreq=0; if(Raiz != NULL){ if(Raiz->freq < Raiz->esq->freq){ tpnum = Raiz->numero; tpfreq = Raiz->freq; Raiz->numero = Raiz->esq->numero; Raiz->freq = Raiz->esq->freq; Raiz->esq->numero = tpnum; Raiz->esq->freq = tpfreq; } else ValidarArvoreEsq(Raiz->esq); } } void ValidarArvoreDir(No *Raiz){ int tpnum=0, tpfreq=0; if(Raiz != NULL){ printf("ok"); if(Raiz->freq < Raiz->dir->freq){ tpnum = Raiz->numero; tpfreq = Raiz->freq; Raiz->numero = Raiz->dir->numero; Raiz->freq = Raiz->dir->freq; Raiz->dir->numero = tpnum; Raiz->dir->freq = tpfreq; } else{ printf("ok"); ValidarArvoreDir(Raiz->dir); } } }
Um Classico exercicio de Lógica de Programação
AIMG-mostrar imagem fraquimentada em pontos aleatórios
Nenhum comentário foi encontrado.
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
VMs e Interfaces de Rede desapareceram (11)
Instalação do drive do adaptador wiffi (7)