Árvore de busca binária com frequência de consultas
Publicado por Danilo Azevedo (última atualização em 25/07/2014)
[ Hits: 3.475 ]
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); } } }
Biblioteca estática para manipulação de pilhas
Mudando Cor da Letra e Fundo de Tela
Nenhum coment�rio foi encontrado.
Customizar a Instalação do Linux Debian com Preseed
Atualizando o Passado: Linux no Lenovo G460 em 2025
aaPanel - Um Painel de Hospedagem Gratuito e Poderoso
Um modo leve de ouvir/ver áudio/vídeo da internet em máquinas pererecas
Resolver algumas mensagens de erro do SSH
Instalar módulo de segurança do Banco do Brasil Warsaw do tipo .run
Possível Migração de windows para linux ???? (pc da empresa) (1)
criar alias do comando "ls -la" (0)
Exibir detalhes de vídeo no Caja (1)