Doppelt verzeigerte Liste mit Referenz auf das Ende der Liste

Implementieren Sie eine doppelt verzeigerte Liste zur Verwaltung ganzer Zahlen. Der Listenkopf referenziert auf das Kopfelement sowie auf das letzte Element der Liste

Eine Liste mit drei Knoten soll wie folgt implementiert sein:

Beachten Sie die die beiden Sonderfälle einer Liste mit einem Element und den Sonderfall einer leeren Liste.

Zur beschleunigten Implementierung sind alle Klassen schon gegeben

• ListenKnoten: Eine einfache Klasse zur Verwaltung ganzer Zahlen mit Referenzen auf Vorgänger- und Nachfolgerknoten
• MainTestListe: Ein Hauptprogramm mit diversen Testroutinen zum Testen der Liste
• EineListe: Eine Rahmenklasse die vervollständigt werden soll. Implementieren Sie die folgenden Methoden:
  • einfuegeAnKopf(einfuegeKnoten): Einfügen eines Knotens am Kopf der Liste
  • laenge(): Berechnung der Länger der Liste
  • loesche(Knoten): Löschen eines Knotens einer Liste
  • enthaelt(Knoten): Prüfung ob ein Knoten in der Liste enthalten ist. Die Prüfung erfolgt auf Objektidentität, nicht auf Wertgleichheit
  • einfuegeNach(nachKnoten,einfuegeKnoten): Einfügen eines neuen Knotens einfuegeKnoten hinter dem Knoten nachKnoten

Warum werden die Methoden in EineListe und nicht in ListenKnoten implementiert? Am Anfang gibt es keine Liste mit Knoten In EineListe muß der Kopf und das Ende gepflegt werden. Hier können Änderungen bei fast allen Operationen notwendig werden. Die Liste kann über Zeiger an die Knoten kommen. Die Knoten wissen aber nicht zu welcher Liste sie gehören.

UML Diagramm der drei Klassen:

Klasse Listenknoten

package s2.listen;
/**
 *
 * @author s@scalingbits.com
 */
public class Listenknoten {
    private Listenknoten vorgaenger;
    private Listenknoten nachfolger;
    private int wert;

   public Listenknoten(int einWert) { wert=einWert;}
   public Listenknoten getNachfolger() { return nachfolger;}
   public void setNachfolger(Listenknoten nachfolger) {
   this.nachfolger = nachfolger;
   }
   public Listenknoten getVorgaenger() {
      return vorgaenger;
   }
   public void setVorgaenger(Listenknoten vorgaenger) {
      this.vorgaenger = vorgaenger;
   }
   public int getWert() {
      return wert;
   }
   public void setWert(int wert) {
      this.wert = wert;
   }
   /**
   * Erlaubt den Zahlenwert als Text auszudrucken
   * @return
   */
   @Override
   public String toString() { return Integer.toString(wert);}
}

Klasse EineListe

Vervollständigen Sie die folgende Klasse

package s2.listen;
/**
*
* @author s@scalingbits.com
*/
public class EineListe {
    protected Listenknoten kopf;
    protected Listenknoten ende;
    /**
     * Konstrukor. Erzeuge eine leere Liste
     */
    public EineListe() {
        kopf = null;
        ende = null;
    }
    /**
    * Berechne die Länge der Liste
    * @return Länge der Liste
    */
    public int laenge() {
        int laenge = 0;
        System.out.println("1. Implementieren Sie EineListe.laenge()");
        return laenge;
    }
    /**
     * Liefert den Kopf der Liste oder einen Null Zeiger
     * @return
     */

    public Listenknoten getKopf() {
        return kopf;
    }

    /**
     * Liefert das Ende der Liste oder einen Null Zeiger
     * @return
     */
    public Listenknoten getEnde() {
        return ende;
    }

    /**
     * Drucke eine Liste alle Objekte auf der Konsole
     */

    public void drucken() {
        System.out.println("Länge Liste: " + laenge());
        Listenknoten k = kopf;
        while (k != null) {
            System.out.println("Knoten: " + k);
            k = k.getNachfolger();
        }
    }

    /**
     * Füge hinter dem Listenknoten "nach" den Knoten "k"ein.
     * Füge nichts ein wenn der Listenknoten "nach" nicht in der Liste
     * vorhanden ist
     * @param nach
     * @param k
     */

    public void einfuegeNach(Listenknoten nach, Listenknoten k) {
        System.out.println("5. Implementieren Sie EineListe.einfuegeNach()");
    }

    /**
     * Füge einen Listenknoten am Kopf der Liste ein
     * @param k neuer Listenknoten
     */

    public void einfuegeAnKopf(Listenknoten k) {
        System.out.println("2. Implementieren Sie EineListe.einfuegeAnKopf()");
    }

    /**
     * Lösche einen Knoten aus der Liste. Mache nichts falls es nichts zu
     * gibt
     * @param k zu löschender Listenknoten
     */

    public void loesche(Listenknoten k) {
        System.out.println("3. Implementieren Sie EineListe.loesche()");
    } // Ende Methode loesche()

    /**
     * Ist wahr wenn ein Knoten mit dem gleichen Wert existiert
     * @param k
     * @return
     */

    public boolean enthaelt(Listenknoten k) {
        boolean result = false;
        System.out.println("4. Implementieren Sie EineListe.enthaelt()");
        return result;
    } // Ende Methode enhaelt()

} // Ende der Klasse EineListe

Klasse MainTestListe

package s2.listen;

