c - 为树添加值

Question

我正在尝试向二叉搜索树添加值，为此我编写了两个函数，一个创建新节点，另一个将这些值插入树所以这是代码

typedef struct Node {

    void *data;
    struct Node *left;
    struct Node *right;
} Node;

 Node *createNode(void *data,size_t s){

    Node *newNode = (Node *)malloc(s * sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}


void addValueBt(Node ** node, void *data, size_t s,int (* compar)(const void *, const void *)){

    if (*node == NULL)
      *node = createNode(data,s);
    else if (compar((*node)->data,data) > 0)
                 addValueBt(&(*node)->left, data, s, compar);
    else
        addValueBt(&(*node)->right, data, s, compar);
}

当我用两种不同的方式在 main 中调用 addValueBt 时(但通常看起来是一样的)我没有得到相同的结果

第一种方式:

int main(){

    Node *root = NULL;
    for(int i = 0; i < 10; i++)
        addValueBt(&root, &i, 1, myCompar);
    printBt(root,print);//print the whole tree
}

显示器给出了这个:

10
10
10
10
10
10
10
10
10
10

第二种方式:

int main(){

 int a = 8, b = 9, c = 5, d = 1;
 addValueBt(&root, &a, 1, myCompar);  
 addValueBt(&root, &b, 1, myCompar);
 addValueBt(&root, &c, 1, myCompar);
 addValueBt(&root, &d, 1, myCompar);
 printBt(root,print);

}

显示:

1
5
8
9

"myCompar"比较两个整数

我的问题是:为什么当我们在循环中使用函数“addValueBt”时它不起作用？(通常它应该给出与另一个相同的结果)

Answer 1

主要问题

作为user3386109在 comment 中正确指出，主要问题是您存储的是指向树中数据的指针，而不是数据的副本。所有节点最终都指向同一位置，因此当该位置发生变化时，树指向的值会同时在所有节点中发生变化。

次要问题

在一组评论中(其中一些是对 Yasmine 的评论问题的回复，OP)，我注意到:

This is tangential to your main problem, but the parameter s is initially confusing. It's always 1 because you only allocate one node at a time. If it was larger, you'd waste the extra space that createNode() does allocate but does not initialize. You could stop using s (assume 1) without causing problems in the visible code.

I mean that in Node *createNode(void *data, size_t s) { Node *newNode = (Node *)malloc(s * sizeof(Node));, you allocate an array of Node structures of the size given by s. However, you initialize only the first structure allocated, and you don't record the size of the array anywhere. This doesn't matter because if you track the calls from main() to addValueBt() to createNode(), the value of s is always 1. But because it is always 1, you really have no need to pass it, so you can simplify the calls all the way down the calling chain.

Note that @user3386109: has identified the problem. You store the same pointer in each element of the tree, so when the pointed at value changes, all the elements of the tree change at the same time. And if the pointed at value goes out of scope, you get undefined behaviour. You either need to make a copy of the data in the createNode() function, which means that you need to know how big the data is so that you can allocate new space to store it, or you need to ensure that a different pointer is passed to the code each time, and those pointers remain valid until the tree is freed.

You can see with your working code, you pass a different pointer each time (a pointer to a different variable). When you repeatedly pass a pointer to the same variable, the same address is stored, so the current value stored at that address is used by all the nodes; they all have the same value.

Part of the problem comes from using void *data; instead of a simple int data;. For the immediate purposes, life would be much, much simpler if your data structure used int data;. You'd have:

Node *createNode(int key)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data; newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

If you store void *, you really need to know how long the data you're storing pointers to is, so that you can make copies, etc. Your comparator can make assumptions about the length (and you'll be OK as long as those assumptions are correct). So, you'd need:

Node *createNode(void *data, size_t len)
{
    void *copy = malloc(len);
    memmove(copy, data, len);
    Node *newNode = (Node *)malloc(s * sizeof(Node));
    newNode->data = copy;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Yasmine 评论道:

I know but I have to do that so that it can be used with other types like float or char.

那时，我开始生成下面的代码。

工作代码

这是一个处理我评论中提出的要点的产品。

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

typedef struct Node
{
    void *data;
    size_t datalen;
    struct Node *left;
    struct Node *right;
} Node;

static int cmp_dbl(const void *p1, const void *p2);
static int cmp_int(const void *p1, const void *p2);
static void freeBt(Node *node);
static void printBt(Node *node, void (*print)(const void *));
static void print_dbl(const void *p);
static void print_int(const void *p);

extern Node *createNode(void *data, size_t len);
extern void addValueBt(Node **node, void *data, size_t len, int (*compar)(const void *, const void *));

Node *createNode(void *data, size_t len)
{
    void *copy = malloc(len);
    // Error check allocation!
    memmove(copy, data, len);
    Node *newNode = (Node *)malloc(sizeof(*newNode));
    // Error check allocation!
    newNode->data = copy;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->datalen = len;
    return newNode;
}

void addValueBt(Node **node, void *data, size_t len, int (*compar)(const void *, const void *))
{
    if (*node == NULL)
        *node = createNode(data, len);
    else if (compar((*node)->data, data) > 0)
        addValueBt(&(*node)->left, data, len, compar);
    else
        addValueBt(&(*node)->right, data, len, compar);
}

int main(int argc, char **argv)
{
    unsigned seed = time(0);
    if (argc == 2)
        seed = atoi(argv[1]);
    srand(seed);
    printf("Seed: %u\n", seed);

    Node *root = NULL;
    for (int i = 0; i < 10; i++)
        addValueBt(&root, &i, sizeof(i), cmp_int);
    printBt(root, print_int);
    freeBt(root);

    root = NULL;
    for (int i = 0; i < 10; i++)
    {
        double d = (double)rand() / RAND_MAX * 1000.0 + (double)rand() / RAND_MAX;
        addValueBt(&root, &d, sizeof(d), cmp_dbl);
    }
    printBt(root, print_dbl);
    freeBt(root);

    return 0;
}

static int cmp_int(const void *p1, const void *p2)
{
    int v1 = *(int *)p1;
    int v2 = *(int *)p2;
    return (v1 > v2) - (v1 < v2);
}

static int cmp_dbl(const void *p1, const void *p2)
{
    double v1 = *(double *)p1;
    double v2 = *(double *)p2;
    return (v1 > v2) - (v1 < v2);
}

static void print_int(const void *p)
{
    printf("%d\n", *(int *)p);
}

static void print_dbl(const void *p)
{
    printf("%8.3f\n", *(double *)p);
}

static void printBt(Node *node, void (*print)(const void *))
{
    if (node != 0)
    {
        printBt(node->left, print);
        print(node->data);
        printBt(node->right, print);
    }
}

static void freeBt(Node *node)
{
    if (node != 0)
    {
        freeBt(node->left);
        freeBt(node->right);
        free(node);
    }
}

这是一个运行示例:

Seed: 1511037421
0
1
2
3
4
5
6
7
8
9
  87.907
 118.694
 140.163
 170.833
 343.940
 412.792
 422.254
 530.731
 557.656
 936.981

发生了什么变化？

我将参数 s 丢给了 addValueBt() 和 createNode()，但添加了一个参数 size_t len。这定义了数据的长度。长度存储在Node结构中的size_t datalen中。

createNode() 中的代码复制了传递给它的数据，并将该副本存储在树中。这确保每个节点都不会受到调用代码中值更改的影响。

添加了什么？

我为 int 比较器添加了代码(你叫你的 myCompar()；我叫我的 cmp_int() 因为我也想使用 double) 和 double 比较器 cmp_dbl()。我添加了打印函数 print_int() 和 printf_dbl() — 将您的 print 重命名为 print_int。我添加了内存释放函数freeBt()。我为 printBt() 添加了代码。

使用命令行参数的代码允许您指定您选择的种子。这有点草率；我可能应该使用 strtoul() 而不是 atoi()。但它允许您在命令行上指定一个数字作为种子，这将在您需要时为您提供可重复性。种子已报告，因此您可以重现结果。这在玩随机数时很有用——有时您想要随机性，有时您想要可重复性。

我没有做的事

我没有修复打印代码，以便树的结构可见。您只会得到一个数字列表。

代码并没有真正使用结构的datalen成员，但是检查一致性或记录字符串的长度可能很有用。