Árvore de busca binária com frequência de consultas
Publicado por Danilo Azevedo (última atualização em 25/07/2014)
[ Hits: 3.498 ]
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); } } }
Algoritmo método da Posição Falsa ou Falsa Posição, Newton Raphson e Bisseção em Calculo Númerico
Mudando Cor da Letra e Fundo de Tela
Busca em texto - Lista encadeada
Nenhum coment�rio foi encontrado.
O que é o THP na configuração de RAM do Linux e quando desabilitá-lo
Comparação entre os escalonadores BFQ e MQ-Deadline (acesso a disco) no Arch e Debian
Conciliando o uso da ZRAM e SWAP em disco na sua máquina
Servidor de Backup com Ubuntu Server 24.04 LTS, RAID e Duplicati (Dell PowerEdge T420)
Deixando o Plasma6 mais fluido no Linux
Como unir duas coleções de ROMs preservando as versões traduzidas (sem duplicatas)
Isso acontece com vcs também? (7)
Problema com audio apos upgrade (10)
Instalação automatizada do Debian 12 em UEFI (2)