插入到二叉树中的 C 段错误

Question

我对 C 还是很陌生，我想弄清楚为什么我(相信)我遇到了段错误。我说相信，因为 exe 停止工作，所以我只是尝试在 Eclipse 的调试器中运行它，这就是我看到错误发生的地方。非常欢迎任何帮助/建议/批评。

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
struct node *left;
struct node *right;
double key;
} node;

void addNode(double value, node **node);
double dRand();
//node* search(double value, node *root);
void killTree(node *root);

int main(void)
{
    int nodesToAdd, i;
    node *n = NULL;
    node **p = &n;
    nodesToAdd = 10;
    for(i=0;i<nodesToAdd;i++)
    {
        printf("DEBUG: Adding node %d to tree\n", i+1);
        addNode(dRand(), p);
    }
    printf("DEBUG: Finished creating tree\n");
    printf("DEBUG: Freeing memory of tree\n");
    killTree(n);
    return 0;
}


double dRand()
{
return ((double)rand()/RAND_MAX)*10;
}

void addNode(double value, node **tree)
{
    node *insert = malloc(sizeof(*insert));
    insert->key = value;


    while(*tree){
        if(value < (*tree)->key)    tree = &(*tree)->left;
        else if(value > (*tree)->key) tree = &(*tree)->right;
        else return;
    }
    *tree = insert;
}

void killTree(node *node)
{
    if(!node){}
    else
    {
        killTree(node->left);
        killTree(node->right);
        printf("DEBUG: Deleting pointer to node of value %f from mem\n", node->key);
        free(node);
    }
}

编辑:我认为错误来自于在分配内存之前尝试引用左右节点，但我不确定我做错了什么。

EDIT2:非常感谢，效果非常好!

Answer 1

如果找到匹配项，则说明您的 addNode 函数存在内存泄漏。您分配，然后搜索。您应该搜索，然后只有在搜索失败时才分配。

关于您的崩溃，您没有将新节点的左右指针初始化为 NULL。这很关键。下次您进入树进行搜索时，您将取消对不确定指针的引用，并因此调用未定义的行为。

也许是这样的:

void addNode(double value, node **tree)
{
    // search first
    while (*tree)
    {
        if (value < (*tree)->key) 
            tree = &(*tree)->left;
        else if((*tree)->key < value) 
            tree = &(*tree)->right;
        else return;
    }

    // no match, so add
    *tree = malloc(sizeof(**tree));
    (*tree)->key = value;
    (*tree)->left = (*tree)->right = NULL; // note: set to null
}

接下来，虽然不重要，但您的 main() 函数不需要 p。您可以直接使用您的节点指针地址:

int main(void)
{
    int nodesToAdd, i;
    node *n = NULL;

    nodesToAdd = 10;
    for(i=0;i<nodesToAdd;i++)
    {
        printf("DEBUG: Adding node %d to tree\n", i+1);
        addNode(dRand(), &n);
    }
    printf("DEBUG: Finished creating tree\n");
    printf("DEBUG: Freeing memory of tree\n");
    killTree(n);
    return 0;
}

就其值(value)而言，如果您是 C 的新手，这并不可怕。掌握双重间接是 C 学习曲线中的一个常见停滞点，您在 add 函数中的使用一点也不糟糕。坚持下去。