Binäre Suchbaum - Kopieren eines Baumes in einen anderen Baum

Question

Ich habe eine BST, die Einträge enthält, die einen Schlüssel und eine Zeichenfolge enthalten. Ich habe einen Baum erstellt und seine Werte gefüllt und möchte seine Werte in einen anderen Baum kopieren. Die einzigen Funktionen, die ich habe, sind die allgemeinen binären Suchbaumfunktionen und die Iteratoren Begin() und End().

Wie kann ich dies tun, ohne eine direkte Kopierfunktion zu verwenden, dh. Kopieren (T1, T2)?

Ich bin nur auf der Suche nach dem, wie theoretisch, nicht die eigentliche Code-Implementierung.

Answer 1

Wenn Sie nur die Funktionen Suchen, Einfügen, Löschen, Beginne Iterator und Ende Iterator haben, klingt es so, als ob Sie nur über den ersten Baum iterieren und jeden Wert einzeln in den Zielbaum einfügen würden. Aber Vorsicht: Wenn diese Iteratoren Elemente in der richtigen Reihenfolge zurückgeben und Ihre Bäume nicht selbstbalancierend sind, dann wird der resultierende Baum ein Stick sein, wenn er kopiert wird. (d. h. es ist völlig unausgeglichen.) Wenn Ihre Iteratoren die Werte pre-order oder breadth first zurückgeben, ist dies kein Problem.

z. Angesichts der folgenden Baum:

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

Wenn die Iteratoren die Sequenz 1, 2, 3 ... 7 zurückgegeben, so dass sie in dieser Reihenfolge in einen leeren Baum eingefügt erzeugen würde folgendes:

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

Allerdings würde vorbestellen Iteratoren zurückgeben 4, 2, 1, 3, 6, 5, 7, und Breath-First-Iteratoren würden 4, 2, 6, 1, 3, 5, 7 zurückgeben, und jede dieser Einfügungsreihenfolgen würde den ursprünglichen Baum reproduzieren.