Ir ao conteúdo
  • Cadastre-se
piresrafael1

C Programa de busca binaria em C....

Recommended Posts

Bom dia, pessoal!!

Sou novo no fórum, e também em programação, estou com um problema da faculdade em que devo fazer o seguinte :

 

"Considere uma árvore binária cujos nós têm um campo chave de um tipo linearmente ordenado, um tipo (como int, char, string, etc.) que admite comparação.

Uma árvore binária deste tipo é de busca se cada nó tem a seguinte propriedade:  a chave de p é (1) maior ou igual à chave de qualquer nó na subárvore esquerda de p  e (2) menor ou igual à chave de qualquer nó na subárvore direita de p.  

Em outras palavras, se p é um nó qualquer então:

esq->chave   ≤   p->chave   ≤   dir->chave

 

O que deve ser realizado na questão:

Considerando-se uma árvore ordenada, ou árvore binária de busca, sem balanceamento, faça um programa para manipular uma árvore que armazene dados de um cliente.

O cliente pode ser uma estrutura com nome, data de nascimento e salário.

Para a árvore, faça as seguintes rotinas:

a) inserir ordenando por nome

B) inserir ordenando por data de nascimento

c) remover um nó folha qualquer

d) verificar se a árvore está vazia

e) mostrar a árvore (basta que os dados dos clientes sejam mostrados “em  ordem”, um cliente por linha)

No main, insira de 10 a 15 clientes, ordenando por nome. Mostre sua árvore.

Depois remova os elementos da primeira árvore, inserindo numa segunda, agora ordenando por data de nascimento. Mostre a segunda árvore no final."

 

Estou me matando pra fazer e tentar resolver, segue codigo a baixo, tem como alguem me dar uma ajuda? por exemplo, para dar entrada no nome, ele tranca.. talvez o que estou pedindo seja muito ***** literalmente, mas no momento to achando *** hehehe, se puderem ajudar, agradeço.

 

 

 


 

#include<stdio.h>

#include<stdlib.h>

struct no{

int dado;

struct no *esq, *dir;

};

typedef struct no ARV;

int menu(){

int opc;

system("cls");

printf("=============================");
printf("\n[0]-sair: \n");
printf("=============================");
printf("\n[1]-inserir nome: \n");
printf("=============================");
printf("\n[3]-inserir data de nascimento: \n");
printf("=============================");
printf("\n[4]-inserir salario: \n");
printf("=============================");
printf("\n[2]-pre ordem: \n");
printf("=============================");
printf("\n[5]- quantidade: \n");
printf("=============================");
printf("\n[6]- maior elemento: \n");
printf("=============================");
printf("\n[7]- menor elemento: \n");
printf("=============================");
printf("\n[8]- remover maior elemento: \n");
printf("=============================");
printf("\n[9]- remover por valor: \n");
printf("=============================");
printf("\n[10]- mostrar no: \n");
printf("=============================");
printf("\n[11]- altura da arvore: \n");
printf("=============================");
printf("\n[12]- nivel do no: \n");
printf("=============================");
printf("\n[13]-em ordem: \n");
printf("=============================");
printf("\n[14]- pos ordem: \n");
printf("=============================");
printf("\nEscolha uma opcao:\n");
scanf("%i",&opc);

return opc;

}

void inserir(ARV **r, int valor){

if(*r==NULL){

ARV *novo;

novo=(ARV *)malloc(sizeof(ARV));

novo->dir=NULL;

novo->esq=NULL;

novo->dado=valor;

*r =novo;

}

else{

if(valor>(*r)->dado)

inserir(&((*r)->dir),valor);

else

inserir(&((*r)->esq),valor);

}

}

void pre_ordem(ARV **r){

if(*r!=NULL){

printf("%i \n",(*r)->dado);

pre_ordem(&((*r)->esq));

pre_ordem(&((*r)->dir));

}

}

void em_ordem(ARV **r){

if(*r!=NULL){

em_ordem(&((*r)->esq));

printf("%i \n",(*r)->dado);

em_ordem(&((*r)->dir));

}

}

void pos_ordem(ARV **r){

if(*r!=NULL){

pos_ordem(&((*r)->esq));

pos_ordem(&((*r)->dir));

printf("%i \n",(*r)->dado);

}

}

//FORMA SEQUENCIAL

