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

Question

我有一个函数可以判断给定的二叉树 A 是否包含在给定的二叉树 B 中。该函数将“包含”定义为“A 被 B 或 B 的任何完整子树覆盖”。例如，如果树 A 是一棵空树而树 B 不是，那么 A 是否因此包含在 B 中？如果它们都是空的呢？

谢谢!

Answer 1

在数学意义上空集(树只是集合的特殊化)包含在所有其他集合中，包括其他空集。

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

Empty set 甚至有它的 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) 不会导致迭代，那么结果为真。