在c中用静态和预先确定的元素创建树

Question

我有一个问题，我决定使用二叉树来解决，但是：

我想不出一种方法来用预定的元素填充树，使其看起来像下面的图像我使用了一个向量如下，然后我将它插入到树中，我不知道我是否只是按照图像中树的组装顺序离开它，但我所做的是以下内容：

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

填写如下：

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

所以现在我的传奇是如何对每个单词施加一些权重，将其指向一侧或另一侧，我试图通过这种方式解决的练习是这样的：

构建一个程序，能够得出以下哪些动物通过问题和答案选择。可能的动物：狮子、马、人、猴子、鲸鱼、鸵鸟、企鹅、鸭子、鹰、乌龟、鳄鱼和蛇。

测试

Answer 1

每个词都可以标注parent-child关系，权重=parent的权重+同parent下自己的序号，赞

Mamifero =>“1”
aves =>“2”
repteis => "3"
bipede =>“12”（第二个 child 在 Mamifero 之下）
afrutifero =>“122”（双足动物下的第二个 child）

如果前缀相同，说明存在parent-child关系，插入树的右侧，否则插入树的左侧

请看修改后的代码

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

在c中用静态和预先确定的元素创建树

create tree with static and pre-determined elements in c

c

data-structures

请看修改后的代码