二叉搜索樹 - 複製一棵樹到另一棵樹

Question

我有一個BST，其中包含一個鍵和字符串的條目。 我製作了一棵樹並填充了它的值，並且想要將它的值複製到另一棵樹中。我唯一的功能是常見的二進制搜索樹函數和迭代器Begin（）和End（）。

我該怎麼做，而不使用直接複製功能，即。複製（T1，T2）？

我只是在尋找理論上的方法，而不是實際的代碼實現。

Answer 1

如果你擁有的唯一功能是搜索，插入，刪除，開始迭代和結束迭代器，那麼它聽起來像你唯一的選擇是遍歷第一棵樹，分別將每個值到目標樹。但是要注意，如果這些迭代器按順序返回元素，並且樹不是自平衡的，那麼當複製時，生成的樹將成爲一個棒。 （即它將完全不平衡）。如果你的迭代器返回值pre-order或breadth first那麼這不是一個問題。

E.g.考慮下面的樹：

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

如果迭代器返回的序列1, 2, 3 ... 7，將它們依次爲空樹將產生如下：

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

然而預購迭代器將返回4, 2, 1, 3, 6, 5, 7，並且呼吸優先迭代器將返回4, 2, 6, 1, 3, 5, 7，並且這些插入順序中的任一個都將重現原始樹。