/**
*
* @author s@scalingbits.com
*/
public class MainTestListe {
   /**
   * Testroutinen für einfache Listen
   * @param args
   */
   public static void main(String[] args) {
      EineListe testListe = new EineListe();
      einfuegeTest(testListe, 4, 6);
      System.out.println("Kontrolle: Drei Knoten von 4 bis 6");
      einfuegeTest(testListe, 1, 3);
      System.out.println("Kontrolle: Sechs Knoten von 1 bis 6");
      einfuegeTest(testListe, 21, 27);
      System.out.println("Kontrolle: 13 Knoten von 21 bis 27, 1 bis 6");
      loeschenEndeTest(testListe, 3);
      System.out.println("Kontrolle: 10 Knoten von 21 bis 27, 1 bis 3");
      loeschenKopfTest(testListe, 8);
      System.out.println("Kontrolle: 2 Knoten von 2 bis 3");
      loeschenKopfTest(testListe, 3);
      System.out.println("Kontrolle: 0 Knoten. Versuch löschen in leerer Liste");
      enthaeltTest(testListe, 10);
      System.out.println("Kontrolle: Einfügen in der Liste");
      testListe = new EineListe();
      einfuegeNachTest(testListe, 10);
   }
   /**
   * Einfügen einer Reihe von Zahlen in eine gegebene Liste
   * @param l Liste in die eingefügt wird
   * @param min kleinster Startknoten der eingefügt wird
   * @param max größter Knoten der eingefügt werden
   */
   public static void einfuegeTest(EineListe l, int min, int max) {
      System.out.println("Test: Einfügen am Kopf [" + min + " bis " + max + "]");
      for (int i = max; i >= min; i--) {
         l.einfuegeAnKopf(new Listenknoten(i));
         System.out.println("Länge der Liste: " + l.laenge());
      }
      l.drucken();
   }
   /**
   * Lösche eine bestimmte Anzahl von Knoten am Ende der Liste
   * @param l Liste aus der Knoten gelöscht werden
   * @param anzahl der zu loeschenden Knoten
   */
   public static void loeschenEndeTest(EineListe l, int anzahl) {
      System.out.println("Test: Löschen am Ende der Liste " + anzahl + "fach:");
      for (int i = 0; i < anzahl; i++) {
         l.loesche(l.ende);
         System.out.println("Länge der Liste: " + l.laenge());
      }
      l.drucken();
   }
   public static void loeschenKopfTest(EineListe l, int anzahl) {
      System.out.println("Test: Löschen am Kopf der Liste " + anzahl + "fach:");
      for (int i = 0; i < anzahl; i++) {
         l.loesche(l.getKopf());
         System.out.println("Länge der Liste: " + l.laenge());
      }
      l.drucken();
   }
   public static void enthaeltTest(EineListe l, int groesse) {
      System.out.println("Test: enhaelt() " + groesse + " Elemente");
      Listenknoten[] feld = new Listenknoten[groesse];
      for (int i = 0; i < groesse; i++) {
         feld[i] = new Listenknoten(i * 10);
         l.einfuegeAnKopf(feld[i]);
      }
      l.drucken();
      for (int i = 0; i < groesse; i++) {
         if (l.enthaelt(feld[0])) {
            System.out.println("Element " + feld[i] + " gefunden");
         }
      }
      System.out.println("Erfolg wenn alle Elemente gefunden wurden");
      Listenknoten waise = new Listenknoten(4711);
      if (l.enthaelt(waise)) {
         System.out.println("Fehler: Element gefunden welches nicht zur Liste gehört!");
      } else {
         System.out.println("Erfolg: Element nicht gefunden welches nicht zur Liste gehört");
      }
   }
   public static void einfuegeNachTest(EineListe l, int max) {
      System.out.println("Test: einfügen nach " + max + "fach");
      Listenknoten[] feld = new Listenknoten[max];
      for (int i = 0; i < max; i++) {
         feld[i] = new Listenknoten(i*10);
         l.einfuegeAnKopf(feld[i]);
      }
      System.out.println("Länge der Liste: " + l.laenge());
      for (int i = 0; i < max; i++) {
         l.einfuegeNach(feld[i], new Listenknoten(feld[i].getWert()+1));
         System.out.println("Länge der Liste: " + l.laenge());
      }
      l.einfuegeNach(l.ende, new Listenknoten(111));
      l.drucken();
   }
}

Doppelt verzeigerte Liste mit Referenz auf das Ende der Liste

Klasse EineListe

Hinweis: Ändern Sie den Namen von EineListeLoseung an den zwei Stellen zu EineListe.

package s2.listen;
/**
 *
 * @author s@scalingbits.com
 */
