前序树遍历有效但后序无效

Question

我有两个函数遍历 preorder 和 postorder 中的树，每个函数都将节点中的值插入到数组中，然后返回数组。

但是，我的 postorder 功能不起作用。调用函数时出现分段错误。

编译以下代码并运行，但在调用 postorder 方法后出现分段错误。

这是我的代码：

int* preorder_recursive(node *root, int* dataArray)
{

  if (root == NULL)
    return dataArray;

  for (int i = 0; i < 512; i++)
  {
    if (dataArray[i] == INT_MIN)
    {
      dataArray[i] = root->data;
      printf("%d is being inserted to the preorder array at pos %d\n", root->data, i);
      break;
    }
  }

  preorder_recursive(root->left, dataArray);
  preorder_recursive(root->right, dataArray);
}

int* postorder_recursive(node *root, int *dataArray)
{
  if (root == NULL)
    return dataArray;

  postorder_recursive(root->left, dataArray);

  postorder_recursive(root->right, dataArray);

  for (int i = 0; i < 512; i++)
  {
    // any "empty" spots in the array should contain INT_MIN
    if (dataArray[i] == INT_MIN)
    {
      dataArray[i] = root->data;
      printf("%d is being inserted to the postorder array at pos %d\n", root->data, i);
      break;
    }
  }
}

调用时：

int * complete_pre_b = preorder_recursive(b, pre_order_b);
for(int i = 0; i < 3; i++)
{
    printf("pre b is %d\n", complete_pre_b[i]);
}

int * complete_post_b = postorder_recursive(b, post_order_b);
// here is the last print I see - code get till here fine
for(int i = 0; i < 3; i++)
{
    printf("post b is %d\n", complete_post_b[i]);
}

(注意 - 我的树有 3 个节点，所以我从 0 到 3 循环 i)

可能是什么问题？我的 post 和预购有什么不同？

Answer 1

注意你做的：complete_post_b = postorder_recursive(b, post_order_b); 当 complete_post_b 在 main 的开头定义为：int* complete_post_b;

但是，在 postorder_recursive 您没有 return 任何数据。所以当分配给 complete_post_b 它实际上是无效的。

你的 for 循环应该是：

for(int i = 0; i < 3; i++)
{
   printf("post b is %d\n", post_order_b[i]); // and not complete_post_b 
}

或者您可以 return dataArray 并使用 complete_post_b。

对于感兴趣的部分：为什么它只发生在 postOrder 上？

注意，你唯一一次 return dataArray 是节点为空的时候。我的猜测是在那种情况下，return 值的寄存器将包含数据数组。当在函数末尾调用递归函数时，数据数组的地址保留在寄存器中并向前传输 - 但你不能指望这一点，如果你想使用，你需要实际 return 地址它

前序树遍历有效但后序无效

Preorder tree traversal works but postorder doesn't

c

tree

segmentation-fault

tree-traversal