-1

Olá estou com um problema que decidi resolver utilizando arvore binaria, porém:

  1. Não consigo pensar em uma forma de preencher a arvore com elementos pre determinados para que fique como segue na imagem inserir a descrição da imagem aqui

eu utilizei um vetor como segue, e então inseri o mesmo na arvore, não sei se eu simplesmente deixar ele na ordem a arvore será montado como na imagem, mais o que eu fiz foi o seguinte:

char* dict[] = {
    "Mamifero","aves","repteis",
    "quadrupede", "bipede", "voadores", "aquaticos",
    "nao-voadoras", "nadadoras", "de rapina", "com casco", "carnivoros", "sem patas",
    "carnivoro", "herbivoro", "onivoro", "afrutifero", "tropical", "polar", 
    "leao", "cavalo", "homem", "macaco", "morcego", "baleia", "avestruz", "pinguim", 
    "pato", "aguia", "tartaruga", "crocodilo", "cobra"
};

typedef struct Animal *animalptr;

typedef struct Animal {
    char *str;
    animalptr left, right;
} Animal;

typedef int (*compare)(const char*, const char*);


void insert (char* key, Animal** leaf, compare cmp) {
    int res;
    if (*leaf == NULL) { 
        *leaf = (Animal*) malloc(sizeof(Animal));
        (*leaf)->str = malloc(strlen(key) + 1);
        strcpy ((*leaf)->str, key);

        (*leaf)->left = NULL; 
        (*leaf)->right = NULL;

        // printf("\nnew node for %s", key); 
    } 
    else {
        // printf("%d\n", res);
        res = cmp (key, (*leaf)->str);
        if (res < 0) insert (key, &(*leaf)->left, cmp);
        else if (res > 0) insert (key, &(*leaf)->right, cmp);
        else printf("key '%s' already in tree\n", key);

    } 
}

int cmpStr (const char* a, const char* b) {
    // printf("a = %d\n b = %d", strlen(a), strlen(b));
    return (strcmp (a,b));
}

preenchi ele como segue:

for (int i = 0;  i < 32; i++) {
        insert(dict[i], &parent, (compare)cmpStr);
    }

então agora minha saga seria como aplicar algum peso para cada palavra, para direcionar ela para um lado ou para o outro, o exercício que estou tentando resolver dessa forma é esté:

inserir a descrição da imagem aqui

se alguém souber como me ajudar ou alguma dica seria bacana, desde já agradeço qualquer ajuda!

3
  • Primeiro de tudo, em C você não precisa converter ponteiros. O compilador faz isso por conta. Segundo, explique o que quer dizer com "aplicar um peso a cada palavra". Claro que o programa não vai receber uma palavra "cavalo" e saber dizer se ele é carnívoro ou herbívoro; você deverá criar uma struct (ou tipo) para representar cada animal e as informações referentes a ele. Commented 2/04/2022 às 21:09
  • como assim converter ponteiros tu diz? Então Bernardo eu quis dizer assim, como são 32 elementos de typedef struct Animal, talvez aplicar um outro campo à struct tipo um int n e ao criar um novo elemento atribuir um valor, manter os menores a esquerda e os maiores a direita eai fazer a leitura sabe, não sei se isso faz sentido, eu pretendia que o programa adivinhasse o animal a depender das respostas do usuario saca, descendo a arvore até a folha e terminando a execução após isso Commented 2/04/2022 às 21:33
  • Em *leaf = (Animal*) malloc(sizeof(Animal));, o (Animal*) não é necessário. Em C, essas conversões acontecem automaticamente. Essa sintaxe só é necessária no C++. Commented 3/04/2022 às 13:29

1 Resposta 1

0

Perceba que você está guardando decisões em nodos internos e resultados (os animais) nos nodos-folha.

typedef char bool;
typedef struct Decisao decisao;
typedef struct Animal animal;

struct Decisao {
    char *name; // "aves", "quadrúpede" etc.
    decisao *caseyes;
    decisao *casenot;
    animal *animais; // poderá, inclusive, guardar um array de animais (se a operação de inserção for construída de tal modo)
};

struct Animal {
    char *name; // nome do animal
    bool *fields;
    // fields será um array de informações sobre o animal. Normalmente se criaria um campo para cada informação,
    // mas se o seu objetivo for meramente construir uma árvore, essa abordagem já serve.
    // exemplo: animal.fields = ["ave", "não voadora", "nadadora" ...]
    // claro, como é um array de booleanos, você vai guardar um 1 para ir à direita na árvore ou 0 para ir
    // à esquerda. O exemplo acima ficaria animal.fields = [0, 1, 0 ...]
};

Desse jeito, é fácil ver que você chegou ao final da árvore, basta definir como nulos os ponteiros caseyes e casenot e dar algum valor para o ponteiro animais. Criei um tipo diferente para as decisões e para os animais. A sua operação de inserção/pesquisa deverá ponderar a ordem em que os campos estão, veja que eu usei um array de booleanos que funciona como uma árvore. Se um elemento for 0, pula-se para o filho à esquerda; se for 1, pula-se ao filho à direita.

Não precisa preencher esse array com caracteres, o tipo char ainda é um int, só que com tamanho reduzido. Basta tratar como se fosse um inteiro normal. Essa estrutura ainda possibilita que você mantenha um vetor de animais.

1
  • opa muito obrigado Bernardo, vc me ajudou muito! Commented 5/04/2022 às 0:07

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .