Обход дерева предзаказа работает, а постзаказ — нет

У меня есть две функции, которые обходят дерево в 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 узлами, поэтому я зацикливаюсь на i от 0 до 3)

В чем может быть проблема? В чем разница между моей почтой и предварительным заказом?


c tree segmentation-fault tree-traversal
person Uclydde    schedule 11.11.2018    source источник
comment
Это выглядит хорошо с алгоритмической точки зрения. Думаю, самое время привести минимальный, полный и лаконичный пример. . .   -  person gsamaras    schedule 11.11.2018
comment
Не могли бы вы опубликовать вариант использования, который не работает, и основной? (создание dataArray и использование функции) Возникает ли ошибка сегментации в начале функции или в середине? у вас вообще есть какие-нибудь отпечатки?   -  person dWinder    schedule 11.11.2018
comment
Я отредактировал сообщение, включив в него весь свой код @DavidWinder.   -  person Uclydde    schedule 11.11.2018
comment
@gsamaras Я соответствующим образом отредактировал сообщение.   -  person Uclydde    schedule 12.11.2018
comment
И именно поэтому вы получили ответ, хороший, хороший вопрос сейчас!   -  person gsamaras    schedule 12.11.2018

Ответы (1)


arrow_upward
1
arrow_downward

Обратите внимание, что вы делаете: complete_post_b = postorder_recursive(b, post_order_b); когда complete_post_b определяется в начале main как: int* complete_post_b;

Однако в postorder_recursive вы не возвращаете какие-либо данные. поэтому при присвоении 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 
}

Или вы можете вернуть dataArray и использовать complete_post_b.

Что касается интереса: почему это происходит только в postOrder?

Обратите внимание, что единственный раз, когда вы возвращаете dataArray, это когда узел имеет значение null. Я предполагаю, что в этом случае регистр для возвращаемого значения будет содержать массив данных. При рекурсивном вызове функции в конце вашей функции адрес массива данных остается в регистре и передается вперед, но вы не можете рассчитывать на это, и вам нужно фактически вернуть адрес, если вы хотите его использовать

person dWinder    schedule 11.11.2018
comment
Как мне изменить свой код, чтобы вернуть адрес, не нарушая всего? - person Uclydde; 12.11.2018
comment
@Uclydde, вы можете просто добавить return dataArray в конце функции, но я считаю, что лучше будет изменить функцию на void и использовать исходный массив в основном - person dWinder; 12.11.2018
comment
Добавление оператора return помогло! Большое спасибо! - person Uclydde; 12.11.2018