c++ - 包含其他二叉树的二叉树

Question

我有一个函数应该告诉给定的二叉树 A 是否包含在给定的二叉树 B 中。该函数将“包含”定义为“A 被 B 覆盖，或 B 的任何完整子树”。例如，如果树 A 是一棵空树而树 B 不是，那么 A 会包含在 B 中吗？如果两个都是空的呢？

谢谢！

Answer 1

在数学意义上，空集（树只是集合的特化）包含在每个其他集合中，包括其他空集。

所以对你的两个问题都是肯定的。

空集甚至有它的 wiki：http ://en.wikipedia.org/wiki/Empty_set

---

无论如何，从您的实现中可以明显看出，空树包含在所有其他树中，示例实现如下所示：

bool Tree::contains(const Tree& otherTree)
{
   for (n: otherTree)
   {
      if (!contains(n)) 
         return false;
   }
   return true;
} 

当然，我可以想象更好的实现，尤其是在对树进行排序时 - 但关键是如果for(n: otherTree)不会导致迭代，那么结果是正确的。