Fragen zu Bäumen

[macantise]

Hallo,
ich bin neu hier im Forum und habe zwei (wahrscheinlich banale) Fragen zu Bäumen.
-Mit der Suchfunktion habe ich nichts finden können, deshalb hab ich einfach mal ein neues Thema geöffnet.

Also 1. Frage: Der Schlüssel des Vaters ist <= dem Schlüssel des Sohnes. Trifft das nur auf den Sonderfall Heap zu oder gilt das für alle Bäume? (Bin etwas verwirrt, nachdem ich mich mit einem Bekannten darüber unterhalten habe).
- Ich dachte das gilt nur für den Heap. (Also das die Schlüssel unterschiedlich groß sein dürfen. siehe Lsg. Frage 2)

2. Frage: Wie komme ich von vorgegebenen Traversierungen auf den dementsprechenden Baum? (Habe das Beispiel aus dem Netz, bin nicht drauf gekommen und leicht am Verzweifeln)
Bsp. Aufgabe mit Lösung:

Gegeben seien die Preorder- und die Inorder-Traversierung eines binaren Baumes:
Preorder: 16 19 13 42 21 23 18 25 11
Inorder: 19 13 16 23 18 21 42 25 11
Zeichnen Sie den zugehorigen Baum.
Lsg:
Anhang anzeigen 699

Vielen Dank im voraus!

 

[SlaterB]

1. was ist denn der 'Schlüssel' eines Knotens, ist das ein Fachbegriff?
allgemein kann ich mir durchaus auch einen unsortierten Baum vorstellen (dein Bild ist doch ein Beispiel?!)
oder eine Sortierung, in der der linke Teilbaum kleine Werte enthält als ein Knoten selber

2. das ist wohl logisches Denken bzw. Ausprobieren, Möglichkeiten aufschreiben und falsche streichen, eine Knobelaufgabe,
ein Programm kann das sicher auch deterministisch,

die obere Reihe verrät, dass die 16 die Wurzel ist und es keinen linken Teilbaum gibt, oder dieser mit 19 beginnt,
die untere Reihe verrät, dass 19 und 13 in den linken Teilbaum gehören, denn sie stehen vor der 16,

nach und nach erhält man so alle Informationen über den Aufbau

 

[Ezra]

1. Nur der Heap.

2. Siehe Wiki, Unterpunkt Traversierung Binärbaum ? Wikipedia
Bei einem binären Baum ist das eindeutig. Zum Beispiel ist bei der Preordertraversierung Wurzel - Links - Rechts. Genauso ordnest Du die Knoten an.

 

[macantise]

Vielen Dank für die Antwort.

- Schlüssel werden doch an Knoten gespeichert? So kenne ich das zumindest.

Hab den Wald vor lauter Bäumen nicht gesehen.
Nachdem du den Anfang erklärt hast, war mir alles klar.

Danke

 

[Ezra]

- Schlüssel werden doch an Knoten gespeichert? So kenne ich das zumindest.

Jap.