public class EineListeLoesung {
    protected Listenknoten kopf;
    protected Listenknoten ende;
    public EineListeLoesung() {
        kopf = null;
        ende = null;
    }
    /**
     * Berechnet die Anzahl der Listenelemente
     * @return Anzahl der Listenelemente
     */
    public int laenge() {
        int laenge = 0;
        Listenknoten zeiger = kopf;
        while (zeiger != null) {
            laenge++;
            zeiger = zeiger.getNachfolger();
        }
        return laenge;
    }
    /**
     * Liefert den Kopf der Liste oder einen Null Zeiger
     * @return Zeiger auf Kopf der Liste
     */
    public Listenknoten getKopf() {
        return kopf;
    }
    /**
     * Liefert das Ende der Liste oder einen Null Zeiger
     * @return Zeiger auf das Ende der Lister
     */
    public Listenknoten getEnde() {
        return ende;
    }
    /**
     * Drucke eine Liste alle Objekte auf der Konsole
     */
    public void drucken() {
        System.out.println("Länge Liste: " + laenge());
        Listenknoten k = kopf;
        while (k != null) {
            System.out.println("Knoten: " + k);
            k = k.getNachfolger();
        }
    }
    /**
     * Füge hinter dem Listenknoten "nach" den Knoten "k"ein.
     * Füge nichts ein wenn der Listenknoten "nach" nicht in der Liste
     * vorhanden ist
     * @param nach
     * @param k
     */
    public void einfuegeNach(Listenknoten nach, Listenknoten k) {
        Listenknoten t;
        t = kopf; // Diese Variable wird über die Listenknoten laufen
        while ((t != null) && (t != nach)) {
            // Iteriere über die Liste solange Knoten existieren
            // und kein passender gefunden hier
            t = t.getNachfolger();
        }
        if (t == nach) { // Der Knoten wurde gefunden
            // Merken des Nachfolger hinter der Einfuegestelle
            Listenknoten derNaechste = nach.getNachfolger();
            if (derNaechste != null) {
                // Setzen des neuen Vorgängers falls es einen Nachfolger gab
                derNaechste.setVorgaenger(k);
            } else { // Wir haben am Ende eingefuegt. Ende-Zeiger korrigieren
                ende = k;
            }
            // Der neu eingefügte Knoten soll auf den Nachfolger zeigen
            k.setNachfolger(derNaechste);
            // Der gesuchte Knoten ist der Vorgaenger. Der neue Knoten
            // soll auf ihn zeigen
            k.setVorgaenger(t);
            // Der Vorgaenger soll auf den neu einfeügten Knoten zeigen
            t.setNachfolger(k);
        }
    }
    /**
     * Füge einen Knoten am Anfang der Liste ein
     * @param k 
     */
    public void einfuegeAnKopf(Listenknoten k) {
        k.setVorgaenger(null);
        if (kopf == null) { // Die Liste ist leer
            ende = k; // Das Ende ist auch der Kopf
            k.setNachfolger(null); // Sicherstellen das kein Nachfolger benutzt wird
        } else { // Liste ist nicht leer
            k.setNachfolger(kopf); // Neuer Nachfolger ist alter Kopf
            kopf.setVorgaenger(k); // Alter Kopf bekommt Vorgaenger

        }
        kopf = k; // Es gibt einen neuen Kopf. Heureka
    }

    public void loesche(Listenknoten k) {
        Listenknoten t = kopf; // Diese Variable wird über die Listenknoten laufen
        if (kopf == null) {
            System.out.println("Löschversuch auf leerer Liste");
        } else {
            //Pflege der Kopf- bzw Endezeiger
            if (kopf == k) {
                // Das Kopfelement wir geloescht
                kopf = k.getNachfolger(); //Kann auch Null sein...
            }
            if (ende == k) {
                // Das zu loeschende Objekt ist das Letzte
                ende = k.getVorgaenger(); // Kann auch Null sein...
            }
            while ((t != null) && (t != k)) {
                // Iteriere über Liste solange Nachfolger da sind
                // und nichts passendes gefunden wird
                t = t.getNachfolger();
            }
            if (t == k) { // Der Knoten wurde gefunden
                Listenknoten nachf = k.getNachfolger();
                Listenknoten vorg = k.getVorgaenger();
                if (nachf != null) {
                    // Es gibt einen Nachfolger. Pflege dessen Vorgaenger
                    nachf.setVorgaenger(vorg);
                }
                if (vorg != null) {
                    // Es gibt einen Vorgaenger. Pflege dessen Nachfolger
                    vorg.setNachfolger(nachf);
                }
                // Entfernen aller Referenzen des geloeschten Objekts
                t.setNachfolger(null);
                t.setVorgaenger(null);
            } // Ende der Knoten wurde gefunden
        } // Ende Loeschen aus einer nicht leeren Liste
    } // Ende Methode loesche

    /**
     * Ist wahr wenn ein Knoten mit dem gleichen Wert existiert
     * @param k
     * @return
     */
    public boolean enthaelt(Listenknoten k) {
        Listenknoten t = kopf;
        boolean result = false;
        while ((result == false) && (t != null)) {
            result = (t == k);
            if (!result) {
                t = t.getNachfolger();
            }
        }
        return result;
    } // Ende Methode enhaelt()
} // Ende der Klasse EineListe
 

Binärbäume werden benutzt da sie ein sehr effizientes Suchen mit einem Aufwand von O(logN) erlauben solange sie balanciert sind. In extremen Fällen kann die Suche nach Knoten jedoch zu einem Aufwand von O(N) führen falls der Baum degeneriert ist.

Die im vorhergehenden Abschnitt vorgestellten Bäume verwenden in ihren Implementierungen der Einfüge- und Entferneoperation naive Verfahren. Diese naive Verfahren können dazu führen, dass ein Baum sehr unbalanciert werden kann.

Erste Vorschläge zur Vermeidung dieses Problems gehen auf die 1962 gemachten Vorschläge von Adelson-Velskij und Landis zurück. Sie schlugen höhenbalancierte AVL Bäume vor.

AVL Bäume

 Beispiele von AVL Bäumen die der obigen Definition genügen sind im folgenden Diagramm zu sehen

 Der nachfolgende Baum ist kein AVL Baum. Der rechte Knoten in der zweiten Ebene von oben hat einen linken Unterbaum der Höhe 1 und einen rechten Unterbaum der Höhe 3.

Dieser Baum müsste umorganisiert werden um ein AVL Baum zu werden.

Zum Verwalten von AVL Bäumen berechet man jedoch nicht immer wieder die Höhe der Teilbäume.

Es ist einfacher einen Balanchefaktor zu jedem inneren Knoten mitzuführen der die Differenz der Höhe vom linken und rechtem Teilbaum verwaltet.

