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)、反復が発生しない場合、結果は真であるということです。