Pages

segunda-feira, 11 de julho de 2016

Arvore binaria em c

Estrutura básica de como funciona uma arvore binaria alocado dinamicamente em c.

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

struct ARVORE{
       int valor;
       struct ARVORE *left, *right;
};

typedef struct ARVORE ARV;
ARV *criaArvore();
ARV *criaNoh(ARV *arvore, int v);
int vazia();
void imprimir(ARV *a);
void preOrdem(ARV *a);
void ordem(ARV *a);
void posOrdem(ARV *a);

int main(){
    ARV *a = criaArvore();
    int opc, valor;
    do{
        printf("1-Inserir novo noh\n"
               "2-imprimir\n3-Pre-Ordem"
               "\n4-Ordem\n5-Pos-ordem\n"
               "0-sair\n");
        scanf("%d",&opc);
        switch(opc){
          case 1:
               printf("informe um valor: ");
               scanf("%d",&valor);
               a = criaNoh(a, valor);
          break;
          case 2:
               if(!vazia(a))
                 imprimir(a);
               else
                 printf("AROVORE VAZIA\n");
          break;
          case 3:
               if(!vazia(a))
                 preOrdem(a);
               else
                 printf("AROVORE VAZIA\n");
                 printf("\n\n");
          break;
          case 4:
               if(!vazia(a))
                 ordem(a);
               else
                 printf("AROVORE VAZIA\n");
                 printf("\n\n");
          break;
          case 5:
               if(!vazia(a))
                posOrdem(a);
               else
                 printf("AROVORE VAZIA\n");
                 printf("\n\n");
          break;
          case 0: break;
          default: printf("opcao invalida\n");
        }
     getch();
     system("cls");
    }while(opc != 0);
    return 0;
}


ARV *criaArvore(){//maketree
    return NULL;
}

ARV *criaNoh(ARV *arvore, int v){//getnode
    ARV *atemp;
    if(arvore == NULL){
       atemp = (ARV*)malloc(sizeof(ARV));
       atemp ->valor = v;
       atemp->left = criaArvore();
       atemp->right = criaArvore();
       return atemp;
       }
    else{
         int dir = 0;
         atemp = arvore;
         ARV *pai, *raiz = arvore;
         while(atemp != NULL){
           pai = atemp;
           if(v <= atemp->valor){
              dir = 0;
              atemp = atemp->left;
              }
           else{
              dir = 1;
              atemp = atemp->right;
              }
        }
   atemp = (ARV*)malloc(sizeof(ARV));
   atemp->valor = v;
   atemp->left = criaArvore();
   atemp->right = criaArvore();
   if(dir)
     pai->right = atemp;
   else
     pai->left = atemp;
     
         return raiz;
    }
}


int vazia(ARV *a){
    return a == NULL;
}
void imprimir(ARV *a){
     printf("\nPai %d\n",a->valor);
     if(a->left != NULL)
       printf("Esq: %d\t",a->left->valor);
     else
       printf("Esq: NULL\t");
     if(a->right != NULL)
       printf("Dir: %d\t",a->right->valor);
     else
       printf("Dir: NULL\t");
     if(a->left != NULL)
      imprimir(a->left);
     if(a->right != NULL)
       imprimir(a->right);
}
void preOrdem(ARV *a){
printf("%d ",a->valor);

if(a->left != NULL){
printf("-> ");
preOrdem(a->left);
}
if(a->right != NULL){
printf("-> ");
preOrdem(a->right);
}
}
void ordem (ARV *a){
if (!vazia(a->left)){
ordem(a->left);
}

printf("%d -> ", a->valor);

if(!vazia(a->right)){
ordem(a->right);
}
}
void posOrdem(ARV *a){
if(!vazia(a->left)){
posOrdem(a->left);
}
if(!vazia(a->right)){
posOrdem(a->right);
}
printf("%d ->", a->valor);
}


Duvidas ou Trabalhos para fazer entre em Contato: marcofernando71@gmail.com

0 comentários:

Postar um comentário