c - ある二分木を別の二分木にコピーする C プログラム

Question

あるバイナリ ツリーを別のバイナリ ツリーにコピーする C プログラムを手伝ってくれる人はいますか?

私は、アルゴリズムまたは C 関数のどちらでも問題ないので、それらを実装できます。

ありがとうございました ：）

Answer 1

追加したいツリーが適切なサブセット (オーバーラップなし) であり、ツリーのバランスを取る必要がない場合は、そのルート ノードを正しい挿入ポイントに追加するだけで済みます。つまり、次のような意味です。

  10
 /  \
1    70
 *
  5
 / \
2   7

の右側にリンクを作成して、1に添付できます5。サブツリー全体が と の間にあるため、これは機能します1(10これは、「重複しない」という意味です)。

実際、ツリーもソートされていない場合は、ルート ノードを必要なリーフにアタッチするだけです。

  40
 /  \
1    10
       *
        5
       / \
      8   789

その場合、ツリーはソートされていないため、オーバーラップは問題になりません。したがって、順序は気にしないと想定するのが安全な方法です。

ただし、バランスのとれた並べ替えられたツリーがある場合は、ツリーの 1 つをトラバースし、見つかった各値を他のツリーinsertに追加するメソッドを使用することをお勧めします。

これにより、「重複する」ツリーが適切に結合され、必要に応じてターゲット ツリーのバランスが保たれます。したがって、上記の最初の例を使用すると、次のようになります。

     7
    / \
   /   \
  2     10
 / \      \
1   5      70

「アルゴリズム」は次のようになります。

def copyTree (source, destination):
    item = source.first()
    while item != none_left:
        destination.insert (item.value)
        item = source.next (item)

insertそうすれば、宛先ツリーのメソッドが自動的に正しいこと (ソート、バランスなど) を行うため、アタッチメントが問題になるかどうかを心配する必要はありません。