c - 对树使用回溯

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 的路径时，此函数返回 R A B(对于 R 和 A，而不是 B)。

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

编辑:我现在更明白了， 我已经添加到函数中:
如果节点是叶子，则 pop()。 如果我搜索 F，它会返回 R A B F 而不是 R B F。我不知道如何避免将 A 保留在堆栈中。

编辑2:

这是代码:(返回 R A B F 而不是 R B F)

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 将允许您在适当的时间退出。