3

2 つのバイナリ ツリーが本質的に同型であることを確認するアルゴリズムは何でしょうか? 私のコード-

boolean isIsomorphic(Root t1 , Root t2){
    if(t1==null || t2==null){
        return false;
    }

    if((t1.value == t2.value) && (isIsomorphic(t1.left,t2.right) && isIsomorphic(t1.right,t2.left))) {
        return true
    }

    return false; 
}
4

2 に答える 2

3

「同型」に関するウィキペディアの記事には、「2 つのオブジェクトが同型である場合、同型によって保持され、オブジェクトの 1 つに当てはまるプロパティは、他のオブジェクトにも当てはまる」と書かれています。

したがって、質問では、形状、データ、パフォーマンスなどを気にするかどうかを述べる必要があります.

検索用のバイナリ ツリーの動作が気になる場合、そのアルゴリズムは正しくありません。2 つの二分木が同形であるとはどういう意味ですか?を参照してください。

同型性をチェックする最も簡単な方法は、2 つのツリーを順番にトラバーサルし、各ステップの後に値をチェックすることです。

一方、形状とデータに関心がある場合は、@amis の修正がそれを取得します。ただし、完全一致と呼んでもかまいません。

最後に、形状のみを気にする場合は、チェックを外す必要がありますt1.value == t2.value

于 2012-04-27T15:19:58.293 に答える
0

ここから: 2 つの木 s と t は、s のノードのいくつかの左と右の子を交換することによって s を t に変換できる場合、準同形です。ノードの値は、準同形性を決定する上で重要ではなく、形状のみが重要です。

このリンクは、同形のこの定義のコードも提供します。

値が重要な場合、アプローチは次のようになります。

  1. 2 つのキューを使用して各ツリーのレベルごとのトラバーサルを実行する
  2. 両方のツリーにレベルを追加したら、キューのサイズを確認します。異なる場合は、「同形ではない」と報告してください
  3. それ以外の場合は、最初の最初のツリーで、そのレベルのすべてのノードをセットにデキューします。
  4. 2 番目のツリーでは、各ノードをデキューし、セットに存在するかどうかを確認します。
  5. セット メンバーシップ テストが失敗した場合は、'NOT ISOMORPHIC' を報告します。
  6. すべてのレベルを終了したら、ISOMORPHIC を報告します。
于 2013-03-27T23:50:35.463 に答える