C Funcao busca nao esta retornando nada

[UmPrograma]

Pessoal, como eu sei o que a funcao esta retornando, se é verdadeiro ou falso.

 

Em C nao tem booleano, e sim 0 e 1.

 

Ai na seguinte funcao é para me retornar se encontrou ou não o valor. porém não esta funcionando.

segue a funcao

 

no23 *find(no23 *raiz, int key) {
    if (raiz==NULL)
        return NULL;      // não encontrou
    if (key == raiz->lkey)
        return raiz;      // é a chave esquerda
    if ((raiz->nkeys == 2) && (key == raiz->rkey))
        return raiz;      // é a chave direita
    if (key < raiz->lkey)
        return find(raiz->left, key);
    else if (raiz->nkeys == 1)
        return find(raiz->center, key);
    else if (key < raiz->rkey)
        return find(raiz->center, key);
    else
        return find(raiz->right, key);
}

 

Ai eu tento fazer o seguinte

 

if(busca(aux, valor)!=NULL)

printf("Encontrado");

 

Mas não funciona.

adicionado 16 minutos depois

0 é verdadeiro

e 1 é falso?

[UmPrograma]

Como faço para printar na tela se encontrei ou nao...

[UmPrograma]

hm

[Flávio Pedroza]

Citação

0 é verdadeiro

e 1 é falso?

0 é falso e qualquer coisa diferente de zero é verdadeiro.

Citação

if(busca(aux, valor)!=NULL)

printf("Encontrado");

É "busca" ou "find" o nome da função?

 

[UmPrograma]

@Flávio Pedroza 

 

É find

 

Mas ai é so um exemplo

adicionado 1 minuto depois

12 minutos atrás, Flávio Pedroza disse:

0 é falso e qualquer coisa diferente de zero é verdadeiro.

Citação

Estava tentando usar isso para printar na tela se encontrou ou nao. Mas nao funcionou

adicionado 5 minutos depois

 

 

 

Ela so funciona para um caso. Se eu mudar o valor que entra, por exemplo tirando o "valor" e colocando outra coisa que nao esteja na estrutura o algoritmo na funcao principal nao printa na tela que "Não achou"

 

adicionado 7 minutos depois

 

 

Desse jeito:

No* res;
res = busca(aux, valor); 
    if(res==0 || res ==NULL){
        printf("Nao achou");
    }
    else printf("Achou");

 

[Flávio Pedroza]

A sua lógica booleana para verificar se encontrou ou não está correta , tanto no primeiro post,  ("!=NULL"), quando no último ("==NULL"). O problema deve ser dentro da função "busca". 

[UmPrograma]

Como assim?

o que a de errado? A funcao busca é recursiva

adicionado 0 minutos depois

 

 

kkk agora que fui entender que tu disse que nao esta errada. entao ta certa kkkkk ooo vida

 

Tambem acho que é na funcao. Mas nao sei o que posso fazer

[Flávio Pedroza]

Posta o código todo, talvez possa ajudar a encontrar o erro na função recursiva.

[UmPrograma]

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

typedef struct no{
    int key1;
    int key2;
    int nkey;
    struct no *left;
    struct no *middle;
    struct no *right;
}No;

No *CriaNovo(){
    No *aux;
    aux = malloc(sizeof(No));
    return aux;
}

No *criaNo(int ch1, int ch2, int nchaves, No *pl, No *pc, No *pr){
   No *n;
   n->key1=ch1;
   n->key2=ch2;
   n->nkey=nchaves;
   n->left=pl;
   n->middle=pc;
   n->right=pr;
   return n;
}

int isLeaf(No *no){
    if(no==NULL){
        return 1;
    }
}

void adicionaChave(No *no,int val, No* pon){
    no->key1 =val;
    no->key2=pon->key1;
}

No *quebraNo(No *no, int val, int *rval, No *subarvore){
    No *paux;

    if (val > no->key2) {  // val esta mais a direita
       *rval = no->key2;   // promove a antiga maior
       paux = no->right;
       no->right = NULL;   // elimina o terceiro filho
       no->nkey = 1;      // atualiza o número de chaves
       return criaNo(val, 0, 1, paux, subarvore, NULL);
    } else if (val >= no->key1){ // val esta no meio
       *rval = val;        // continua sendo promovido
       paux = no->right;
       no->right = NULL;
       no->nkey = 1;
       return criaNo(no->key2, 0, 1, subarvore, paux, NULL);
    } else {              // val esta a mais a esquerda
       *rval = no->key1;
       // primeiro cria o nó a direita
       paux = criaNo(no->key2, 0, 1, no->middle, no->right, NULL);
       no->key1 = val;   // em seguida arruma o nó a esquerda
       no->nkey = 1;
       no->right = NULL;
       no->middle = subarvore;
       return paux;
    }
}

No *busca(No *raiz, int chave){
    if(raiz==NULL){
        printf("Árvore vazia!\n");
        return NULL;
    }
    if(chave == raiz->key1){
        return raiz;
    }
    if((raiz->nkey == 2) && chave == raiz->key2){
        return raiz;
    }
    if(chave < raiz->key1){
        return busca(raiz->left, chave);
    }
    else if((raiz->nkey == 2)&& chave < raiz->key2){
        return busca(raiz->middle, chave);
    }
    else if((raiz->nkey == 2)&& chave > raiz->key2){
        return busca(raiz->right, chave);
    }
}

