使用回溯树

Question

由于堆栈（带有推入和弹出），我在树中使用回溯算法。 它有效，但我有一个问题。堆栈给出的路径是“错误的”。

bool Prefix(Node*root, stack *tas, char *search)
{
    if (!isEmpty(root))
    {
        if (strcmp(search,root->data) != 0)
            push(tas, root->data, search, root);

        if (strcmp(search,root->data) == 0)
        {
            return True ;
        }

        Prefix(root->left, tas, search);
        Prefix(root->right, tas, search);
    }
    return False;
}

例如，我有一棵树：

     Root
    /    \    
   A      B
  / \    / \
 C   D  E   F    

例如，当我想要 C 的路径时，此函数返回 RAB（适用于 R 和 A，而不是 B）。

我不知道它是来自这个函数还是push()函数。 如果您在函数中没有看到任何错误，我将粘贴push()，但它很长。

编辑：我现在更好理解了， 我已添加到该功能：
如果节点是叶子，则 pop()。 如果我搜索 F，它会返回 RABF 而不是 RB F。我不知道如何避免将 A 保留在堆栈中。

edit2：

这里是代码：（返回 RABF 而不是 RBF）

bool Prefix(Node*root, stack *tas, char *search)
{
    if (!isEmpty(root))
    {
        if (strcmp(search,root->data) == 0)
            return True ;

        if (LeafOrNot(root) == True ){  //it's a leaf, pop()
            pop(tas);

        if (Prefix(root->left, tas, search))
            return True;
        if (Prefix(root->right, tas, search))
            return True;
    }
    return False;
}

我不明白如何弹出遍历子节点以获得好的结果，也许添加 if (Prefix(root->left, tas, search)) 的 else ？有人有主意吗？

谢谢 ！

Answer 1

至少有一个问题是您没有检查对 Prefix 调用的返回值，因此您不知道递归调用是否“完成”（并且您应该停止探索）。

查看此情况的一个简单方法是遍历函数调用（给定示例树）：

Prefix("Root")
  found "C"?
    no: Prefix("A")
      found "C"?
        no: Prefix("C")
           found "C"?
              yes: return true
        (without check of Prefix("C")): Prefix("D")
           found "C"?
              no: return false
      Prefix("B")
        found "C"?
          no: Prefix("E")
             found "C"?
               no: return false
          Prefix("F")
             found "C"?
               no: return false
       return false
  return false

这显示了调用的顺序和缩进大致与调用堆栈上的帧相对应。

您可以看到，检查对 Prefix 的调用是否返回 true 将允许您在适当的时间退出。

Answer 2

我必须同意@Mark Elliot 的观点，但乍一看，他的答案可能看起来令人困惑。您确实需要一个停止条件，这样您就不会继续探索其他节点并将它们添加到堆栈中。您将返回一个布尔值，以便您可以使用它来测试调用是否找到您要查找的节点。

如果您打算将 C 路径中的最后一个节点包含在堆栈中，那么您应该在添加到堆栈时删除字符串比较。

例如，你可以这样做。

bool Prefix(Node*root, stack *tas, char *search)
{
    if (!isEmpty(root))
    {
        push(tas, root->data, search, root);

        if (strcmp(search,root->data) == 0)
        {
            return True;
        }

        if (Prefix(root->left, tas, search))
            return True;
        if (Prefix(root->right, tas, search))
            return True;
    }
    return False;
}