Zwei Binärbäume vereinigen

[Chucky]

Hi,
habe die Aufgabe bekommen zwei Binärbäume zu vereinigen
a) A enthält zahlen zwischen 15000 und 30000, B zwischen 0 und 20000
b) A enthält Zahlen zwischen 25000 und 50000, B zwischen 0 und 20000
c) Über A und B ist nichts weiter bekannt.

Ich denke das Programmieren schaffe ich wenn ich erstmal den Ansatz habe und die Vorstellung was da passieren musst. Wäre euch sehr dankbar für einer kleiner Starthilfe

 

[Eldaron]

Hast du die Binärbäume schon als Datenstruktur? Oder ist Dir momentan noch nicht ganz klar, welche Eigenschaften ein Binärbaum hat, bzw. welche Methoden du für den Baum brauchst ?

 

[Chucky]

doch die habe ich schon bräuchte praktisch nur einen groben algorithmus wie man da vorgeht :/

 

[Eldaron]

Hm,

also so ausm Bauch raus würd ich einfach
das niedrigste Element von A und das niedrigste Element von B nehmen, dann vergleichen, und das Niedrigere von beiden dann hinzufügen zum neuen Baum (und ausm BaumA entfernen). Das machste so lange, bis einer der beiden Bäume leer ist, dann kannst den anderen Baum einfach anhängen, weil er ja durch seine Eigenschaften schon sortiert sein muss.

 

[Chucky]

Also bei Fall b) hängt man einfach die Wurzel von Baum B and das links unterste Element von Baum A weil alle elemente in B kleiner sind aber bei a) und c) hab ich noch keine Lösung wies am schnellsten geht bei c) denke ich gibts auch net viel :/

 

[Leroy42]

das niedrigste Element von A und das niedrigste Element von B nehmen, dann vergleichen, und das Niedrigere von beiden dann hinzufügen zum neuen Baum...

:shock:
Auf gar keinen Fall!!!
Wenn es sich bei dem neuen Baum nicht gerade um einen, sich selbst ausgleichenden
Baum handelt, ist es das falscheste was man machen kann.

Wenn du in einen normalen Binärbaum die Elemente aufsteigend/absteigend
einfügst, degeneriert er zu einer Liste, da für jedes Element rechts/links ein neuer
Teilbaum angelegt wird.

Also wenn, dann schon erst die Knoten einfügen und dann rekursiv mit
den Teilbäumen weitermachen.

@Chucky

Zu b) gebe ich dir Recht.
Zu c) wie von Eldaron beschrieben, aber ohne Vergleiche von den Wurzeln aus,
abwechselnd einfügen

Bei a) bin ich mir nicht sicher ob es da etwas Raffiniertes/Angepaßtes gibt; ansonsten
verfahren wie bei c)

 

[Guest]

Habe jetzt auch zu a) ne Lösung glaub ich:
Den kritischen Bereich stellen hier die Zahlenmenge 15000-20000 dar, da Zahlen aus diesen Bereichen in beiden Bäumen vorhanden sind. Dh es führt kein Weg dran vorbei jedes Element einzeln einfügen zu müssen.
Die übriggeliebenen Teilbäume kann ich dann denk ich wieder links und rechts anfügen.

 

[Chucky]

Sry vergessen mich einzuloggen :/