Im folgenden Beispiel sind die Balancefaktoren für die inneren Knoten eingetragen:

 AVL Bäume müssen beim Einfügen und Entfernen von Knoten unter Umständen neu balanciert werden. Der Vorteil besteht jedoch in dem sehr vorhersagbaren Verhalten mit dem Aufwand von O(logN) bei Operationen auf dem Baum.

Tipp: Bauen Sie sich Ihren eigen AVL Baum. Die Universität hat eine web basierte Visualisierung von AVL Bäumen.

Bruderbäume kann man als expandierte AVL Bäume verstehen.

Bruderbäume bekommen durch gezieltes Einfügen unärer Knoten eine konstante Tiefe für alle Blätter. Sie sind höhenbalancierte Bäume. Mit ihnen lässt sich garantieren, dass man mit dem gleichen Suchaufwand auf alle Blätter des Baums zugreifen kann.

Bruderbäume unterscheiden sich von den Binärbäumen dadurch, dass die inneren Knoten mindesten einen Sohn haben.

Bruderbäume haben ihren Namen von dem Fakt, dass für die Söhne eines Knoten untereinander (die Brüder) bestimmte Regeln gelten.

Ein binärer Baum ist ein Bruderbaum wenn das folgende gilt:

Beispiele

Im folgenden Diagramm ist der rechte Baum ist kein Bruderbaum da es auf der zweiten Ebene von oben zwei unäre Bruder gibt.

Im Diagramm unten ist der rechte Baum kein Bruderbaum weil die beiden Bruderknoten in der zweiten Ebene von oben unäre Brüder sind.

Bemerkung

Bei Bruderbäumen müssen bei Bedarf innerer Knoten eingefügt werden um die Bruderbedingungen zu erfüllen. Bruderbäume sind daher Bäume bei denen die zu verwaltenden Datenstrukturen nicht notwendigerweise in den inneren Knoten verwaltet werden können.

Balancierte und unbalancierte Bäume

Das folgende Programm erlaubt es manuell einen streng geordneten Binärbaum aus Ganzzahlen aufzubauen.

Das Programm steht als jar Datei zur Verfügung und kann nach dem Download wie folgt gestartet werden:

java -jar BaumGUI.jar

Balancierter Baum

Benutzen Sie das Beispielprogramm und erzeugen sie einen balancierten Baum mit 15 Knoten und der Höhe 4 wie zum Bsp.:

In welcher Reihenfolge müssen die Werte eingegeben werden?

Degenerierter Baum

Erzeugen Sie einen degenerierten Baum mit 5 Knoten und der Höhe 5:

Welche Eingabefolgen von Zahlen erzeugen eine Liste degenerierten Teilbäumen?

Implementierung einer Binärbaums

Alle Klassen zu dieser Übung sind auch über github verfügbar.

Implementieren Sie einen streng geordneten Binärbaum in dem man ganze Zahlen Einfügen und Löschen kann.

Es ist nicht notwendig einen balancierten Baum oder AVL Baum zu implementieren.

Vervollständigen Sie die 3 drei fehlenden Methoden:

• s2.baum.Baumknoten
  • Methode hoehe() : Implementieren Sie eine rekursive Methode zum bestimmen der Höhe des Baums (1.ter Schritt)
• s2.baum.Binaerbaum
  • Methode einfuegen(teilBaum, Knoten) (2.ter Schritt)
    • Tipps
      • Betrachten Sie zuerst Sonderfälle (fehlen von Söhnen)
      • Welchen Teilbaum müssen Sie modifizieren wenn der neue Knoten kleiner als die aktuelle Wurzel ist?
      • Welchen Teilbaum müssen Sie modifizieren wenn der neue Knoten größer als die aktuelle Wurzel ist?
      • Fügen Sie keinen Knoten mit einem Wert ein, der schon existiert!
  • Methode loeschen(teilBaum, Knoten) (3.ter Schritt)
    • Tipps
      • Was müssen Sie tun wen der aktuelle Knoten gelöscht werden muss?
      • Was müssen Sie tun wenn der zu löschende Knoten die Wurzel des gesamten Baums ist?

Übersetzen Sie alle Klassen. Starten Sie die Anwendung mit

$ java s2.baum.BaumGUI

Testen Sie die Anwendung mit der automatisierten Generierung mit dem Befehl

$ java s2.baum.BaumGUI magic

Hinweis: Die Implementierung des Algorithmus zum Entfernen von Knoten ist sehr viel aufwendiger da viele Randbedingungen geprüft werden müssen. Implementieren Sie zu Beginn nur das Einfügen von Knoten und Testen Sie zuerst das Einfügen. Die aktuelle Trivialimplementierung zum Entfernen erlaubt das Übersetzen und Ausführen der Anwendung ohne das Knoten entfernt werden.

UML Diagramm der beteiligten Klassen:

Notwendige Vorarbeiten

Erzeugen Sie die Infrastruktur für das folgenden Paket s2.baum

Klasse s2.baum.Baumknoten

package s2.baum;

