4

以下は、同じツリー (系統) の 3 つの同等の表現です。2 つのツリー表現が等しいかどうかを確認するアルゴリズムを見つけようとしています。ノード間の親子関係が類似している場合、ツリーは同等であると定義されます。

(Whale,(Seal,((Mouse,Rat),((((Carp,Loach),Frog),Chicken),Human))),Cow);
(Whale,(Seal,((Rat,Mouse),(Human,((Frog,(Loach,Carp)),Chicken)))),Cow);
((Seal,((Rat,Mouse),(Human,((Frog,(Loach,Carp)),Chicken)))), Cow, Whale);

誰でも方法を提案できますか？

4

3 に答える 3

8

1 つの方法は、子を辞書順 (または任意の厳密な弱い順序) で調べて比較することです。

于 2012-04-21T11:05:06.593 に答える
0

両方のツリーの順序順トラバーサルと後順トラバーサルをチェックします。それらが同じである場合、それらの 2 つのツリーは同じです

于 2012-04-22T13:49:28.753 に答える
0

各エッジを 2 回記述することができます。1 回は (a,b) として、もう 1 回は (b,a) として両方のツリーに記述できます。たとえば、(Mouse, Rat) に対して "Mouse : Rat" と "Rat : Mouse" の 2 つの文字列を作成し、これらすべての文字列を書き込み、辞書順に並べ替えて、2 つのリストを比較します。それらが同じなら、木は似ています。これは Andrew Tomazos のソリューションとは異なります。ツリーはそれ自体が下から上にトラバースされることに似ている、つまりエッジの反転をサポートするからです。

于 2012-04-21T11:08:33.030 に答える