Бинарные деревья в Си

Question

У меня есть следующий код:

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

TreeNode newTreeNode(void* data){
    TreeNode node = (TreeNode) malloc(sizeof(struct treenode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

bool insert(TreeNode tree, TreeNode node, int (*comp)(void*, void*)){
if(tree == NULL){
    tree = node;
    return true;
}
if(comp(node->data, tree->data) == 0){
    return false;
}
else if (comp(node->data, tree->data) < 0){
    insert((tree->left), node, comp);
}
else {
    insert((tree->right), node, comp);
}
return false;
}

int compare(void* i, void* j) {
if (*(int*)i < *(int*)j)
    return -1;
else if (*(int*)i == *(int*)j)
    return 0;
else
    return 1;
}

Он отлично работает для 3 узлов, но когда я пытаюсь вставить больше, он не проходит через первую строку дерева (строка после корня) потому что, похоже, он не обновил корневой узел.Я думаю, что это как-то связано с указателями в моем методе вставки, но я перепробовал все, что мог придумать, и до сих пор ничего не получаю.

Любая помощь очень ценится.

Answer 1

bool insert(TreeNode tree, TreeNode node, int (*comp)(void*, void*)){
if(tree == NULL){
    tree = node;
    return true;
}

Проблема (или, по крайней мере, a проблема) прямо здесь: вы передаете tree в качестве указателя на триод, затем вы назначаете node этому указателю - но вы Вы назначаете только локальную копию указателя, которая не влияет на указатель вне этой функции. Чтобы чего-то добиться, вам нужно что-то вроде:

bool insert(TreeNode *tree, TreeNode node, int (*comp)(void *, void *)) { 
    if (*tree == NULL) {
        *tree = node;
        return true;
    }
// ....

Таким образом, вы меняете указатель, адрес которого был передан в функцию.

В качестве альтернативы, вы можете рассмотреть вопрос о том, чтобы всегда помещать отдельный узел в дерево сразу после создания, поэтому вы всегда работаете только с дочерними элементами корневого узла и никогда не сталкиваетесь с (несколько) особенным случаем вставки корневого узла сам по себе.

Answer 2

Вам нужен указатель на ваш Treenode, чтобы изменить его. В противном случае вы изменяете только копию.

<code>
bool insert(TreeNode* tree, TreeNode node, int (<em>comp)(void</em>, void*)

Answer 3

Вы модифицируете только локальную копию дерева. Попробуйте:

bool insert(TreeNode* tree, TreeNode node, int (*comp)(void*, void*)){ 
if(*tree == NULL){ 
    *tree = node; 
    return true; 
} 
if(comp(node->data, (*tree)->data) == 0){ 
    return false; 
} 
else if (comp(node->data, (*tree)->data) < 0){ 
    insert((&((*tree)->left)), node, comp); 
} 
else { 
    insert((&((*tree)->right)), node, comp); 
} 
return false; 
}