Árvore de busca binária com frequência de consultas
Publicado por Danilo Azevedo (última atualização em 25/07/2014)
[ Hits: 3.319 ]
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); } } }
Memória compartilhada, semáforo e criação de processos
3º EP - Poli USP - Angry Birds (angry bixos)
Nenhum comentário foi encontrado.
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (16)
Arch Linux - Guia para Iniciantes (2)
Problemas ao instalar o PHP (11)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)