Вставка в двоичное дерево, которое использует void * в C

Question

Я должен создать двоичное дерево, используя структуру следующим образом:

struct treenode;
typedef struct treenode* TreeNode;
struct treenode {
 void* data;
 TreeNode left, right;
};

с использованием void * в качестве типа данных, которые будут храниться на каждом листе, так что объект любого типа может быть вставлен в дерево.

Когда я вставляю новый лист, мне нужно использовать функцию сравнения, которая проверяет, есть ли данные в новом листе, уже в дереве, которая принимает два пустых * параметра, например:

int compare(void* a, void* b){
..
..
}

но как я могу сравнить два объекта, если я не знаю, какого они типа?

Некоторый код для решения этой проблемы был бы очень полезен.

Answer 1

Предполагается, что функция сравнения предоставляется пользователем дерева, который знает, каков фактический тип данных.

int compare(void const* va, void const* vb) {
    Foo const* a = va;
    Foo const* b = vb;
    ...
}

Answer 2

Итак, кто вы в этом случае? Вы тот, кто реализует дерево? Вы тот, кто использует это? (Вы сказали, что должны «создать» дерево. Но «создать» - довольно неоднозначное слово.)

Тот, кто реализует , дерево не знает и не должен знать тип элемента. В этом весь смысл. Три должны быть реализованы так, чтобы они были полностью независимы от фактического типа элементов. Вот почему он использует void * указатели. И именно поэтому он вызывает некоторую внешнюю функцию для выполнения сравнения.

Тот, кто использует , эти три, конечно, будут знать фактический тип элемента. Пользователь предоставит фактические элементы, а пользователь предоставит соответствующую функцию сравнения. Поскольку пользователь знает фактический тип своих элементов, он может привести тип указателя внутри функции сравнения от void * к конкретному типу указателя и выполнить фактическое сравнение.

Итак, кем вы должны быть в этом случае? Пользователь? Или реализатор?

Answer 3

Лучше всего добавить функцию сравнения к самому дереву, но это потребует от вас поддерживать «дерево» как нечто отличное от «узла в дереве» или дублировать функцию в каждом узле кажется расточительным и странным):

typedef struct {
  TreeNode root;
  int (*compare)(const void *a, const void *b);
} Tree;

Как отметил Иоан в комментарии, вы можете также разрешить функции insert():

TreeNode * tree_insert(TreeNode root, const void *data,
                       int (*compare)(const void *a, const void *b));

Обратите внимание, что это довольно опасно; вы рискуете испортить структуру дерева, если при вставке в то же дерево вы передаете разные функции сравнения.

Answer 4

Если вы действительно хотите иметь возможность хранить различные типы в каждом узле, вам понадобится индикатор в самом узле, чтобы определить, какой тип полезной нагрузки. Что-то вроде:

typedef enum {
    TYP_STRING,
    TYP_INT,
    TYPE_FLOAT
} tNodeType;
struct treenode {
    tNodeType typ;
    void* data;
    TreeNode left, right;
};

Ваша функция сравнения должна сначала взглянуть на тип. Если типы разные, узлы разные. Если типы совпадают, вам нужно сравнить узлы на основе типа. С головы до головы, поэтому, возможно, потребуется отладка:

int compareNodes (TreeNode a, TreeNode b) {
    if (a->typ != b->typ) return FALSE;
    switch (a->typ) {
        case TYP_STRING: {
            return (strcmp ((char*)(a->data), (char*)(b->data)) == 0);
        }
        case TYP_INT: {
            return (*((int*)(a->data)) == *((int*)(b->data));
        }
        case TYP_FLOAT: {
            return (*((float*)(a->data)) == *((float*)(b->data));
        }
    }
    return FALSE;
}

Если вам не нужно хранить различные типы в дереве, тогда тип (и функция сравнения) принадлежат дереву, а не каждому узлу. Это обычный случай, хотя, безусловно, возможно иметь дерево, содержащее разные типы, - это лишь немного усложняет код.

Answer 5

Невозможно сравнить данные объекта, поскольку у вас есть только указатель на них и тип или даже размер. Единственное, что вы можете сделать, это проверить, равны ли указатели, что так же просто, как a == b. Нечто подобное a->value == b->value было бы неопределенным для void *, даже если оно было определено в исходной функции.