No *insere( No **no, int val, int *rval){
    No *paux, *paux2;
    int   vaux, promov;

    if (*no == NULL) {    // arvore vazia
       *no = (No *) malloc (sizeof(No));
       *no = criaNo(val, 0, 0, NULL, NULL, NULL);
             // cria no folha com um valor
       return NULL;       // nada a fazer depois
    }
    if (isLeaf(*no)){     // chegou a folha
       if ((*no)->nkey == 1){ // caso fácil
          adicionaChave(*no, val, NULL);
          return NULL;
       } else {
          paux = quebraNo(*no, val, &vaux, NULL);
          *rval = vaux;
          return paux;
       }
    } else {             // continua a procura
       if (val < (*no)->key1)
          paux = insere( &((*no)->left), val, &vaux);
       else if (((*no)->nkey == 1) || (val < (*no)->key2))
          paux = insere( &((*no)->middle), val, &vaux);
       else
          paux = insere( &((*no)->right), val, &vaux);
       if (paux == NULL) // nao promoveu
          return NULL;
       else
          if ((*no)->nkey == 1){
             adicionaChave(*no, vaux, paux);
             return NULL;
          } else {
             paux2 = quebraNo(*no, vaux, &promov, paux);
             *rval = promov;
             return paux2;
          }
    }
}

void imprimir(No *no){
    No* ajuda=no;
    if(no==NULL){
        printf("Arvore vazia!\n");
    }
    else if(no!=NULL){
        if(no->nkey==1){
            printf("%d, ", no->key1);
                if(no->left!=NULL){
                    printf("%d, ", no->left);
                    return imprimir(no->left);
                }
                else if(no->right!=NULL){
                    printf("%d, ", no->right);
                    return imprimir(no->right);
                }
        }

        if(no->nkey==2){
            printf("%d, ", no->key1);
            printf("%d, ", no->key2);
            if(no->left!=NULL){
                    do{
                        printf("%d, ", no->left);
                    }while (no->left==NULL);
            }
            if(no->middle!=NULL){
                    do{
                        printf("%d, ", no->middle);
                    }while (no->middle==NULL);
            }
            if(no->right!=NULL){
                    do{
                        printf("%d, ", no->right);
                    }while (no->right==NULL);
            }

        }
    }
}

int main(){
    int key1, key2;
    No* aux, *a, *b, *c;
    aux = (No*)malloc(sizeof(No));
    a=5;b=17;c=22;
    key1=10;key2=20;

    aux->key1 = key1;aux->key2 = key2;aux->nkey=2;
    aux->left = a;aux->middle = b;aux->right = c;

    imprimir(aux);

    return 0;
}

 

[UmPrograma]

difícil ne?!

[Flávio Pedroza]

Adaptei um pouco o seu código, de modo a simplificar. Veja se está funcionando do jeito que queria:

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

typedef struct no{
    int keys[2];
    int nkey;
    struct no *subnos[3]; //0 - lef, 1 - middle, 2 - right
}No;

No *CriaNovo(){
    No *aux;
    aux = (No *)malloc(sizeof(No));
    return aux;
}

No *criaNo(int ch1, int ch2, int nchaves, No *pl, No *pc, No *pr){
   No *n = CriaNovo();
   n->keys[0]=ch1;
   n->keys[1]=ch2;
   n->nkey=nchaves;
   n->subnos[0] = pl;
   n->subnos[1] = pc;
   n->subnos[2] = pr;
   return n;
}


No *busca(No *raiz, int chave){
    No* aux = NULL;
    
    if(raiz==NULL){
        return NULL;
    }
    for (int i=0; i < raiz->nkey; i++)
      if(chave == raiz->keys[i]){
        return raiz;
      }
    
    for (int i=0; i < 3; i++) 
    {
        aux = busca(raiz->subnos[i], chave);
        if (aux != NULL) break;
    }
    
    return aux;
}

void imprimir(No *no){
    No* aux = NULL;
    
    if(no==NULL){
        printf("Arvore vazia!\n");
        return;
    }
    for (int i=0; i < no->nkey; i++) 
    {
      printf("%d ", no->keys[i]);
    }
    printf("\n");
    for (int i=0; i < 3; i++) 
    {
        aux = no->subnos[i];
        if (aux != NULL) imprimir(aux);
    }
}
    
int main(){
    No *a, *b, *c, *d, *e, *f, *g;
    No *aux;
    
    e = criaNo(1, 2, 2, NULL, NULL, NULL);
    f = criaNo(2, 3, 2, NULL, NULL, NULL);
    g = criaNo(3, 4, 2, NULL, NULL, NULL);
    c = criaNo(4, 5, 2, g, f, e);
    b = criaNo(5, 0,  1, NULL, c, NULL);
    a = criaNo(6, 0, 1, b, NULL, NULL);//raiz
    /*
    Estrutura da rede de nós
          a
        / | \
       b  *  * 
     / | \
    *  c  *
     / | \
    e  f  g 
  
    */
    imprimir(a);
    
    printf("Resultado da busca:\n");
    imprimir(busca(a, 4)); //busca no "c" a partir da raiz "a"
    
    
    free(e);
    free(f);
    free(g);
    free(c);
    free(b);
    free(a);
    
    
    return 0;
}

Estão faltando as demais funções (insere, quebra, etc...)

[UmPrograma]

todos os nos folhas (aqueles que nao tem filho) devem esta no mesmo nivel (na mesma altura)

adicionado 7 minutos depois

 

 

Está otimo, perfeito diria. So que é uma arvore balanceada, acho que essa seja nao seja balanceada...

 

Nesse algortimo que fiz, nao sei se chegou a roda-lo, mas nele nao consigo passar para a funcao insere. Ai eu passei os valores no proprio main, e depois imprimir. (so que nem o meu é uma arvore 2-3) Não sei...

adicionado 14 minutos depois

 

 

Mas eu posso mudar de tal forma que tenha a aparencia de uma arvore 2-3.