c++ - 二叉搜索树根正在工作，但它不能有任何 child ？

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

在添加中，当您这样做时

root = new node;

root 是一个类变量，因此这不是问题，并且是正确的方法。但是，在 addRecursive 中，当您执行时

currentNode = new node;

currentNode 是一个按值传递给函数的指针，因此您只需使局部变量 currentNode 指向内存中的另一个位置。您需要通过引用传递指针，以便当您修改参数时，它会修改原始变量而不仅仅是局部变量。只需将函数 addRecursive 的签名设置为 void addRecursive(node*& currentNode, const string& newData) 即可。这将使指针通过引用传递给函数。

另请注意，我将 string newData 更改为 const string& newData。这样您就可以避免每次调用该函数时在内存中复制该字符串。当您不需要修改传递给函数的字符串拷贝时，您应该在所有函数中进行更改，以提高效率。