c - C 中的二叉树练习

Question

我在大学接到了一项作业，我们必须解决以下练习:

在这个问题中，我们考虑给定一个正整数 n，形式为加法表达式

n = 1 ± 2 ± 3 ± 4 ± ... ± n − 2 ± n − 1 ± n

例如，对于 n = 5，以下两个表达式是该形式的唯一有效表达式:

• 5 = 1 + 2 + 3 + 4 − 5
• 5 = 1 − 2 − 3 + 4 + 5

编写一个程序，其输入接受整数 n(其中 0 < n < 30)并输出计算结果为 n 的上述形式的表达式的数量。

现在我知道我应该寻找一个带有循环和递归的二叉树。但是我们还没有对指针做太多事情，我真的不知道从哪里开始或如何构建这样的二叉树。也许有一个技巧，程序不必那么复杂，但我还没有找到捷径。有什么建议吗？

Answer 1

我觉得自己很慷慨。我不会给你递归的答案，我会使用 bit bashing，所以如果你能自己弄清楚这一点并将其更改为递归，我认为你已经学到了足够多的东西，不会欺骗自己。如果你确实复制了这个逐字，你的教授就会知道你作弊了。

    int n = 5;
    int i,j,c;

    for (i=0;i<(1<<n);i++)
    {
        c = 0;
        for (j=1;j<=n;j++)
        {
            if (i&(1<<(j-1))) {c+=j; printf("+%d",j); }
            else { c-=j; printf("-%d",j); }
        }
        if (c == n) printf(" = %d\n",n);
        else printf(" != %d\n",n);
    }

输出为:

-1-2-3-4-5 != 5
+1-2-3-4-5 != 5
-1+2-3-4-5 != 5
+1+2-3-4-5 != 5
-1-2+3-4-5 != 5
+1-2+3-4-5 != 5
-1+2+3-4-5 != 5
+1+2+3-4-5 != 5
-1-2-3+4-5 != 5
+1-2-3+4-5 != 5
-1+2-3+4-5 != 5
+1+2-3+4-5 != 5
-1-2+3+4-5 != 5
+1-2+3+4-5 != 5
-1+2+3+4-5 != 5
+1+2+3+4-5 = 5
-1-2-3-4+5 != 5
+1-2-3-4+5 != 5
-1+2-3-4+5 != 5
+1+2-3-4+5 != 5
-1-2+3-4+5 != 5
+1-2+3-4+5 != 5
-1+2+3-4+5 = 5
+1+2+3-4+5 != 5
-1-2-3+4+5 != 5
+1-2-3+4+5 = 5
-1+2-3+4+5 != 5
+1+2-3+4+5 != 5
-1-2+3+4+5 != 5
+1-2+3+4+5 != 5
-1+2+3+4+5 != 5
+1+2+3+4+5 != 5