algorithm - 2 つのツリーが与えられたとき、ツリーの 1 つが他のツリーのサブツリーであることをどのように確認しますか?

Question

2 つのツリーが与えられたとき、ツリーの 1 つが他のツリーのサブツリーであることをどのように確認しますか? これに最適なアルゴリズムを与えてください...そしてあなたが答えたものの順序も与えてください...

Answer 1

最初に頭に浮かぶのは、一方の木を横断し、その子のいずれかがもう一方の木の頭であるかどうかを確認することです。その後、逆にします。

それぞれの木の高さがわかれば、どちらの木が他の木のサブツリーである可能性があるかがわかるでしょう。

ツリーの他の詳細または特性（ソートされているかどうか、バランスが取れているかどうか）を知っている場合は、それらの特性を使用して、さらに高速なアルゴリズムを考え出すことができます。

Answer 2

双方向ツリーがあると仮定すると、このメソッドを 2 回呼び出すだけで、複雑さは O(k) になります。ここで、k=n+m で、n と m - 両方のツリーの高さです。

isSubtree(Node n1, Node n2){
   while(n2.parent != null){
      if(n2.parent == n1){
         return true;
      }
      n2=n2.parent;
   }
   return false;
}

訪問した親ノードを覚えていれば、さらにうまくいく可能性があります。

isParent(Node n1, Node n2){
   Set<Node> parents = new HashSet<Node>();
   parents.add(n1);
   parents.add(n2);
   while(n1.parent != null || n1.parent != null){
        if (parents.contains(n1.parent)){
            n1 is subtree of n2
        }
        if (parents.contains(n2.parent)){
            n2 is subtree of n1
        }
       parents.add(n1.parent);
       parents.add(n2.parent);
       n1=n1.parent;
       n2=n2.parent;
   }
   not a subtrees
}

Answer 3

できることは次のとおりです: isSubSet2 つのツリーのルートを取得するという関数があるとします。一方、isIdentical2 つのツリーが同一かどうかをチェックするという関数があります。

ツリー S がツリー T のサブセットであるかどうかを確認したいとします。T と S が同一の場合は同一であり、そうでない場合はisSubset関数を再度呼び出して S を調べます。しかし今回は、T の左部分木に対して T->Left および S を送信し、S の右部分木に対して T->Right および S を送信します。

コードと詳細については、こちらを参照してください。