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

Question

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

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

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

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

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

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;
}

Answer 3

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

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
       }
     }
   }