Binärbäume

• Baum:
  • auf jeden Knoten zeigt genau ein Zeiger (keine Schlingen)
  • genau ein Knoten (Wurzel) hat keinen Vorgängerknoten
  • Blatt = Knoten ohne Nachfolger
  • Höhe eines Baumes h(B) = maximale Länge eines Weges im Baum B
  • Binärbaum = Knoten haben genau zwei Zeiger (darunter ggf. null-Zeiger)
  • Beispiel: Baum der Höhe 4 (in der Informatik wachsen Bäume nach unten)
    
  • Knoten für Binärbäume als Java-Klasse: BaumKnoten.java
• Durchlaufen eines Baums:
  • z.B.zur Ausgabe aller Elemente oder zum Speichern der Daten
  • viele verschiedene Reihenfolgen möglich, drei besonders häufig
  • inorder:
    • zuerst linken Teilbaum, dann Wurzel, dann rechten Teilbaum
      
    • Ausgabe des Beispielbaums: 2 5 7 9 10 15 18 24
  • preorder:
    • zuerst Wurzel, dann linken Teilbaum, dann rechten Teilbaum
      
    • Ausgabe des Beispielbaums 10 5 2 7 9 18 15 24
  • postorder:
    • zuerst linken Teilbaum, dann rechten Teilbaum, dann Wurzel
      
    • Ausgabe des Beispielbaums 2 9 7 5 15 24 18 10
• Implementierung der Baumausgabe in Reihenfolge inorder:
  • ausdrucken(BaumKnoten b) druckt Teilbaum ab b
  • benutzt Rekursion, um Unterbäume links und rechts auszudrucken

    • ausdrucken(BaumKnoten b) { 
        // druckt ganzen Unterbaum ab b
        if (b.links != null) { 
          ausdrucken(b.links); 
        } 
        System.out.print(daten);
        if (b.rechts != null) { 
          ausdrucken(b.rechts); 
        }
      }
      

  • Blatt → beide Zeiger null → Abbruch der Rekursion
  • bequemes Ausdrucken des ganzen Baums mit

    • public void ausdrucken() {
          if (wurzel != null) {
            ausdrucken(wurzel);
          } else {
            System.out.println("<leerer Baum>");
          }
        }
      

• Sortieren mit Binärbäumen:
  • Sortierbaum: links von einem Knoten nur kleinere Werte, rechts nur größere
  • Aufbau eines Sortierbaums
    • Elemente nacheinander einfügen
    • an jedem Knoten Größenvergleich mit dortigem Wert
    • abhängig vom Ergebnis nach links oder rechts weitergehen
    • unten angekommen → neues Blatt anfügen
  • Beispieldaten 5 2 1 8 9 4 liefern
    
  • Implementierung des Einfügens rekursiv, ähnlich zum Ausdrucken
  • Beispielprogramm Baum.java
  • sehr schnelles Suchen (O(log n)) bei einigermaßen symmetrischem Baum
  • Problem
    • sich aufbauender Baum kann sehr unsymmetrisch werden
    • Suchen im Extremfall wieder O(n)
    • etwa für Beispieldaten 8 5 2 1 9 4
      
• Aufgaben:
  • Aufgabe 5