0

我正在尝试制作/创建 BST，但它似乎无法正常工作。我已经坐在这里好几个小时试图弄清楚发生了什么。它已经到了我已经绘制了一百万张图表来解决这个问题的地步，但是我的代码让我失败了。我需要将根节点传递给函数。然后我需要遍历树，直到我发现函数的父字符串参数与树父节点的字符串重合。如果我找到它，我必须将字符串插入父级，并从该父级创建两个新子级。如果找不到父字符串，则返回 false。

 bool insertNode(BSTNode *n, char* parentQ, char* leftQ, char* rightQ)
 {   
  if(n->Q == parentQ)
  {
    n->left = new BSTNode(leftQ);
    n->right = new BSTNode(rightQ);
    return true;
  }
  else if(n->Q != parent)
  {
    insertNode(n->left,parentQ,leftQ,rightQ);
    insertNode(n->right,parentQ,leftQ,rightQ);
  }
  else
    return false;
}

此外，我需要制作另一种方法来获取我建立的树并更正字符串。因此，该方法修改父字符串（如果找到），并查看其子字符串（如果找到），并将这些字符串替换为在方法参数中找到的字符串。这有点像添加一个子树而不把整个树搞砸。提前致谢！

bool changeNode(BSTNode *n,char* parentQ, char* leftQ, char* rightQ)
{
  if(n->Q == leftQ)
  {
    n->Q = parentQ;
    n->left = new BSTNode(leftQ);
    n->right = new BSTNode(rightQ);
    return true;
  }
  else if(n->Q == rightQ)
  {
    n->Q = parentQ;
    n->left = new BSTNode(leftQ);
    n->right = new BSTNode(rightQ);
    return true;
  }
  else if(n->Q != leftQ)
  {
    changeNode(n->left,parentQ,leftQ, rightQ);
  }
  else if(n->Q != rightQ)
  {
    changeNode(n->right,parentQ,leftQ,rightQ);
  }
    return false;
}
4

1 回答 1

1

您甚至没有提到错误是什么，例如输入/预期输出，但是在使用这些孩子调用函数之前，您不应该检查当前节点是否真的有左右孩子吗？

else if(n->Q != parentQ) // <--- you have a typo in this line, "parent"
  {                      //      (and you don't even need the 'if')
    insertNode(n->left,parentQ,leftQ,rightQ);
    insertNode(n->right,parentQ,leftQ,rightQ);
    // in this case you return nothing! corrupted return value
  }

^ 这似乎很容易出错，尤其是空指针。你应该把它变成这样的东西：

    else
      {
        if(n->left != NULL) // take a look at nullptr if you have C++11
          if(insertNode(n->left,parentQ,leftQ,rightQ)) return true;
        if(n->right != NULL)
          if(insertNode(n->right,parentQ,leftQ,rightQ)) return true;
        return false;
      }

否则，您的truereturn 永远不会传播回 first return，因此您总是会返回false，除非在树的根实际上是您正在搜索的节点的唯一情况下。

此外，不要char使用 比较两个数组==，除非n->Q它实际上是一个std::string. 你应该使用if(strcmp(n->Q, parentQ) == 0)其他方式。

但是，您的第二段代码只是一团糟。您需要更好地了解您else if的 's 上究竟会发生什么，看看它是否真的在做您想要的（提示：它不是），因为您目前最多只执行 1 个代码块，甚至如果多个条件为真。

于 2013-06-04T04:46:43.893 回答