Árvore de busca binária com frequência de consultas
Publicado por Danilo Azevedo (última atualização em 25/07/2014)
[ Hits: 3.179 ]
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); } } }
Jogo da Velha com IA invencivel
Nenhum comentário foi encontrado.
Agora temos uma assistente virtual no fórum!!! (247)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
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
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
Agora temos uma assistente virtual no fórum!!! (247)
iso de sistema 32 bit em atividade (12)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (27)