這個指針算法爲什麼不起作用？

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和當前字符指針。