/**
*
* @author s@scalingbits.com
*/
public class Baumknoten {
private int wert;
//private final int maxWert= Integer.MAX_VALUE;
private final int maxWert= 99;

public int getWert() {
return wert;
}

public void setWert(int wert) {
this.wert = wert;
}
/**
* Verwalte linken Knoten
*/
private Baumknoten l;
/**
* verwalte rechten Knoten
*/
private Baumknoten r;

public Baumknoten(int i) {wert=i;}
/**
* Liefere linken Knoten zurück
* @return linker Knoten
*/
public Baumknoten getLinkerK() {
return l;
}
/**
* Setze linken Knoten
* @param k Referenz auf linken Knoten
*/
public void setLinkerK(Baumknoten k) {
l = k;
}
/**
* Liefere rechten Knoten zurück
* @return rechter Knoten
*/
public Baumknoten getRechterK() {
return r;
}
/**
* Setze rechten Knoten
* @param k rechter Knoten
*/
public void setRechterK(Baumknoten k) {
r = k;
}
/**
* Drucken einen Unterbaum und rücke entsprechend bei Unterbäumen ein
* @param einruecken
*/
public void druckeUnterbaum(int einruecken) {
if (l != null) {
l.druckeUnterbaum(einruecken + 1);
}
for (int i = 0; i < einruecken; i++) {
System.out.print(".");
}
System.out.println(toString());
if (r != null) {
r.druckeUnterbaum(einruecken + 1);
}
}
/**
* Berechne Höhe des Baums durch rekursive Tiefensuche
* @return
*/
public int hoehe() {
System.out.println("Implementieren Sie Baumknoten.hoehe() als rekursive Methode");
return -1;
}
/**
* Generiere eine Zufallsbelegung für den gegebenen Knoten
* Die Funktion darf nicht mehr nach Einfügen in den Baum
* aufgerufen werden, da der neue Wert zu einer inkorrekten Ordnung führt
*/
public void generiereZufallswert() {
wert= (int)(Math.random()*(double)maxWert);
}
/**
* Erlaubt den Zahlenwert als Text auszudrucken
* @return
*/
public String toString() { return Integer.toString(wert);}
}

Klasse s2.baum.Binaerbaum

package s2.baum;

/**
*
* @author sschneid
*/
public class Binaerbaum {
private Baumknoten wurzelKnoten;

public Baumknoten getWurzelknoten() {return wurzelKnoten;}
/**
* Füge einen neuen Baumknoten in einen Baum ein
* @param s
*/
public void einfuegen(Baumknoten s) {
if (wurzelKnoten == null) {
// Der Baum ist leer. Füge Wurzelknoten ein.
wurzelKnoten = s;
}
else // Der Baum ist nicht leer. Normales Vorgehen
einfuegen(wurzelKnoten,s);
}
/**
* Füge einen gegebenen Knoten s in einen Teilbaum ein.
* Diese Methode ist eine rekursive private Methode
* Da der neue Knoten die Wurzel des neuen Teilbaums bilden kann,
* wird eventuell ein Zeiger auf einen neuen Teilbaum zurückgeliefert
* Randbedingung:
* * Es wird kein Knoten mit einem Wert eingefügt der schon existiertz
* @param teilbaum
* @param s
*/
private void einfuegen(Baumknoten teilbaum, Baumknoten s) {
System.out.println("Implementieren Sie die Methode Binaerbaum:einfuegen()");
}
/**
* Öffentliche Methoden zum Entfernen eines Baumknotens
* @param s
*/
public void entfernen(Baumknoten s) {
wurzelKnoten = entfernen(wurzelKnoten,s);}
/**
* Private, rekursive Methode zum Entfernen eines Knotens aus einem
* Teilbaum. Es kann ein neuer Teilbaum enstehen wennn der Wurzelknoten
* selbst entfernt werden muss. Der neue Teilbaum wird daher wieder mit
* ausgegeben
* @param teilbaum Teilbaum aus dem ein Knoten entfernt werden soll
* @param s der zu entfernende Knoten
* @return Der verbleibende Restbaum. Es kann auch Null für einen leeren Baum ausgegeben werden
*/
private Baumknoten entfernen(Baumknoten teilbaum, Baumknoten s) {
System.out.println("Implementieren Sie die Methode Binaerbaum:entfernen()");
return teilbaum;
}
/**
* Berechnung der Hoehe des Baums
* @return Hoehe des Baums
*/
public int hoehe() {
if (wurzelKnoten == null) return 0;
else return wurzelKnoten.hoehe();
}
/**
* Rückgabe des Namens
* @return
*/
public String algorithmus() {return "Binaerbaum";}

public void druckenBaum() {
System.out.println("Tiefe:" + hoehe());
if (wurzelKnoten != null) wurzelKnoten.druckeUnterbaum(0);
System.out.println("A-----------A");
}

}

Klasse s2.baum.BaumGUI

package s2.baum;

import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JPanel;
import javax.swing.JTextField;

