2

一般的なツリーから一意の二分木を構築できることは知っていますが、その逆は本当ですか？つまり、二分木から一意の一般的なツリーを取得できますか？

4

2 に答える 2

2

はい。次の変換は可逆的です。

順序付けられているがインデックス付けされていない子を持つ一般的なツリーが与えられた場合、最初の子をその親の左の子としてエンコードし、他の各ノードをその（元の）兄弟の右の子としてエンコードします。

逆は次のとおりです。左右の子が区別される二分木がある場合、ノードの左の子を最初の子として読み取り、右の子を次の兄弟として読み取ります。

だから、次の木

  a
 /|\
b c d

としてエンコードされます

  a
 /
b
 \
  c
   \
    d

次の木が

   a
  / \
 b   c
 |
 d

としてエンコードされます

     a
    /
   b
  / \
 d   c

（読み取り：はのd最初の子でありb、cの兄弟ですa）。

ルートに兄弟を割り当てることで、ルート化されたフォレストをエンコードできることに注意してください（順序付けられたコンポーネントを使用します。そうでない場合、表現は一意ではありません）。

  a
 / \
b   c
 \   \
  d   e

として読み取られます

  a   c e
 / \
b   d

バイナリツリーから一意の一般的な（無向の）ツリーを取得する別の方法は次のとおりです。

  • 頂点二分木には、0...3個の隣接するグラフが含まれる場合があります。
  • ルートに12ノードを追加します
  • 左の各子に8つのノードを追加します
  • 各右の子に4つのノードを追加します

この操作は元に戻すことができます。

  • ノードに少なくとも12個のネイバー「ルート」のラベルを付けます。一意でない場合は、失敗します。
  • 各ノードに8..11ネイバー「左」のラベルを付けます。
  • 各ノードに4..7ネイバー「右」のラベルを付けます。
  • すべての葉を削除します
  • すべてのエッジをルートから遠ざけるように向けます
  • いずれかのノードに複数の左の子または複数の右の子がある場合、失敗します。

それで、

  • 順序付けられたルートツリーとバイナリツリーの間には全単射があります（1番目と2番目のアルゴリズム）。
  • 一般的なツリーは任意にルート化できるため、一般的な（有向または無向）ツリーから二分木への注入があります。
  • 二分木から一般的な無向木への注入があります（3番目のアルゴリズム）
  • 二分木から一般的な木へ、そしてその逆への注入があるので、一般的な（有向または無向）木と二分木の間に全単射が存在しなければなりません。
于 2012-10-20T15:29:25.103 に答える
1

ありそうもない。通常、二分木は左の子と右の子を区別します。ただし、一般的な木はそうではありません。

これらの2つの二分木から一意の一般的なツリーを取得するにはどうすればよいですか。

  X      X
 / \    / \
 Y Z    Z Y

そして、これら2つはどうですか？

  X      X
 /        \
 Y        Y

一方で、

二分木の左または右の子を区別しないことを選択した場合、または子が一般的なツリーに表示されるシーケンスを尊重することを選択した場合は、各二分木をそれ自体にマップするだけです。これは、各二分木に固有の一般的なツリーになります。

于 2012-10-20T15:19:05.033 に答える