Baum aus Prüfercode?
Hallo,
gegeben ist der Prüfercode p = (1, 2, 1, 2, 1, 6) und daraus soll der entsprechende Baum gezeichnet werden.
Ist meine Zeichnung aus dem Anhang richtig?
2 Antworten
Ich bekomme das selbe heraus. Man kann ja jetzt anhand der Zeichnung die Probe machen und den Prüfercode zu dem Baum erstellen:
Die Blätter im Baum haben die Label 3, 4, 5, 7 und 8. Das kleinste Label ist die 3, der Knoten an dem die 3 hängt, ist die 1: P=(1,...)
3 wird entfernt. Jetzt sind die Blätter 4, 5, 7 und 8. Das kleinste Label ist die 4, die hängt an der 2: P=(1,2,....)-
4 wird entfernt. Es bleiben die Blätter 5, 7 und 8. Das kleinste Label ist die 5, die hängt an der 1: P= (1,2,1,...).
5 wird entfernt. Es bleiben die Blätter 7 und 8. 7 ist das kleinste, hängt an der 2; P=(1,2,1,2...)
Jetzt sind 2 und 8 die beiden Blätter (2 ist neu hinzugekommen, da wir inzwischen 4 und 7 gestrichen haben). 2 ist das kleinste, hängt an der 1: P=(1,2,1,2.,1...).
Nach dem Streichen von 2 sind jetzt die Blätter 1 und 8 übrig. 1 ist das kleinste, hängt an der 6: P=(1,2,1,2,1,6).
Jetzt sind nur noch Blätter übrig (6 und 8). Damit sind wir also fertig. Und man sieht: Es kommt der richtige Code heraus. Du hast also den richtigen Baum ermittelt.
der Baum rechts müsste meiner Schätzung nach den Prüfercode haben:
3 entfernt->1 hinzu
4 entfernt-> 2 hinzu
5 entfernt 1 hinzu
7 entfernt 2 hinzu
2 entfernt 1 hinzu
1 entfernt 6 hinzu
nur noch die knoten 6 und 8 übrig, wir sind fertig.
Demnach müsste der prüfercode zu deiner zeichnung
(1,2,1,2,1,6) sein
stimmt also :-)
wie hast du eigentlich diesen baum dazu gezeichnet?
die vermutlich inneren knoten 1,2,6 aneinandergereiht und alle anderen zahlen so lange rumprobiert bis es passte? :-)
Das geht ganz systematisch. Erstmal kommen alle Knoten von 1 bis 8 in die Menge der verfügbaren Knoten K = {1,...8}.
P ist Prüfercode, also P = (1,2,1,2,1,6).
Man fängt mit der 1 an, ist ja das erste Element des Prüfercodes. Jetzt sucht man die kleinste Zahl, die im Prüfercode nicht vorkommt und hängt sie an die 1 heran. Das ist in diesem Fall die 3, also hat man jetzt die zwei Knoten 1 und 3 verbunden.
Jetzt wird die 1 am Anfang aus dem Code gestrichen und die 3 aus der Menge der verfügbaren Knoten.
P ist dann (2,1,2,1,6), K = {1,2,4,5,6,7,8}
Als nächstes kommt im Code die 2. Wieder sucht man in der Menge der noch verfügbaren Knoten nach dem kleinsten Knoten, der nicht im verbleibenden Code vorkommt. Das ist die 4, also verbindet man die 2 und die 4. Wieder streicht man die führende 2 aus dem Code und die 4 aus der Menge der Knoten.
P = (1,2,1,6), K = {1,2,5,6,7,8}
Jetzt haben wir wieder die 1. Der kleinste verfügbare Knoten, der nicht im Rest-Code vorkommt, ist die 5. Also hängen wir die 5 wieder an die 1.
P = (2,1,6), K = {1,2,6,7,8}
Jetzt wieder die 2. Der kleinste verfügbare Knoten, der nicht im Restcode vorkommt, ist die 7, also hängen wir die 7 an die 2.
P = (1,6), K = {1,2,6,8}
Jetzt wieder die 1. Jetzt ist der kleinste verfügbare Knoten, der nicht im Restcode vorkommt, die 2. Also verbinden wir die 1 und die 2.
P = (6), K = {1,6,8}
Jetzt haben wir die 6. Der kleinste verfügbare Knoten... ist die 1. Also verbinden wir die 6 und die 1.
P=(), {6,8}
Jetzt sind nur noch zwei Knoten über, die verbinden wir einfach.
Fertig.