Deutsch
Menü

Datenstrukturen und Algorithmen

Die Werte 50, 30, 70, 20, 40, 60, 80 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. In welcher Reihenfolge werden die Knoten besucht, wenn der Baum in Post-Order (erst der linke Teilbaum, dann der rechte Teilbaum, dann der Knoten) durchlaufen wird?

  1. A50, 30, 20, 40, 70, 60, 80
  2. B20, 40, 30, 60, 80, 70, 50
  3. C20, 30, 40, 50, 60, 70, 80
Antwort und Erläuterung anzeigen

Antwort: B. 20, 40, 30, 60, 80, 70, 50

Die Wurzel ist 50; ihr linkes Kind ist 30 (mit den Kindern 20 und 40), ihr rechtes Kind 70 (mit den Kindern 60 und 80). Post-Order besucht den linken Teilbaum als 20, 40, 30 und den rechten Teilbaum als 60, 80, 70 und erst danach die Wurzel 50. 50, 30, 20, 40, 70, 60, 80 ist das Ergebnis von Pre-Order, das jeden Knoten zuerst besucht, und 20, 30, 40, … das Ergebnis von In-Order. Post-Order wird verwendet, wenn Kinder zuerst verarbeitet werden müssen, etwa beim Löschen eines Baums oder beim Erzeugen der Postfixnotation aus einem Ausdrucksbaum.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Die Werte 1, 2, 3, …, 1000 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt (ohne Rebalancierung). Mit wie vielen Knoten wird bei der Suche nach 1000, beginnend an der Wurzel, verglichen, bis der Wert gefunden ist?
  2. Was ist der Hauptgrund dafür, dass für Indizes in Datenbanken und Dateisystemen B-Bäume (einschließlich B+-Bäumen) statt binärer Suchbäume weit verbreitet sind?
  3. Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?
  4. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?
  5. In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?