Árvore de busca binária com frequência de consultas [C/C++]

Árvore de busca binária com frequência de consultas

Publicado por Danilo Azevedo (última atualização em 25/07/2014)

[ Hits: 3.321 ]

Download TAD_arvoreDeFreq.zip

0 0

Denuncie Favoritos Indicar

Segue anexo no arquivo .zip com instruções e informações do programa.

Esconder código-fonte

#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);        }
                }
            }

Scripts recomendados

Fibbonacci com Memoization - O(n)

Fibonnaci com Memoization

4 EP - Poli USP - LIG4 (LigK)

Leds da porta paralela com interface

Jogo Micro Breakout

Comentários

Nenhum comentário foi encontrado.