这个指针算法为什么不起作用？

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和当前字符指针。