Implementação de algoritmos para a manipulação de uma árvore binária de busca na linuagem C.

Especificações:
1. Consultar se a árvore é vazia ou não
2. Inserir valor
3. Percurso em pré-ordem
4. Percurso em ordem
5. Percurso em pós-ordem
6. Consultar valor
7. Consultar valor com mais detalhes
8. Consultar o maior valor
9. Consultar o menor valor
10. Consultar quantidade de nós
11. Imprimir Árvore
12. Sair

• Download arvoresBinarias.c
• Enviar nova versão

Esconder código-fonte

/*Lucas Juan Nogueira Novaes || Aluno Ciencia da computação CEUT
email p/ contato novaeslucas@hotmail.com*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

int quantidadeNos = 0;

typedef struct _no{
        int chave;
        int cont;
        
        struct _no *esq, *dir, *pai;
        }no;

no* auxPai = NULL;

void vaziaArvore(no *raiz){
    if (raiz == NULL){
             printf("   A arvore esta vazia\n\n");
             }
             else {
                  printf("   A arvore nao esta vazia\n\n");
                  }
    }
        
void insere (int x, no **p){
      
      if (*p==NULL){
                    *p=(no *)malloc(sizeof(no));
                    (*p)->chave=x;
                    (*p)->dir=NULL;
                    (*p)->esq=NULL;
                    (*p)->pai = auxPai;
                    (*p)->cont=0;
                    (*p)->cont++;
      }
      else{
            if (x<(*p)->chave){
                if((*p)->esq == NULL)
                    auxPai = *p;
                insere(x, &(*p)->esq);
            }
            if(x>(*p)->chave){
                if((*p)->dir == NULL)
                    auxPai = *p;               
                insere(x, &(*p)->dir);
            }
            if(x == (*p)->chave){
                (*p)->cont++;
                return;
            }
      }
}

int contaNos(no *p){
    if(p != NULL){
         quantidadeNos ++;
         contaNos(p -> dir);
         contaNos(p -> esq);        
    }
    return quantidadeNos;
}

no* busca(no *arvore, int x){
   if (arvore == NULL)
       return NULL;
   if (x == arvore->chave)
       return arvore;
   if (x < arvore->chave) 
       return busca(arvore->esq, x);
   else 
       return busca(arvore->dir, x);
}

void consultarValor(no* raiz){
    int num;
    no* aux;
    printf("Digite o numero procurado: ");
    scanf("%d", &num);
     
    aux = busca(raiz, num);
    if (aux == NULL)
       printf("Nao encontrado!\n");
    else{
       printf("Encontrado!\n");
       printf("O numero %d foi repetido %d vezes\n", num, aux->cont);
    }
}

void consultarDetalhes(no* raiz){
    int num;
    no* aux;
    printf("Digite o numero procurado: ");
    scanf("%d", &num);
    aux = busca(raiz, num);
    if (aux == NULL)
       printf("Nao encontrado!\n");
    else{
       printf("Encontrado!\n");
       printf("O numero %d foi repetido %d vezes.\n", num, aux->cont);
       if(aux->pai == NULL){
           printf("O No que contem o valor %d e a raiz da arvore.\n", num);
           if(aux->esq != NULL)
               printf("Valor contido no No filho a esquerda: %d\n", aux->esq->chave);
           if(aux->dir != NULL)
               printf("Valor contido no No filho a direito: %d\n", aux->dir->chave);
       }
       if((aux->esq == NULL)&&(aux->dir == NULL)&&(aux->pai != NULL)){
           printf("O No que contem o valor %d e uma folha da arvore.\n", num);
           printf("Valor contido no No pai: %d\n", aux->pai->chave);
       }
       if(((aux->esq != NULL)||(aux->dir != NULL))&&(aux->pai != NULL)){
           printf("O No que contem o valor %d e um no interno a arvore.\n", num);
           printf("Valor contido no No pai: %d\n", aux->pai->chave);
           if(aux->esq != NULL)
                printf("Valor contido no No filho a esquerda: %d\n", aux->esq->chave);
           if(aux->dir != NULL)
                printf("Valor contido no No filho a direito: %d\n", aux->dir->chave);
       }
    }
}

void imprime(no *p, int nivel){
     int i;
     if(p == NULL)
        return;
     imprime(p->dir, nivel+1);
     for(i=0;i<nivel;i++)
        printf("      ");
     printf("%6d\n\n",p->chave);
     imprime(p->esq,nivel+1);
     
}

void consultaNivel(no *p){
     int i, nivel;
     if(p == NULL)
        return;
     imprime(p->dir, nivel+1);
     for(i=0;i<nivel;i++)
        printf("      ");
     printf("%6d\n\n",p->chave);
     imprime(p->esq,nivel+1);
}

void preordem (no *arvore){
     if(arvore != NULL){
          printf("%d\n",arvore->chave);
          preordem(arvore->esq);
          preordem(arvore->dir);
     }
}

void emordem(no *arvore){
     if(arvore != NULL){
           emordem(arvore->esq);
           printf("%d\n",arvore->chave);
           emordem(arvore->dir);
     }
}

void posordem(no *arvore){
     if(arvore != NULL){
                 posordem(arvore->esq);
                 posordem(arvore->dir);
                 printf("%d\n",arvore->chave);
     }
}

void maiorValor(no* raiz){
    if((raiz->dir != NULL)&&(raiz->dir->chave > raiz->chave))
                 maiorValor(raiz->dir);
    else
                 printf("Maior Valor: %d\n", raiz->chave);
}

void menorValor(no* raiz){
    if((raiz->esq != NULL)&&(raiz->esq->chave < raiz->chave))
                 menorValor(raiz->esq);
    else
                 printf("Menor Valor: %d\n", raiz->chave);
}

//int quantNos(no* raiz){
//int cont;
  //  }
                          
 int menu(){
           int op;
           printf("\n>>>>>>>>>>MENU<<<<<<<<<<\n\n");
           printf("1 - Consultar lista\n");
           printf("2 - Inserir valor\n");
           printf("3 - Imprimir pre ordem\n");
           printf("4 - Imprimir in-ordem\n");
           printf("5 - Imprimir pos ordem\n");
           printf("6 - Procurar um numero\n");
           printf("7 - Consulta detalhada\n");
           printf("8 - Consultar maior valor\n");
           printf("9 - Consultar menor valor\n");
           printf("10 - Quantidades de nos da arvore\n");
           printf("11 - Imprimir arvore\n");           
           printf("12 - Sair\n\n>>>>>>>>>>MENU<<<<<<<<<<\n\n\n");
           printf("Digite sua opcao: ");
           scanf("%d", &op);
           return op;
           }
      

int main(){
    int n,a,b;
    no *raiz, *aux;
    raiz = NULL;
    int opcao;
    
    while(opcao!=12){
    system("cls");
    opcao = menu();
    switch(opcao){
                  
                  case 1:
                       system("cls");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       vaziaArvore(raiz);
                       printf(">>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       getch();
                       break;
                  case 2:
                       system("cls");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       printf("Digite -1 para terminar\n");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       do{
                            printf("Digite um numero: ");
                            scanf("%d", &n);
                            if(n!=-1){
                            insere(n, &raiz);                             
                            }
                       }while (n!=-1);
                       system("cls");
                       printf("          (o)\n");
                       printf("       (o)(o)(o)\n");
                       printf("  ( ARVORE BINARIA )\n");
                       printf("     (o)(o)(o)(o)\n");
                       printf("         )  (\n");
                       printf("       __|  |__\n\n\n");
                       imprime(raiz,0);
                       getch();
                       break;
                  case 3:
                       system("cls");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       printf("------> Pre-Ordem <------\n");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       preordem(raiz);
                       getch();
                       break;
                  case 4:
                       system("cls");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       printf("------> Em-Ordem <------\n");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       emordem(raiz);
                       getch();
                       break;
                  case 5:
                       system("cls");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       printf("------> Pos-Ordem <------\n");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       posordem(raiz);
                       getch();
                       break;
                  case 6:
                       system("cls");
                       printf("\n\nDigite o numero procurado: ");
                       scanf("%d",&a);
                       aux = busca(raiz,a);
                       if (aux == NULL){
                       system("cls");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       printf("       Nao encontrado!\n");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       }
                       else{
                       system("cls");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       printf("        Encontrado!\n");
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       }
                       getch();
                       break;
                  case 7:
                       system("cls");
                       consultarDetalhes(raiz);
                       getch();
                       break;
                  case 8:
                       system("cls");
                       maiorValor(raiz);
                       getch();
                       break;
                  case 9:
                       system("cls");
                       menorValor(raiz);
                       getch();
                       break;
                  case 10:
                       system("cls");
                       b=contaNos(raiz);
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       printf("  A arvore possui %d nos!\n",b);
                       printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n");
                       getch();
                       break;
                  case 11:
                       system("cls");
                       printf("ARVORE BINARIA\n");
                       imprime(raiz,0);
                       getch();
                       break;
                  case 12:                       
                       exit(0);
                       break;
                  
                  default :
                       system("cls");
                       printf("opcao nao existe! tente novamente");
                       getch();
                       break;   
                  }
                    
                    }

    system("PAUSE");
    return 0;

}

Tabuada

Peso ideal

Processo em background

Tabela hash com classes e tratamento de colisões por encadeamento

Hello world 3