/**
*
* @author s@scalingbits.com
*/
public class BaumGUI implements ActionListener {

final private JFrame hf;
final private JButton einfButton;
final private JButton entfButton;
final private JTextField eingabeText;
final private JMenuBar jmb;
final private JMenu jm;
final private JMenuItem exitItem;
final private BaumPanel myBaum;
final private Binaerbaum b;

public BaumGUI(Binaerbaum bb) {
b = bb;
JLabel logo;
//ButtonGroup buttonGroup1;
JPanel buttonPanel;
// Erzeugen einer neuen Instanz eines Swingfensters
hf = new JFrame("BaumGUI");
// Gewünschte Größe setzen
// 1. Parameter: horizontale Größe in Pixel
// 2. Parameter: vertikale Größe
hf.setSize(220, 230);

// Beenden bei Schliesen des Fenster
hf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

// Erzeugen der Buttons und Texteingabefeld
eingabeText = new JTextField("17");
einfButton = new JButton();
einfButton.setText("Einfügen");
entfButton = new JButton();
entfButton.setText("Entfernen");

// Registriere die eigene Instanz
// zum Reagieren auf eine Aktion der beiden Buttons
einfButton.addActionListener(this);
entfButton.addActionListener(this);

// Einfügen der drei Komponenten in ein Panel
// Das Gridlayout führt zum Strecken der drei Komponenten
buttonPanel = new JPanel(new GridLayout(1, 1));
buttonPanel.add(eingabeText);
buttonPanel.add(entfButton);
buttonPanel.add(einfButton);

// Erzeugen des Panels zum Malen des Baums
myBaum = new BaumPanel(b);

// setze Titel des Frame
hf.setTitle(b.algorithmus());

// Erzeuge ein Menueeintrag zum Beenden des Programms
jmb = new JMenuBar();
jm = new JMenu("Datei");
exitItem = new JMenuItem("Beenden");
exitItem.addActionListener(this);
jm.add(exitItem);
jmb.add(jm);
hf.setJMenuBar(jmb);

Container myPane = hf.getContentPane();
myPane.add(myBaum, BorderLayout.CENTER);
myPane.add(buttonPanel, BorderLayout.SOUTH);

hf.pack();
hf.setVisible(true);
hf.setAlwaysOnTop(true);
}

/**
* Diese Methode wird bei allen Aktionen der Menüleiste oder
* der Buttons aufgerufen
* @param e
*/
public void actionPerformed(ActionEvent e) {
Object source = e.getSource();
int wert = 0;
try {
if (source == entfButton) { //Entfernen aufgerufen
wert = Integer.parseInt(eingabeText.getText());
b.entfernen(new Baumknoten(wert));
myBaum.fehlerText("");
myBaum.repaint();
eingabeText.setText("");
}
if (source == einfButton) { // Einfügen aufgerufen
wert = Integer.parseInt(eingabeText.getText());
b.einfuegen(new Baumknoten(wert));
myBaum.fehlerText("");
myBaum.repaint();
eingabeText.setText("");
}
if (source == exitItem) { // Beenden aufgerufen
System.exit(0);
}
} catch (java.lang.NumberFormatException ex) {
// Fehlerbehandlung bei fehlerhafter Eingabe
myBaum.fehlerText("Eingabe '" + eingabeText.getText() + "' ist keine Ganzzahl");
myBaum.repaint();
eingabeText.setText("");
}
}

public static void main(String[] args) {
BaumGUI sg = new BaumGUI(new Binaerbaum());
if ((args.length > 0) && (args[0].equalsIgnoreCase("magic"))) {
sg.magicMode(15);
}

}

public void magicMode(int anzahl) {
Baumknoten[] gz = new Baumknoten[anzahl];
for (int i = 0; i < gz.length; i++) {
gz[i] = new Baumknoten(0);
gz[i].generiereZufallswert();
}
try {
for (int i = gz.length - 1; i >= 0; i--) {
eingabeText.setText(gz[i].toString());
b.einfuegen(gz[i]);
Thread.sleep(800);
myBaum.repaint();
}
for (int i = 0; i < gz.length; i++) {
eingabeText.setText(gz[i].toString());
b.entfernen(gz[i]);
Thread.sleep(800);
myBaum.repaint();
}
} catch (InterruptedException e) {
}
}

}

Klasse s2.baum.BaumPanel

package s2.baum;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import javax.swing.JPanel;

/**
*
* @author s@scalingbits.com
*/
public class BaumPanel extends JPanel{
final private Binaerbaum b;
final private int ziffernBreite = 10 ; // Breite einer Ziffer in Pixel
final private int ziffernHoehe = 20; // Hoehe einer Ziffer in Pixel
private String fehlerString;

public BaumPanel(Binaerbaum derBaum) {
fehlerString = "";
b = derBaum;
setPreferredSize(new Dimension(600,200));
setDoubleBuffered(true);
}
/**
* Setzen des Fehlertexts des Fehlertexts
* @param s String mit Fehlertext
*/
public void fehlerText(String s) {fehlerString = s;}

/**
* Methode die das Panel überlädt mit der Implementierung
* der Baumgraphik
* @param g
*/
public void paintComponent(Graphics g) {
super.paintComponent(g);
int maxWidth = getWidth();
int maxHeight = getHeight();
Baumknoten k = b.getWurzelknoten();
if (k != null) { // Male Wurzelknoten falls existierend
g.setColor(Color.black);
g.drawString("Hoehe: " + b.hoehe(), 10, 20);
g.drawString(fehlerString, 10, 40);
paintKnoten(g,k,getWidth()/2, 20);
}
else {
g.setColor(Color.RED);
g.drawString("Der Baum ist leer. Bitte Wurzelknoten einfügen.",10,20);
}
}

/**
* Malen eines Knotens und seines Unterbaums
* @param g Graphicshandle
* @param k zu malender Knoten
* @param x X Koordinate des Knotens
* @param y Y Koordinate des Knotens
*/
public void paintKnoten(Graphics g,Baumknoten k, int x, int y) {
int xOffset = 1; // offset Box zu Text
int yOffset = 7; // offset Box zu Text
String wertString = k.toString(); // Wert als Text
int breite = wertString.length() * ziffernBreite;
int xNextNodeOffset = ((int)java.lang.Math.pow(2,k.hoehe()-1))*10;
int yNextNodeOffset = ziffernHoehe*6/5; // Vertikaler Offset zur naechsten Kn.ebene
if (k.getLinkerK() != null) {
// Male linken Unterbaum
g.setColor(Color.black); // Schriftfarbe
g.drawLine(x, y, x-xNextNodeOffset, y+yNextNodeOffset);
paintKnoten(g,k.getLinkerK(),x-xNextNodeOffset,y+yNextNodeOffset);
}
if (k.getRechterK() != null) {
// Male rechten Unterbaum
g.setColor(Color.black); // Schriftfarbe
g.drawLine(x, y, x+xNextNodeOffset, y+yNextNodeOffset);
paintKnoten(g,k.getRechterK(),x+xNextNodeOffset,y+yNextNodeOffset );
}
// Unterbäume sind gemalt. Male Knoten
g.setColor(Color.LIGHT_GRAY); // Farbe des Rechtecks im Hintergrund
g.fillRoundRect(x-xOffset, y-yOffset, breite, ziffernHoehe, 3, 3);
g.setColor(Color.black); // Schriftfarbe
g.drawString(wertString, x+xOffset, y+yOffset);
}

}

