c++ - 这个代码块到底是如何工作的[树]？

Question

下面的代码块究竟是如何工作的？更具体地说，程序如何知道返回哪个选项？

return    ancestor (node1->left(), node2)
           || ancestor (node1->right(), node2)
           || ancestor (node2->left(), node1)
           || ancestor (node2->left(), node1);

此代码块是遍历树的代码的一部分，以便在给定树中的 node1 和 node2 时确定一个节点是否是另一个节点的祖先。

请注意，node1 和 node2 被传递给负责确定是否存在可能的祖先/后代关系的函数:

bool ancestor (const Binary_node<Type> * node1, const Binary_node<Type> * node2)
{
         // .... code
}

Answer 1

How does the program know which option to return?

程序会不断尝试这些选项，直到找到一个可行的选项。

How exactly does the below code block work?

在每次调用 ancestor() 时，该函数将尝试四种可能性:

• 将 node1 移动到它的左子树，并尝试解决剩余的问题。
• 如果这不起作用，请尝试将 node1 移动到它的右子树。
• 如果这不起作用，则将 node2 移至其左子树。
• 如果这不起作用，则将 node2 移至其右子树。

如果所有四种可能性都失败，则节点 node1 和 node2 肯定没有祖先关系。

警告:除了非常小的树外，祖先函数在实现时非常慢。因为我们在每个 ancestor() 调用中尝试了四个选项，所以如果将树的高度增加 1，状态的数量大约会增加四倍。