バイナリ検索ツリー - 別のツリーに1つのツリーをコピーする

Question

私はキーと文字列を含むエントリを持つBSTを持っています。 私はツリーを作って値を移入し、その値を別のツリーにコピーしたいと思っています。私が持っている唯一の機能は、共通バイナリ検索ツリー関数とイテレータBegin（）とEnd（）です。

ダイレクトコピー機能を使用せずにこれを行うにはどうすればよいですか？コピー（T1、T2）？

私は理論的に、実際のコードの実装方法を探しています。

Answer 1

あなたが持っている唯一の機能は、イテレータと終了イテレータを開始し、検索、挿入、削除されている場合は、あなたの唯一のオプションは、個別の宛先ツリーに各値を挿入し、最初のツリーを反復することであろうように、それが聞こえます。しかし、これらのイテレータが要素を順番に返すと、ツリーが自己平衡化されない場合、コピーすると結果のツリーはスティックになります。 （つまり、完全にアンバランスになります）。イテレータがpre-orderまたはbreadth firstという値を返す場合、これは問題ではありません。

など。以下のツリーを考える：イテレータはシーケンス1, 2, 3 ... 7を返された場合

 4 
    /\ 
/ \ 
    2  6 
/\ /\ 
1 3 5 7 

、空の木にその順序でそれらを挿入すると、以下を生成します：

1 
\ 
    2 
    \ 
    3 
    \ 
     4 
     \ 
     5 
     \ 
      6 
      \ 
      7 

プリオーダーのイテレータは4, 2, 1, 3, 6, 5, 7を返しますが、呼吸優先イテレータは4, 2, 6, 1, 3, 5, 7を返し、これらの挿入命令のいずれかが元のツリーを再現します。