将值传递到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'd。

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

Answer 1

无需第二次遍历树。请注意，在将它们相加为x后，您不需要a和b的值。所以你可以在添加后释放它们，这在@ 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;
}

Answer 2

你可以添加一个额外的参数needToFree来通知调用者释放返回的指针。

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

            if( needToFreeA ) free(a);
            if( needToFreeB ) free(b);

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