Baumschule...

Fragen zu Binärbäumen

Welche der beiden Bäume sind korrekte, streng sortierte Binärbäume?

Welche sind keine streng sortierten Binärbäume und warum?

Streng sortierter Binärbaum 1

Streng sortierter Binärbaum 2

AVL Bäume

Welche der beiden AVL-Bäume sind korrekte AVL-Bäume?

Welche Bäume sind keine korrekten AVL Bäume und warum?

AVL-Baum 1

AVL Baum 2

Bruder-Baum

 Welche der beiden Bäume sind keine korrekten Bruder-Bäume?

Warum sind sie keine Bruderbäume?

Bruder-Baum 1

Bruder-Baum 2

Bruder-Baum 3

Balancierte und unbalancierte Bäume

Balancierter Baum

Eingabe: 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15

Es sind auch andere Lösungen möglich.

Degenerierte Baum

Eingabemöglichkeiten

• 5, 4, 3, 2, 1
• 1, 2, 3, 4, 5

Sortierte Folgen, gleich ob sie fallend oder steigend sortiert sind, führen bei einfachen binären Bäumen zu degenerierten Bäumen mit großer Höhe.

Implementierung eines Binärbaums

Klasse s2.baum.Baumknoten

Informelle Beschreibung der Algorithmen

Höhe eines Baums

• Bestimme Höhe des linken Unterbaums
  • Gibt es einen linkenUnterbaum?
    • Nein: Höhe links =0
    • Ja: Höhe links= Höhe linker Unterbaum
• Bestimme Höhe des rechten Unterbaum
  • Gibt es einen rechten Unterbaum?
    • Nein: Höhe rechts = 0
    • Ja: Höhe rechts = Höhe rechter Unterbaum
• Bestimme den höchsten der beiden Unterbäume
• Höhe des Baumes= 1 + Höhe höchster Unterbaum

Quellcode

package s2.baum;

/**
*
* @author s@scalingbits.com
*/
public class Baumknoten {
   private int wert;
   //private final int maxWert= Integer.MAX_VALUE;
   private final int maxWert= 99;
  public int getWert() {
   return wert;
   }
   public void setWert(int wert) {
     this.wert = wert;
   }
   /**
   * Verwalte linken Knoten
   */
   private Baumknoten l;
   /**
   * verwalte rechten Knoten
   */
   private Baumknoten r;
   public Baumknoten(int i) {wert=i;}
   /**
   * Liefere linken Knoten zurück
   * @return linker Knoten
   */
   public Baumknoten getLinkerK() {
      return l;
   }
   /**
   * Setze linken Knoten
   * @param k Referenz auf linken Knoten
   */
   public void setLinkerK(Baumknoten k) {
      l = k;
   }
   /**
   * Liefere rechten Knoten zurück
   * @return rechter Knoten
   */
   public Baumknoten getRechterK() {
      return r;
   }
   /**
   * Setze rechten Knoten
   * @param k rechter Knoten
   */
   public void setRechterK(Baumknoten k) {
      r = k;
   }
   /**
   * Drucken einen Unterbaum und rücke entsprechend bei Unterbäumen ein
   * @param einruecken
   */
   public void druckeUnterbaum(int einruecken) {
      if (l != null) {
      l.druckeUnterbaum(einruecken + 1);
   }
   for (int i = 0; i < einruecken; i++) {
      System.out.print(".");
   }
   System.out.println(toString());
   if (r != null) {
      r.druckeUnterbaum(einruecken + 1);
   }
   }
   /**
   * Berechne Höhe des Baums durch rekursive Tiefensuche
   * @return
   */
   public int hoehe() {
      int lmax = 1;
      int rmax = 1;
      int max = 0;
      if (l != null) lmax = 1 + l.hoehe();
      if (r != null) rmax = 1 + r.hoehe();
      if (rmax > lmax) return rmax;
      else return lmax;
   }
   /**
   * Generiere eine Zufallsbelegung für den gegebenen Knoten
   * Die Funktion darf nicht mehr nach EInfügen in den Baum
   * aufgerufen werden, da der neue Wert zu einer inkorrekten Ordnung führt
   */
   public void generiereZufallswert() {
      wert= (int)(Math.random()*(double)maxWert);
   }
   /**
   * Erlaubt den Zahlenwert als Text auszudrucken
   * @return
   */
   public String toString() { return Integer.toString(wert);}
}

Klasse s2.baum.Binaerbaum

Informelle Beschreibung der Algorithmen

Einfügen von Knoten

• Ist der Wert des neuen Knoten gleich der Wurzel meines Baums?
  • Ja: Fertig. Es wird nichts eingefügt
  • Nein:
    • Ist der Wert kleiner als mein Wurzelknoten?
      • Ja: Der neue Knoten muss links eingefügt werden
        • Gibt es einen linken Knoten?
          • Nein: Füge Knoten als linken Knoten ein
          • Ja: Rufe Einfügemethode rejursiv auf...
      • Nein: Der neue Knoten muss rechts eingefügt werden
        • Gibt es einen rechten Knoten?
          • Nein: Füge Knoten als rechten Knoten ein
          • Ja: Rufe Einfügemethode rekursiv auf...

Quellcode

package s2.baum;
/**
 *
 * @author s@scalingbits.com
 */
