1

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

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 保留在堆栈中。

编辑2：

这是代码：（返回 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 ？有人有想法吗？

谢谢 ！

4

2 回答 2

3

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

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

前缀（“根”）
  找到“C”？
    否：前缀（“A”）
      找到“C”？
        否：前缀（“C”）
           找到“C”？
              是：返回真
        （不检查前缀（“C”））：前缀（“D”）
           找到“C”？
              否：返回假
      前缀（“B”）
        找到“C”？
          否：前缀（“E”）
             找到“C”？
               否：返回假
          前缀（“F”）
             找到“C”？
               否：返回假
       返回假
  返回假

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

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

于 2011-07-07T00:03:55.470 回答
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;
}
于 2011-07-07T00:38:46.463 回答