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

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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

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

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