public class BinaerbaumLoesung {
    private Baumknoten wurzelKnoten;
    public Baumknoten getWurzelknoten() {return wurzelKnoten;}
    /**
     * Füge einen neuen Baumknoten in einen Baum ein
     * @param s
     */
    public void einfuegen(Baumknoten s) {
        if (wurzelKnoten == null) {
            // Der Baum ist leer. Füge Wurzelknoten ein.
            wurzelKnoten = s;
        }
        else // Der Baum ist nicht leer. Normales Vorgehen
           einfuegen(wurzelKnoten,s);
    }
    /**
     * Füge einen gegebenen Knoten s in einen Teilbaum ein.
     * Diese Methode ist eine rekursive private Methode
     * Da der neue Knoten die Wurzel des neuen Teilbaums bilden kann,
     * wird eventuell ein Zeiger auf einen neuen Teilbaum zurückgeliefert
     * Randbedingung:
     * * Es wird kein Knoten mit einem Wert eingefügt der schon existiertz
     * @param teilbaum
     * @param s
     */
    private void einfuegen(Baumknoten teilbaum, Baumknoten s) {
        if (!(s.getWert()==teilbaum.getWert())) {
            // Nicht einfuegen wenn Knoten den gleichen Wert hat
            if (s.getWert()<teilbaum.getWert()) {
                // Im linken Teilbaum einfuegen
                if (teilbaum.getLinkerK() != null)
                        einfuegen(teilbaum.getLinkerK(),s);
                else teilbaum.setLinkerK(s);
             }
            else // Im rechten Teilbaum einfuegen
                if (teilbaum.getRechterK() != null)
                        einfuegen(teilbaum.getRechterK(),s);
                else teilbaum.setRechterK(s);
        }
    }
    /**
     * Öffentliche Methoden zum Entfernen eines Baumknotens
     * @param s
     */
    public void entfernen(Baumknoten s) {
        wurzelKnoten = entfernen(wurzelKnoten,s);}
    /**
     * Private, rekursive Methode zum Entfernen eines Knotens aus einem
     * Teilbaum. Es kann ein neuer Teilbaum enstehen wennn der Wurzelknoten
     * selbst entfernt werden muss. Der neue Teilbaum wird daher wieder mit
     * ausgegeben
     * @param teilbaum Teilbaum aus dem ein Knoten entfernt werden soll
     * @param s der zu entfernende Knoten
     * @return Der verbleibende Restbaum. Es kann auch Null für einen leeren Baum ausgegeben werden
     */
    private Baumknoten entfernen(Baumknoten teilbaum, Baumknoten s) {
       Baumknoten result = teilbaum;
       if (teilbaum != null) {
         if (teilbaum.getWert()==s.getWert()) {
             // der aktuelle Knoten muss entfernt werden
            Baumknoten altRechts = teilbaum.getRechterK();
            Baumknoten altLinks = teilbaum.getLinkerK();
            if (altRechts != null) {
                result = altRechts;
                if (altLinks != null) einfuegen(result, altLinks);
            }
            else
                if (altLinks!=null) result = altLinks;
                else result = null;
         }
         else if (teilbaum.getWert()<s.getWert()) {
            Baumknoten k = teilbaum.getRechterK();
            teilbaum.setRechterK(entfernen(k,s));
            }
         else {
            Baumknoten k = teilbaum.getLinkerK();
            teilbaum.setLinkerK(entfernen(k,s));
            }
        }
        return result;
        }
    /**
     * Berechnung der Hoehe des Baums
     * @return Hoehe des Baums
     */
    public int hoehe() {
        if (wurzelKnoten == null) return 0;
        else                      return wurzelKnoten.hoehe();
    }
    /**
     * Rückgabe des Namens
     * @return
     */
    public String algorithmus() {return "Binaerbaum";}

public void druckenBaum() {
System.out.println("Tiefe:" + hoehe());
if (wurzelKnoten != null) wurzelKnoten.druckeUnterbaum(0);
System.out.println("A-----------A");
}
}

Baumschule...

Fragen zu Binärbäumen

Welche der beiden Bäume sind korrekte, streng sortierte Binärbäume?

Welche sind keine streng sortierten Binärbäume und warum?

Streng sortierter Binärbaum 1

Der Baum ist kein streng sortierter Binärbaum. Knoten 3 müsste rechter Sohn von Knoten 2 sein. Knoten 4 müsste rechter Sohn von Knoten 3 sein.

Streng sortierter Binärbaum 2

Der Baum ist ein streng sortierter Binärbaum.

AVL Bäume

Welche der beiden AVL-Bäume sind korrekte AVL-Bäume?

Welche Bäume sind keine korrekten AVL Bäume und warum?

AVL-Baum 1

Der Baum ist ein AVL-Baum. Alle Blätter sind auf nur zwei unterschiedlichen Ebenen angeordnet.

AVL Baum 2

Der Baum ist kein AVL Baum. Das Fehlen eines zweiten Sohns von Knoten B führt zu einem Unterschied von zwei Ebenen im Baum.

Bruder-Baum

 Welche der beiden Bäume sind keine korrekten Bruder-Bäume?

Warum sind sie keine Bruderbäume?

Bruder-Baum 1

Der Baum ist ein Bruder-Baum. Alle Blätter sind auf der untersten Ebene. Der einzige unäre Knoten B hat einen binären Bruderknoten.

Bruder-Baum 2

Der Baum ist kein Bruder-Baum. Der Blattknoten E ist nicht auf der untersten Ebene.

Bruder-Baum 3

Der Baum ist kein Bruder-Baum. Knoten B und C sind unäre Brüder. Einer von ihnen müsste binär sein.

Knoten B und C sind überflüssig. Nach ihrem Entfernen entsteht wieder ein Bruder-Baum.