3

だから、私は次のようになる明らかなブルートフォースアルゴリズムを持っています

int isSubtree (binTree *S, binTree *T)
{
    if (S == NULL)
        return 0;
    return (isEqual (S,T) || isSubtree (S->left, T) || isSubtree (S->right, T));
}

int isEqual (binTree *S, bintree *T)
{
    if (S==NULL && T==NULL)
        return 1;
    if (S==NULL || T==NULL)
        return 0;
    if (S->val == T->val)
        return isEqual(S->left,T->left) && isEqual (S->right,T->right);
    else
        return 0;
}

しかし、これは O(n²) アプローチです。

次のような別のアプローチがあります。これは O(n) です。最初のツリーを順番どおりにトラバースし、それを配列に格納します。次に、2 番目のツリーをトラバースし、順序どおりに格納します。ここで、2 番目の配列が最初の配列のサブ配列である場合は、先に進み、先行順序トラバーサルについても同じ手順を繰り返します。両方のクエリの結果が TRUE の場合、ツリーは最初のツリーのサブツリーです。そうでなければ、そうではありません。

次のアルゴリズムが機能するかどうか教えてもらえますか?

そして、この問題に対してよりスペースを最適化したソリューションはありますか?

注: 両方の配列のトラバーサルを保存しているので、2 つの配列が必要ですが、とにかく 1 つの配列でできることはありますか? ツリーの 1 つの順不同トラバーサルを格納し、その配列を使用して、他のツリーをトラバースしながらサブ配列の状態をチェックするように。それとも、余分なスペースはなく、O(n) 時間の複雑さでしょうか?

注: サブ配列とは、要素が連続して発生する必要があることを意味します。

{2,3,5} is a subarray of {1,2,3,5} but not a subarray of {1,2,3,4,5}
4

4 に答える 4

0

inorder traversal と DFS を使用できます (バイナリ ツリーでは、preorder traversal に縮小されます)。最初に DFS を使用して、両方のツリーのデータ構造を変更し、各ノードでその下のサブツリーの数を保存します。その後、両方のツリーの inorder traversal を記述し、文字列を KMP と照合します。O(n+m) (両方のツリーの n & m- ノード) では、さまざまなマッチングを見つけることができます。ハッシュを使用して、DFS で変更されたグラフに接続できます。KMP と一致するたびに、2 つの DFS 修正グラフを (サブツリーの数で) 比較できます。シーケンス全体でも一致する場合、それはサブツリーであり、そうでない場合は、KMP の別の一致に進みます。の上。

上記の例では、DFS 後の 'T' の変更されたデータ構造は [x(2);y(0);z(0)] & 'S' [x(3);y(0);z( 1);q(0)]。「T」の順序: yxz 「S」の順序: yxzq

一致する 'yxz' が得られます。次に、DFS の変更された構造に進みます。x に不一致があります。したがって、「T」は「S」のサブツリーではありません。

于 2013-12-28T04:37:16.557 に答える
0

深さ優先検索を実行して、すべてのノードでサブツリー ノードの数を保存し、ノード数が問題の他のツリーと同等である親のサブツリーのみを比較します。

于 2013-07-22T04:52:31.097 に答える
0

配列 {2,3,5} では、ルートは 2、または 3、または 5 になる可能性があるため、このような配列を使用してツリーを表すことはできません。

A が B のサブツリー (コードと同様) であり、leafs(x)左から右への「ツリー x の葉ノード」の配列であると仮定すると、leafs(A) は leafs(B) の部分文字列です。

上記のようにサブストリングを見つけたら、リーフからルートまでのノードをチェックして、それが本当にサブツリーであることを確認します。

于 2013-12-28T06:09:37.293 に答える