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

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

[ Hits: 3.300 ]

Download TAD_arvoreDeFreq.zip




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

Tabuada com QT4

Derrubando SyGate Profissional Firewall !

1o. joguinho Labirinto (com graficos).c

Pilha

Efeito Bubblesort


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts