函数将二叉树变成每个节点下所有节点的总和；如果我不创建新的二叉树，则会出现分段错误

Question

我想创建一个函数来对某个节点下的所有节点求和，包括它自己的值，就像这样

  3                       6
 / \                     / \
1   2  would turn into  1   2

Link 到有问题的练习：https://codeboard.io/projects/16280

这里是ABin的定义和函数的调用：

typedef struct nodo {
    int valor;
    struct nodo *esq, *dir;
} *ABin;

ABin somasAcA (ABin a);

这是有效的版本，尽管我不喜欢它，因为它创建了一个新的二叉树：

int getsums(ABin a){
    int esq, dir;
    if(a == NULL) return 0;
    esq = getsums(a->esq);
    dir = getsums(a->dir);
    return(a->valor + esq + dir); 
}

ABin somasAcA (ABin a) {
    ABin b, *res;
    res = &b;

    if(a!=NULL){
        b = newABin(getsums(a), NULL,NULL);
        b->esq= somasAcA(a->esq);
        b->dir= somasAcA(a->dir);
    }
    if(a==NULL) b=NULL;
    return *res;
}

这是给我分段错误的版本：

ABin somasAcA (ABin a) {
    if(a == NULL) return NULL;
    a->valor = getsums(a);
    a->esq = somasAcA(a->esq);
    a->dir = (somasAcA(a->dir));
    return a;
}

问题是，如果我把 a->valor = getsums(a);在中间我没有得到 segfault （但如果树的高度高于 2，我得到错误的值）。是什么导致了这个分段错误，为什么我不能在不创建新的 bin 树的情况下执行此操作？谢谢。

Answer 1

当我们必须从程序片段创建 MCVE 时，这很麻烦。然而，这是可行的——虽然很痛苦，但可行。

这是我对您的代码的变体。在显示的 115 行中，有 35 行是您在问题中所写的——粗略。所以，我不得不创建两倍的代码来创建一个半可信的 MCVE。

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

typedef struct ABin_s *ABin;
struct ABin_s
{
    int valor;
    ABin esq;
    ABin dir;
};

ABin somasAcA_OK(ABin a);
int getsums(ABin a);
ABin somasAcA(ABin a);

static ABin newABin(int valor, ABin esq, ABin dir)
{
    ABin ab = malloc(sizeof(*ab));
    if (ab == 0)
    {
        fprintf(stderr, "Failed to malloc %zu bytes\n", sizeof(*ab));
        exit(EXIT_FAILURE);
    }
    ab->valor = valor;
    ab->esq = esq;
    ab->dir = dir;
    return ab;
}

int getsums(ABin a)
{
    if (a == NULL)
        return 0;
    int esq = getsums(a->esq);
    int dir = getsums(a->dir);
    return(a->valor + esq + dir);
}

ABin somasAcA_OK(ABin a)
{
    ABin b, *res;
    res = &b;

    if (a != NULL)
    {
        b = newABin(getsums(a), NULL, NULL);
        b->esq = somasAcA_OK(a->esq);
        b->dir = somasAcA_OK(a->dir);
    }
    if (a == NULL)
        b = NULL;
    return *res;
}

ABin somasAcA(ABin a)
{   // Remove unused b
    if (a != NULL)
    {
        a->valor = getsums(a);
        a->esq = somasAcA(a->esq);
        a->dir = somasAcA(a->dir);
    }
    return a;
}

static void print_postorder(ABin node)
{
    if (node != 0)
    {
        print_postorder(node->esq);
        print_postorder(node->dir);
        printf("Valor = %d\n", node->valor);
    }
}

static void print_tree(const char *tag, ABin node)
{
    printf("Tree: %s\n", tag);
    print_postorder(node);
}

static void free_tree(ABin node)
{
    if (node != 0)
    {
        free_tree(node->esq);
        free_tree(node->dir);
        free(node);
    }
}

int main(void)
{
    ABin root = newABin(3, 0, 0);
    ABin esq = newABin(1, 0, 0);
    ABin dir = newABin(2, 0, 0);
    root->esq = esq;
    root->dir = dir;

    print_tree("Before", root);

    ABin eval = somasAcA(root);
    assert(eval == root);

    print_tree("After", root);

    eval = somasAcA_OK(root);
    assert(eval != root);

    print_tree("Second time", root);

    free(root);
    free(esq);
    free(dir);
    free_tree(eval);
}

我根据您的工作函数创建了 somasAcA_OK()，略微清理了它。我的 somasAcA() 是您的 'non-working' 函数，稍微清理了一下。我不认为我显着改变了两者的功能。请注意，树构建代码不会尝试使用函数来构建它——您还没有显示这样的函数。它创建三个节点并手动链接它们。

代码在 Mac OS X 10.11.5 上的 GCC 6.1.0 下使用命令行编译干净：

$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
>     -Wold-style-definition -Werror abin.c -o abin
$

当运行低于 valgrind 时，它获得了干净的健康证明。

$ ./abin
Tree: Before
Valor = 1
Valor = 2
Valor = 3
Tree: After
Valor = 1
Valor = 2
Valor = 6
Tree: Second time
Valor = 1
Valor = 2
Valor = 6
$

根据我所见，你的第二批代码，即你声称失败的代码，工作正常，但你声称成功的代码实际上并没有进行加法（最后 valor第二次应该是9）。

我对你的函数的工作方式有点怀疑。我希望 somasAcA() 在对修改后的树求和之前评估子树。它起作用可能是最小树的副作用。也许你应该使用：

ABin somasAcA(ABin a)
{
    if (a != NULL)
    {
        a->esq = somasAcA(a->esq);
        a->dir = somasAcA(a->dir);
        a->valor = getsums(a);
    }
    return a;
}

我也不认为它需要 return 一个值，因此通过一些附属更改，您可以使用：

void somasAcA(ABin a)
{
    if (a != NULL)
    {
        somasAcA(a->esq);
        somasAcA(a->dir);
        a->valor = getsums(a);
    }
}

将测试扩展到更广泛的树留给具有正确树创建函数代码的人作为练习。

函数将二叉树变成每个节点下所有节点的总和；如果我不创建新的二叉树，则会出现分段错误

Function to turn a Binary Tree into the sums of all nodes below each node; segmentation fault if I don't create a new binary tree

c

tree

binary-tree

segmentation-fault