Deutsch
Menü

Datenstrukturen und Algorithmen

Wie sind die Werte der besuchten Knoten angeordnet, wenn ein binärer Suchbaum in In-Order (symmetrische Reihenfolge: erst der linke Teilbaum, dann der Knoten, dann der rechte Teilbaum) durchlaufen wird? Alle Werte seien verschieden.

  1. AAufsteigend (der kleinste zuerst)
  2. BIn der Reihenfolge, in der sie eingefügt wurden
  3. CNach der Nähe zur Wurzel (die flachsten zuerst)
Antwort und Erläuterung anzeigen

Antwort: A. Aufsteigend (der kleinste zuerst)

In einem binären Suchbaum sind für jeden Knoten alle Werte im linken Teilbaum kleiner und alle Werte im rechten Teilbaum größer als der Knoten. Werden der linke Teilbaum, der Knoten und der rechte Teilbaum in dieser Reihenfolge besucht, kommen die Werte daher vom kleinsten zum größten, das Ergebnis ist also aufsteigend sortiert. Die Knoten nach der Nähe zur Wurzel zu besuchen, ist ein Durchlauf in Breitenreihenfolge (Level-Order), der Ebene für Ebene von links nach rechts vorgeht. Die Einfügereihenfolge prägt zwar die Form des Baums, stimmt aber mit keiner dieser Durchlaufreihenfolgen überein.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. 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?
  2. 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?
  3. 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?
  4. 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?
  5. 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?