Двоичный корень дерева поиска работает, но у него не могут быть дети?

Question

Итак, я пытаюсь создать свой собственный BST для проверки орфографии, потому что я хочу использовать дополнительную функциональность (найти подходящие узлы для предложений). В любом случае, я могу создать корневой узел, но после этого он не работает. Например, если у меня есть следующий код:

BST myTree; 
myTree.add("rootElement"); 
myTree.add("abcChild"); 

Если я корневой узел (* корень) общественности и проверить myTree.root-> левый = NULL ||! myTree.root-> right! = NULL, я получаю ошибку seg. Я не понимаю. Вот некоторые из моего кода:

struct node { 
    string data; 
    node *left; 
    node *right; 
}; 


void BST::add(string newData) 
{ 
    //Find a position                               
    if (root == NULL){ 
    root = new node; 
    root->data = newData; 
    root->left = NULL; 
    root->right = NULL; 

    } 
    else{ //remember to include string                           

    if(root->data.compare(newData) < 0){ 

     // Add to left                               

     addRecursive(root->left, newData); 

    } 
    else{ 
     // Add to right                              
     addRecursive(root->right, newData); 
    } 
    } 
} 


void BST::addRecursive(node *currentNode, string newData) 
{ 
    if (currentNode == NULL){ 

    currentNode = new node; 
    currentNode->data = newData; 
    currentNode->left = NULL; 
    currentNode->right = NULL; 

    } 
    else{ //remember to include string                         

    if(currentNode->data.compare(newData) < 0){ 

     // Add to left                             

     addRecursive(currentNode->left, newData); 

    } 
    else{ 
     // Add to right                             
     addRecursive(currentNode->right, newData); 
    } 
    } 
} 

В чем дело?

Answer 1

В add, когда вы

root = new node; 

root является переменной класса, так что это не проблема, и это правильный способ сделать это. Однако, в addRecursive, когда вы делаете

currentNode = new node; 

currentNode является указатель, который передается по значению вашей функции, так что вы только делаете локальную переменную currentNode точку в другое место в памяти. Вам нужно передать указатели по ссылке, чтобы при изменении параметра он изменял оригинал вместо локальной переменной. Просто сделайте подпись своей функции addRecursive до void addRecursive(node*& currentNode, const string& newData). Это заставит указатели быть переданы функции по ссылке.

Также обратите внимание, что я изменил string newData на const string& newData. Таким образом, вы избегаете делать копию строки в памяти каждый раз, когда вы вызываете эту функцию. Вы должны внести это изменение во все ваши функции, если вам не нужно изменять копию строки, переданной функции, для повышения эффективности.

Answer 2

В текущей реализации:

void BST::addRecursive(node *currentNode, string newData) 
{ 
    if (currentNode == NULL){ 

    currentNode = new node; 
    currentNode->data = newData; 
    currentNode->left = NULL; 
    currentNode->right = NULL; 
//WHERE DOES currentNode GOES ??   <----------- ??? currentNode was originally NULL, so 0... All NULL's are same. 
    } 
    else{ //remember to include string                         

    if(currentNode->data.compare(newData) < 0){ 

     // Add to left                             

     addRecursive(currentNode->left, newData); 

    } 
    else{ 
     // Add to right                             
     addRecursive(currentNode->right, newData); 
    } 
    } 
} 

попробовать что-то вроде этого:

struct node { 
     string data; 
     node *left; 
     node *right; 
    }; 


    void BST::add(string newData) 
    { 
     //Find a position                               
     if (root == NULL){ 
     root = new node; 
     root->data = newData; 
     root->left = NULL; 
     root->right = NULL; 

     } 
     else{ //remember to include string                           
      addRecursive(root, newData);  
     } 
    } 


    void BST::addRecursive(node *currentNode, string newData) 
    { 

     if(root->data.compare(newData) < 0){ 

      // Add to left                               
     if(currentNode->left != NULL){ 
      addRecursive(currentNode->left, newData); 
     }else{ 
     currentNode->left = new node; 
     currentNode->left->data = newData; 
     currentNode->left->left = NULL; 
     currentNode->left->right = NULL; 
     } 

     } 
     else{ 
      // Add to right                              
      //Implementation Symmetric to Left 
     } 
    } 
    } 

Answer 3

Попробуйте это:

struct node { 
    string data; 
    node *left; 
    node *right; 
}; 



void BST::add(string newData) 
{ 
     root = addRecursive(root, newData); 
} 


node* BST::addRecursive(node *currentNode, string newData) 
{ 
    if (currentNode == NULL){ 

    currentNode = new node; 
    currentNode->data = newData; 
    currentNode->left = NULL; 
    currentNode->right = NULL; 

    } 
    else{ //remember to include string                         

    if(currentNode->data.compare(newData) < 0){ 

     // Add to left                             

     currentNode->left = addRecursive(currentNode->left, newData); 

    } 
    else{ 
     // Add to right                             
     currentNode->right = addRecursive(currentNode->right, newData); 
    } 
    } 
    return currentNode; 
}