包含其他二叉树的二叉树

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)不会导致迭代，那么结果是真的。