Verschmelzen von Bäumen

starbug

Erfahrenes Mitglied
hallo leute ich habe eine aufgabe bekommen die ich einfach nicht hin bekomme. es wäre super von euch wenn mir jemand helfen kann. hier sind mal die klassen mit den standartmethoden.

public class Knoten
{
//Attribute
private char Schluessel;
private Knoten TeilbaumLinks;
private Knoten TeilbaumRechts;
//Standardmethoden
public char getSchluessel(){...}
public Knoten getKnotenLinks(){...}
public Knoten getKnotenRechts(){...}
public void setSchluessel(char Schluessel) {...}
public void setKnotenLinks(Knoten TeilbaumLinks) {...}
public void setKnotenRechts(Knoten TeilbaumRechts) {...}
}
public class Baum
{
//Attribute
private Knoten Wurzel;
private Knoten Loeschposition;
//Standardmethoden
public Knoten getWurzel() {...}
public void setWurzel(Knoten Wurzel) {...}
public boolean suchen(char Schluessel, Knoten Teilbaum) {...}
public Knoten einfuegen(char Schluessel, Knoten Teilbaum) {...}
public Knoten entfernen(char Schluessel, Knoten Teilbaum) {...}
}

die methode die erstellen soll heis: public void verschmelzen(Knoten wurzelZweiterBaum)

danke für antworten schonmal im vorraus :)
 
Ja ne, das ist mir klar soweit. Mir persönlich kommen aber solche Fragen auf:
Welchen Schlüssel erhält der Wurzelknoten, von Baum 1 oder Baum 2?
Was passiert, wenn es 3 oder 4 Teilbäume insgesamt sind?
Was soll passieren, wenn die Schlüssel der ersten Subknoten gleich sind? Wird das ignoriert oder werden diese in tieferen Ebenen verschmolzen?
...
Einfach mehr Details bitte...
 
also ich hab das so verstanden das der erste baum eine wurzel hat und die des zweiten dann mit des ersten verglichen wird. es ist übrigens ein suchbaum also kein avl oder sowas. danach sollen halt alle elemente des zweiten baumes mit denen des ersten verglichen werden und dementsrechend eingefügt werden. gleiche schlüssel weren dann nach unten verschoben
 
Aha, vorausgesetzt ist verstehe das richtig, dann würde ich mti etwa folgendem Ansatz rangehen:
Vergleiche die Schlüssel beider Wurzelknoten
A) Beide Schlüssel sind gleich - Der neue Baum besitzt den gleichen Wurzelknotenschlüssel wie die Ursprungsbäume.
Die jeweiligen Schlüssel der Teilbäume (4 an der Zahl) werden wiederum verglichen,
d.h. die Funktion wird rekursiv aufgerufen. Allerdings muss man hier überlegen, ob nur links+links bzw.
rechts+rechts oder auch links+rechts verschmolzen werden kann.
Wenn links+rechts verschmolzen werden können, was passiert wenn alle 4 Teilschlüssel unterschiedlich sind?
B) Beide Schlüssel sind verschieden - Es wird ein neuer Baum mit einem neuen Wurzelknoten generiert,
welcher die beiden Ursprungsbäume als Teilbäume links und rechts hat.
Die Rekursion findet hier eine Abbruchbedingung.

Hilft dir das in etwa weiter?

Edit: Ich habe gerade gesehen, dass deine Funktion nichts zurückgibt, ist das so festgelegt? Wenn ja, dann wird das mti der Rekursion schwierig ;)
 
Zuletzt bearbeitet:
Zurück