c语言 - 将二叉树转换为每个节点下所有节点的总和的函数;如果我不创建新的二叉树，则分段错误

Question

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

3                       6
/                      / 
1   2  would turn into  1   2

有问题的练习链接：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;
}

问题是，如果我把一个->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 bytesn", 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 = %dn", node->valor);
}
}
static void print_tree(const char *tag, ABin node)
{
printf("Tree: %sn", 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()是你的"非工作"功能，稍微清理一下。我认为我没有显著改变这两个的功能。请注意，树构建代码并不试图使用函数来构建它——您还没有显示这样的函数。它创建三个节点并手动链接它们。

该代码在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;
}

我也不相信它需要返回一个值，所以有了一些附带的变化，你可以使用：

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

将测试扩展到更广泛的树，对于具有正确的树创建功能代码的人来说，这只是一项练习。