Двоичное дерево поиска - копирование одного дерева в другое дерево

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, и любой из этих заказов на вставку будет воспроизводить исходное дерево.