I have a problem that I decided to solve using binary tree, however:

I can't think of a way to fill the tree with predetermined elements so that it looks like the following in the image I used a vector as follows, and then I inserted it into the tree, I don't know if I just leave it in the order the tree will be assembled as in the image, but what I did was the following:

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));
}

fill it in as follows:

int main () {
    Animal *parent = NULL;
    char q;   
    // printf("%ld\n", sizeof(dict));
    // insert(dict[0], &parent, (compare)cmpStr);
    // printTree(parent);
    for (int i = 0;  i < NUM_NODES; i  ) {
        insert(dict[i], &parent, (compare)cmpStr);
    }

    printf ("%s", search(parent, "", (compare)cmpStr)->str);


    // printTree(parent);
    // do {
    // //     scanf("%c", &q);
    // //     printf("%s?", dict[rand() % 32]); 
    // // }while (q != 'q');

    return 0;
}

so now my saga would be how to apply some weight to each word, to direct it to one side or the other, the exercise I'm trying to solve in this way is this:

Build a program that is able to conclude which of the following animals was chosen through questions and answers. Possible animals: lion, horse, man, monkey, whale, ostrich, penguin, duck, eagle, turtle, crocodile and snake.

teste

CodePudding user response：

Each word can be marked with a parent-child relationship, weight = parent's weight own serial number under the same parent, like

• Mamifero => "1"
• aves => "2"
• repteis => "3"
• bipede => "12" (second child under Mamifero)
• afrutifero => "122" (second child under bipede)

If the prefixes are the same, it means that there is a parent-child relationship, insert it on the right side of the tree, otherwise insert it on the left side of the tree

Please see the modified code

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    typedef struct words {
        char *weight;
        char *name;
    } Words;
    
    Words dict[] = {
        {"1", "Mamifero"},
        {"2", "aves"},
        {"3", "repteis"},
        {"11", "quadrupede"},
        {"12", "bipede"},
        {"13", "voadores"},
        {"14", "aquaticos"},
        {"21", "nao-voadoras"},
        {"22", "nadadoras"},
        {"23", "de rapina"},
        {"31", "com casco"},
        {"32", "carnivoros"},
        {"33", "sem patas"},
        {"111", "carnivoro"},
        {"112", "herbivoro"},
        {"121", "onivoro"},
        {"122", "afrutifero"},
        {"211", "tropical"},
        {"212", "polar"},
        {"1111", "leao"},
        {"1121", "cavalo"},
        {"1211", "homem"},
        {"1221", "macaco"},
        {"131", "morcego"},
        {"141", "baleia"},
        {"2111", "avestruz"},
        {"2121", "pinguim"},
        {"221", "pato"},
        {"231", "aguia"},
        {"311", "tartaruga"},
        {"321", "crocodilo"},
        {"331", "cobra"}
    };
    
    #define NUM_NODES (sizeof(dict)/sizeof(*dict))
    
    typedef struct Animal *animalptr;
    
    typedef struct Animal {
        char *weight;
        char *str;
        animalptr left, right;
    } Animal;
    
    typedef int (*compare)(const char *, const char *);
    
    void insert(Words *key, Animal **leaf, compare cmp)
    {
        int res;
        if (*leaf == NULL) {
            *leaf = (Animal *) malloc(sizeof(Animal));
            (*leaf)->str = strdup(key->name);
            (*leaf)->weight = strdup(key->weight);
    
            (*leaf)->left = NULL;
            (*leaf)->right = NULL;
        } else {
            res = cmp(key->weight, (*leaf)->weight);
            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->name);
        }
    }
    
    int cmpStr(const char *a, const char *b)
    {
        if (strcmp(a, b) == 0)
            return 0;
        // If the prefixes are the same, it means a is a child of b, insert on the right
        if (strncmp(a, b, strlen(b)) == 0)
            return 1;
        // Otherwise insert left
        return -1;
    }
    
    char *search(Animal *leaf)
    {
        char *ret = "";
        char buf[16];
    
        while (leaf) {
            if (!leaf->right && !leaf->left) {
                ret = leaf->str;
                break;
            }
    
            // guess
            printf("É %s (yes,no): ", leaf->str);
            fgets(buf, sizeof(buf), stdin);
            if ((*buf == 'q') || (*buf == 'Q'))
                break;
    
            // If yes, go to the right
            if ((*buf == 'y') || (*buf == 'Y'))
                leaf = leaf->right;
            // Otherwise, left
            else if ((*buf == 'n') || (*buf == 'N'))
                leaf = leaf->left;
        }
    
        return ret;
    }
    
    int main()
    {
        Animal *parent = NULL;
    
        for (int i = 0;  i < NUM_NODES; i  ) {
            insert(&dict[i], &parent, (compare)cmpStr);
        }
    
        printf("%s\n", search(parent));
        return 0;
    }