二进制搜索树 - 将一棵树复制到另一棵树中

Question

我有一个包含键和字符串的条目。我做了一棵树并填充了IT值，并希望将其值复制到另一棵树中。我拥有的唯一功能是常见的二进制搜索树功能和迭代器begin（）和end（）。

我如何在不使用直接复制函数的情况下执行此操作。复制（T1，T2）？

我只是在寻找理论上的方法，而不是实际的代码实现。

Answer 1

如果您拥有的唯一函数是搜索，插入，删除，开始迭代器和结束迭代器，那么您唯一的选项是在第一个树上迭代，单独插入每个值进入目标树。但是请注意，如果这些迭代器按顺序返回元素，而您的树也不是自动平衡，那么在复制时，所得树将是棍子。（即它将完全不平衡。）如果您的迭代器首先返回预订或广度，那么这不是一个问题。

例如。给定以下树：

     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，这些插入订单中的任何一个都将重现原始树。