在返回语句中使用&&

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

至少海事组织第一套声明：

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

...are确实比他们所需要的更令人困惑，所以我首先把它们简化一些。这基本上是在检查我们是否到达了一棵树或两棵树中的一个叶节点。如果树木是相同的“形状”，我们应该在同一时间到达叶节。因此，这意味着如果任何一个都是空指针，那么(从这里我们可以看到)，它们的形状是相同的当且仅当两者都是空指针。

但是，请注意，当我们在任何一棵树中达到一个空指针时，我们已经遍历了足够远--我们不需要再递归了。它们都是空指针(因此我们返回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是当且仅当两个子语句都返回true --也就是说，如果语句1为真，语句2为真。我们可以将其缩写为这样的逻辑and：

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

然而，传统上，C和C++使用&&作为逻辑和，这使我们回到了您最初发现的语法。

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

Answer 2

第一个if语句检查传递给函数的两个节点是否为NULL。(如果两者都为NULL，则同构因此返回true)。

第二个if语句检查传递给函数的一个节点是否为NULL。(在这种情况下，显然它们不是同构的，所以返回false。)

此时，函数知道传递给该函数的两个节点都不是空的。这意味着传递给函数的前两个节点是有效的(表示同构)。

但是你想知道的是整个树结构是否是同构的。在这里，最后一条返回语句发挥了神奇的作用。

最后一个返回语句是对函数本身的两个递归调用。第一个递归调用检查左侧节点是否为同构节点。第二个是右边的。

这个递归调用通过遍历节点来检查树中的所有节点。

我的建议是在笔记本上写一棵树，一步一步地执行代码，看看会发生什么。