c - 通过 C 中的树向上传递值

Question

我正在用 C 编写一个简单的解析器，但我不确定在评估树时哪种方法是传递结果的最佳方式。

这是我当前的代码、节点结构和用于评估树的 walk 函数。

typedef struct node {
    struct node* left;
    struct node* right;
    void* data;
    Symbol type;
} node;

void* walk(node* n) {
    if (n != NULL) {

        if (n->type == plus) {

            int x = 0;
            int a = *(int*)walk(n->left);
            int b = *(int*)walk(n->right);

            x = a + b;

            return &x;

        } else if (n->type == number) {
            return (int*)n->data;
        }
    }
    return NULL;
}

从代码中您可以看到，当我将两个数字相加时，我将结果存储在一个局部变量中并将地址返回给该变量，我知道这是未定义的行为，所以我考虑使用 malloc 并更改我的代码对此:

int* x = malloc(1 * sizeof(int));
int a = *(int*)walk(n->left);
int b = *(int*)walk(n->right);

*x = a + b;

return x;

但是这段代码的问题是，我不确定释放我刚刚 malloc 的内存的最佳方法是什么。

我应该第二次走树并以这种方式释放所有内存，还是在我完成后释放内存的更好方法，或者有更好的方法在我的树中传播值？

Answer 1

无需第二次遍历树。请注意，在将 a 和 b 的值加到 x 之后，您不需要它们。所以你可以在添加后释放它们，这在@flu的答案中显示。此外，您可以在不为标志使用额外内存的情况下做到这一点。

注意:此代码将通过运行时错误来处理无效输入。为了处理这个错误，在访问指针之前检查 NULL 指针。

void* walk(node* n) {
    if (n != NULL) {
        if (n->type == plus) {
            int * x = malloc(sizeof(int));
            int * a = (int*)walk(n->left);
            int * b = (int*)walk(n->right);
            *x = *a + *b;

            free(a);
            free(b);

            return x;
        } else if (n->type == number) {
            int * val = malloc(sizeof(int)); //allocate dynamic memory for the leaf node so that all nodes can be freed without checking.
            *val = n->data;
            return val;
        }
    }
    return NULL;
}