c++ - 在返回语句中使用 &&

Question

我正在查看一个函数示例，该示例显示两个二叉搜索树是否同构(具有相同的形状)。在示例中，它返回两个语句。我很难理解这意味着什么。

bool isomorphic(struct treenode *treeone, struct treenode *treetwo)  
{  
    if (!treeone && !treetwo)  
        return true;    
    if((!treeone && treetwo) || (treeone && !treetwo))  
        return false;  

    return (isomorphic(treeone->left, treetwo->left)  
        && isomorphic(treeone->right, treetwo->right));  
}  

我遇到麻烦的部分是最后一个返回语句。

以上代码来自这里:http://tech-queries.blogspot.com/2010/04/isomorphic-trees.html

Answer 1

至少 IMO，第一组陈述:

if (!treeone && !treetwo)  
    return true;    
if((!treeone && treetwo) || (treeone && !treetwo))  
    return false;  

...确实比他们需要的更令人困惑，所以我会先稍微简化一下。这基本上是在检查我们是否已到达一棵或两棵树中的叶节点。如果树的“形状”相同，我们应该同时到达两者的叶节点。所以，这意味着如果其中一个是空指针，那么(从我们现在可以看到的)当且仅当两者都是空指针时，它们是相同的形状。

但是请注意，一旦我们到达任一 树中的空指针，我们就已经遍历了足够远的地方——我们不需要进一步递归。它们要么都是空指针(因此我们返回 true)，要么其中一个是空指针而另一个不是(在这种情况下我们返回 false)。

不过，我们可以使该逻辑更加明显。我想我会这样写:

if ((treeone == nullptr) || (treetwo == nullptr))
    return treeone == treetwo;

如果执行超过了那个点，我们收到的指针都不是空指针。在这种情况下，当且仅当它们的两个子树都是相同的形状时，树才是相同的形状。 可以这样写:

if (!isomorphic(treeone->left, treetwo->left))
    return false;

if (!isomorphic(treeone->right, treetwo->right))
    return false

return true;

但是，我们返回 true当且仅当两个子语句都返回真时——也就是说，如果语句一为真并且语句二为真。我们可以将其缩写为合乎逻辑的 and像这样:

return isomorphic(treeone->left, treetwo->left) 
   and isomorphic(treeone->right, treetwo->right));

然而，传统上，C 和 C++ 使用 &&对于逻辑与，这让我们回到您最初找到它时的语法。

然而，对于当前的 C 编译器，如果您使用 and，则此代码应该编译(使用 && 而不是 #include <iso646.h>) .在当前的 C++ 中，您甚至不必这样做(尽管您可能必须使用一些特殊的命令行开关——例如，VC++ 需要 /Za)。