c++ - 二叉搜索树 - 将一棵树复制到另一棵树

Question

我有一个 BST，其条目包含键和字符串。 我做了一棵树并填充了它的值，并想将它的值复制到另一棵树中。我拥有的唯一函数是常见的二叉搜索树函数和迭代器 Begin() 和 End()。

如何在不使用直接复制功能的情况下执行此操作，即。复制(T1，T2)？

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

Answer 1

如果您仅有的功能是搜索、插入、删除、开始迭代器和结束迭代器，那么听起来您唯一的选择就是迭代第一棵树，将每个值单独插入到目标树中。但是请注意，如果这些迭代器按顺序返回元素，并且您的树不是自平衡的，那么在复制时，生成的树将是一根棍子。 (即它将完全不平衡。)如果您的迭代器返回值 pre-order或 breadth first那么这不是问题。

例如给定以下树:

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