c++ - 如何将 child 添加到 BST

Question

我正在尝试制作/创建 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;
}

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

否则你的 true 返回永远不会传播回第一个 return 之后，所以你总是返回 false 除非在唯一的情况下树的根实际上是您要搜索的节点。

此外，不要使用 == 比较两个 char 数组，除非 n->Q 实际上是一个 std::字符串。您应该使用 if(strcmp(n->Q, parentQ) == 0) 否则。

然而，您的第二段代码只是一团糟。您需要更好地了解您的 else if 到底会发生什么，看看它是否真的在做您想要的(提示:它不是)，因为您目前只执行最多 1 个代码块，即使不止一个条件为真。