Á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.192 ]

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

Programa recursivo para obter raiz quadrada

Rotina para controle de portas paralelas em C.

Arvore Binária

Biblioteca math.h

Biblioteca estática para manipulação de pilhas

Comentários

Nenhum comentário foi encontrado.