Нахождение ошибки сегмента в рекурсивном коде для преемника наследования
Эй, ребята, я просто практикую рекурсивный код в бинарном дереве поиска. Я получаю ошибку сегмента, но я не уверен, где проблема (вероятно, что-то глупое, уставившее меня прямо в лицо). У меня есть другие функции, которые работают нормально, например, подсчет количества узлов или подсчет высоты дерева. В частности, эта функция доставляет мне неприятности. Я пишу на C ++.
//wrapper function
int table::in_order_successor()
{
node * temp;
temp = root;
in_order_successor(root, temp);
}
//Find the in-order successor
int table::in_order_successor(node * root, node * temp)
{
if(root == NULL) return 0;
if(root->right != NULL)
if(root->data == temp->data)
in_order_successor(root, temp->right);
in_order_successor(root, temp->left);
return temp->data;
}
У меня была идея сделать так, чтобы функция однажды пошла вправо от корня, а затем продолжила влево как можно дальше. Чтобы заставить его работать сразу, я хочу идти правильно, только если мои root-> data равны моим temp-> data (данные являются просто случайно сгенерированным int).
Решение
Для ошибки сегмента, вы должны проверить, temp является null, как ваш код может пройти temp->right а также temp->left к нему, который может быть null,
if(temp == NULL) return 0; // add this check
Но в вашем коде есть еще одна проблема: вы никогда не используете возвращаемое значение. Тогда это будет просто повторяться. Предположим, что вы хотите вернуть данные, сохраненные в листовом узле после обхода, тогда код может выглядеть так:
//Find the in-order successor
int table::in_order_successor(node * root, node * temp) {
if(root == NULL) return 0;
if(temp == NULL) return 0; // add this check
if(root->right != NULL) {
// check by pointer instead of the data unless each
// node->data is unique. Otherwise unwanted moving
// right will occur.
if(root == temp) {
if (temp->right != null) {
// use `return` here instead of plain function call to get
// the update of the rest of the recursion.
return in_order_successor(root, temp->right);
}
}
}
if (temp->left != null) {
// if have left child, return what you will find in the next step
return in_order_successor(root, temp->left); // use return here
} else {
// reach the left-most leaf after first steping right at root node.
return temp->data;
}
}
Другие решения
Также
if(temp->left != NULL)
in_order_successor(root, temp->left);
а также
if(!temp-> left)
return temp->data;