c - 为什么这个指针运算不起作用？

Question

在我的程序中，我有一个定义如下的二叉树:

struct node {
    char value; 
    struct node *left, *right;
};

在我的程序中，我试图编写一个函数，该函数按索引顺序(从上到下，从右到左遍历)返回每个节点值的字符串。

为了尝试这样做，我编写了以下函数:

char *to_string_util(struct node *root, char *str) {

    if (!root) return str;

    *str++ = root->value;

    // If not NULL
    if (root->left) to_string_util(root->left, str);
    if (root->right) to_string_util(root->right, str);

    return str;
}

这似乎应该有效，但遗憾的是，它没有。我已经通过使用数组索引让它工作了，它工作但不受欢迎，因为它需要引入另一个变量。

这是有效的版本:

char *to_string_util(struct node *root, char *str, int *cur_pos) {

    if (!root) return str;

    str[(*cur_pos)++] = root->value;

    if (root->left) to_string_util(root->left, str, cur_pos);

    if (root->right) to_string_util(root->right, str, cur_pos);

    return str;
}

给定树:

             +
           /   \
          *     *
         / \   / \
         a  a  b  b 

结果应该是:+*aa*bb

需要注意的一件事是，我在另一个函数中调用了这个函数，该函数在它的末尾附加了一个空字符，这应该不会影响输出，但我认为可能值得一提。

为什么使用数组索引的第二个版本有效，而第一个版本却不行？

Answer 1

它不起作用，因为您忽略了从递归子调用返回的 str 的新值。您的函数旨在更新 str 的值并通过执行 return str; 返回新值。而您只是丢弃了返回值。因此，在每个递归级别，对右子树的调用都会覆盖对左子树的递归调用所写入的数据。

这可能更接近你的想法

// If not NULL
if (root->left) str = to_string_util(root->left, str);
if (root->right) str = to_string_util(root->right, str);

当然，您应该记得在最后以零终止您的字符串。

---

如果你的函数以

开头

if (!root) return str;

那么递归子调用实际上不需要空检查，可以简化为

str = to_string_util(root->left, str);
str = to_string_util(root->right, str);

(除非您将其视为优化)。

---

您的基于索引的版本不再依赖于 str 的更新(并且根本不更新它)。这取决于位置值 *cur_pos 的更新。由于位置值是在不同级别的递归之间通过引用传递的，因此所有级别的递归都会看到这些更新。

您也可以在第一个版本中使用相同的技术，即通过引用传递您的指针值。但是为此，您必须将 str 作为 char **str (指向指针的指针)传递并使用 *str 和当前字符指针。