int *maior(ARV **r){

ARV *p;

if(*r==NULL){

return NULL;

}

else{

for(p=(*r);p->dir!=NULL;p=p->dir);

return &(p->dado);

}

}

int *menor(ARV **r){

ARV *p;

if(*r==NULL){

return NULL;

}

else{

if((*r)->esq==NULL)

return &((*r)->dado);

else

return menor((&(*r)->esq));

}

}

int qtd_nos(ARV **r){

if(*r==NULL)

return 0;

else{

return 1 + qtd_nos(&((*r)->esq)) + qtd_nos(&((*r)->dir));

}

}

//FORMA RECURSIVA

int remove_maior_elemento(ARV **r){

if (*r==NULL)

return 0;

else{

if((*r)->dir==NULL){

ARV *p;

p=*r;

*r=p->esq;

free(p);

return 1;

}

else{

return remove_maior_elemento(&((*r)->dir));

}

}

}

int remover_valor(ARV **r, int vlr){

if(*r==NULL)

return 0;

else{

if(vlr==(*r)->dado){

if((*r)->esq==NULL){

ARV *p;

p=*r;

*r=p->dir;

free(p);

return 1;

}

else{

if((*r)->dir==NULL){

ARV *p;

p=*r;

*r=p->esq;

free(p);

return 1;

}

else{

(*r)->dado=*maior(&((*r)->esq));

remove_maior_elemento(&((*r)->esq));

return 1;

}

}

}

else{

if(vlr>(*r)->dado)

return(remover_valor(&((*r)->dir),vlr));

else

return(remover_valor(&((*r)->esq),vlr));

}

}

}

void nos_folhas(ARV **r){

if ((*r)==NULL){

printf("Arvore vazia");

return ;

}

if(((*r)->esq==NULL)&& ((*r)->dir==NULL)){

printf("%i \n ",(*r)->dado);

}

else{

if((*r)->esq!=NULL){

nos_folhas(&((*r)->esq));

}

if((*r)->dir!=NULL) {

nos_folhas(&((*r)->dir));

}

}

}

int altura(ARV **r){

if((*r)==NULL)

return -1;

else{

if(altura(&((*r)->esq))>altura(&((*r)->dir)))

return 1+altura(&((*r)->esq));

else

return 1+altura(&((*r)->dir));

}

}

int nivel_no(ARV**r, int niv){

if((niv==0) && (*r!=NULL))

printf("%i\n",(*r)-> dado);

else{

if((*r)->esq!= NULL)

nivel_no(&((*r)->esq),niv-1);

if((*r)->dir!= NULL)

nivel_no(&((*r)->dir),niv-1);

}

}

int main(){

int opc,vlr;

ARV *r=NULL;

int *retorno;

int *nivel;

while(opc=menu()){

switch(opc){

case 1:

printf("informe um nome:\n");

scanf("%c",&vlr);

inserir(&r, vlr);

break;

case 2:

pre_ordem(&r);

break;

break;

case 3:

printf("informe a data de nascimento:\n");

scanf("%i",&vlr);

inserir(&r, vlr);

break;

case 4:

printf("informe um valor:\n");

scanf("%i",&vlr);

inserir(&r, vlr);

break;

case 5:

printf("a qtd de elementos é: %i \n",qtd_nos(&r));

break;

case 6:

retorno=maior(&r);

if(retorno==NULL)

printf("arvore vazia.\n");

printf("maior:%i \n",*retorno);

break;

case 7:

retorno=menor(&r);

if(retorno==NULL)

printf("arvore vazia.\n");

printf("menor:%i \n",*retorno);

break;

case 8:

if(remove_maior_elemento(&r))

printf("elemento removido. \n");

else

printf("nao foi possivel remover");

break;

case 9:

printf("valor:");

scanf("%i",&vlr);

if(remover_valor(&r,vlr))

printf("removido. \n");

else

printf("nao encontrado ,\n");

break;

case 10:

nos_folhas(&r);

break;

case 11:

printf("a altura da arvore é: %i \n",altura(&r));

break;

case 12:

printf("Nivel da arvore para consulta: ");

scanf("%i", &nivel);

break;

case 13:

em_ordem(&r);

break;

case 14:

pos_ordem(&r);

break;


}

system("pause");

}

}

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×