Поиск ошибки seg в рекурсивном коде для последующего преемника

Question

Эй, ребята, я просто практикую рекурсивный код на двоичном дереве поиска. Я получаю ошибку seg, но я не уверен, где проблема (возможно, что-то глупое смотрит мне прямо в лицо). У меня есть другие функции, которые работают нормально, как подсчет количества узлов или подсчет высоты дерева. Эта функция, в частности, дает мне проблемы. Я кодирую в 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-> равны моим темп-> данным (данные - это просто генерируемый случайным образом int).

Answer 1

Для вина односегментного, вы должны проверить, является ли 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; 
    } 
} 

Answer 2

Также

if(temp->left != NULL) 
    in_order_successor(root, temp->left); 

и

if(!temp-> left) 
    return temp->data;