2.4 Bäume (Binärbäume)

Synopsis: [Binärbaum] Viele Inhalte entnommen aus LFB 02L-baeume-arbeitsblatt.docx [u-helmich.de/inf/kursQ1/folge17/folge17.html]

Definitionen

1. Ein Blatt ist ein Knoten ohne Kinder.
2. Ein Halbblatt ist ein Knoten mit nur einem Kind.
3. Ein Binärbaum ist voll, wenn er keine Halbblätter hat.
4. Ein Pfad ist eine geordnete Liste von Knoten, die durch Kanten verbunden sind. Seine Länge ist die Anzahl der Kanten.
5. Höhe eines Knotens n, ist die Länge des längsten Pfades von n zu einem Blatt. Die Höhe eines Blattes ist immer 0. Die Höhe der Wurzel ist die Höhe des Baumes.
6. Die Tiefe eines Knotens n ist die Länge des Pfades von der Wurzel bis zum Knoten n.
7. Ein voller Binärbaum wird als vollständig bezeichnet, wenn alle Blätter die gleiche Tiefe haben.
8. Ein Baum hat keine Zyklen: Es handelt sich um einen Baum, wenn es zwischen zwei beliebig wählbaren Knoten nur einen Weg gibt.

Fragen zum Baum oben:

1. Nenne alle Blätter.
2. Nenne alle Halbblätter..
3. Ist der Baum voll?
4. Auf welcher Ebene ist Knoten 4?
5. Welche Höhe und Tiefe hat Knoten 5?
6. Welche Höhe und Tiefe hat Knoten 10?

Tiefendurchlauf

Gehe alle Knoten ausgehend vom Startknoten (Wurzel) durch. Es gibt 3 Reihenfolgen:

• Inorder: (L-K-R) Zuerst wird der linke Teilbaum L rekursiv durchlaufen, dann der Knoten K betrachtet und schließlich der rechte Teilbaum R rekursiv durchlaufen. Diese Reihenfolge entspricht bei binären Suchbäumen der Anordnung der Schlüssel und ist für die meisten Anwendungen die gegebene.
• Preorder: (K-L-R) Zuerst wird der Knoten K betrachtet und anschließend der linke L, schließlich der rechte Teilbaum R rekursiv durchlaufen.
• Postorder: (L-R-K) Zuerst wird der linke L, dann der rechte Teilbaum R rekursiv durchlaufen und schließlich der Knoten K betrachtet.

Ein Inorder-Tiefendurchlauf ergibt diese Zahlenfolge:
5, 10, 21, 7, 8, 2, 3, 0
Nennen Sie die Zahlenfolge für einen Preorder-Tiefendurchlauf:

Lösung

7, 10, 5, 21, 3, 2, 8, 0

Nennen Sie die Zahlenfolge für einen Postorder-Tiefendurchlauf:

Lösung

5, 21, 10, 8, 2, 0, 3, 7

Binärbaum implementieren

Ich habe hier auf die Klasse Typ verzichtet, mit Integer funktioniert es, falls ein eigener Typ verwendet werden soll muss beim Ausgeben Inhalt.ausgebenDaten() verwendet werden..

public class Binaerbaum <Typ>{
  private Knoten <Typ> wurzel;
  public Binaerbaum(){}
  public Binaerbaum(Typ e){
    wurzel = new Knoten(e); 
  }
  public Knoten <Typ> gibWurzel(){
    return wurzel;
  }
  public Knoten <Typ> gibLinkenTeilbaum(){
    return wurzel.gibLinkenTeilbaum();
  }
  public Knoten <Typ> gibRechtenTeilbaum(){
    return wurzel.gibRechtenTeilbaum();
  }
  public boolean istLeer(){
    return wurzel==null;
  }
  public void ausgebenDatenInorder(){
    wurzel.ausgebenDatenInorder();
  }
  public void ausgebenDatenPreorder(){
    wurzel.ausgebenDatenPreorder();  
  }
  public void ausgebenDatenPostorder(){
    wurzel.ausgebenDatenPostorder();  
  }
}

public class Test{
  public static void teste(){
    Knoten k,j; // zum einfacheren Baum-Bau
    System.out.print("\f"); // Konsole leeren
    Binaerbaum<Integer> b = new Binaerbaum(7);
    k=new Knoten(10);
    k.setzeLinkenTeilbaum(new Knoten(5));
    k.setzeRechtenTeilbaum(new Knoten(21));
    b.gibWurzel().setzeLinkenTeilbaum(k);
    k=new Knoten(2);
    k.setzeLinkenTeilbaum(new Knoten(8));
    j=new Knoten(3);
    j.setzeLinkenTeilbaum(k);
    j.setzeRechtenTeilbaum(new Knoten(0));
    b.gibWurzel().setzeRechtenTeilbaum(j);
    System.out.print("\n Inorder: ");
    b.ausgebenDatenInorder();
    System.out.print("\n Preorder: ");
    b.ausgebenDatenPreorder();
    System.out.print("\n Postorder: ");
    b.ausgebenDatenPostorder();
    System.out.print("\n Höhe: ");
    System.out.println(b.gibWurzel().gibHoehe());
  }
}

public class Knoten <Typ>{
  private Typ inhalt;
  private Knoten<Typ> linkerTeilbaum;
  private Knoten<Typ> rechterTeilbaum;
  public Knoten(Typ e){
    inhalt = e;    
  }
  public Typ gibInhalt(){
    return inhalt;
  }
  public Knoten <Typ> gibLinkenTeilbaum(){
    return linkerTeilbaum;
  }
  public Knoten <Typ> gibRechtenTeilbaum(){
    return rechterTeilbaum;
  }
  public void setzeLinkenTeilbaum(Knoten <Typ> k){
    linkerTeilbaum = k;
  }
  public void setzeRechtenTeilbaum(Knoten <Typ> k){
    rechterTeilbaum = k;
  } 
  public boolean istBlatt(){
      return linkerTeilbaum==null && rechterTeilbaum==null;
  }
  public void ausgebenDatenInorder(){
    if(linkerTeilbaum != null){
      linkerTeilbaum.ausgebenDatenInorder();
    }
    System.out.print(inhalt+" "); // inhalt.ausgebenDaten()
    if(rechterTeilbaum != null){
      rechterTeilbaum.ausgebenDatenInorder();
    }
  }
  public void ausgebenDatenPreorder(){
  }
  public void ausgebenDatenPostorder(){
  }
  public int gibHoehe(){
    int h=-1;
    ...
    return h+1;
  }
}

public void ausgebenDatenPreorder(){
    System.out.print(inhalt+" "); // inhalt.ausgebenDaten()
    if(linkerTeilbaum != null){
      linkerTeilbaum.ausgebenDatenPreorder();
    }
    if(rechterTeilbaum != null){
      rechterTeilbaum.ausgebenDatenPreorder();
    }
  }
  public void ausgebenDatenPostorder(){
    if(linkerTeilbaum != null){
      linkerTeilbaum.ausgebenDatenPostorder();
    }
    if(rechterTeilbaum != null){
      rechterTeilbaum.ausgebenDatenPostorder();
    }
    System.out.print(inhalt+" "); // inhalt.ausgebenDaten()
  }
  public int gibHoehe(){
    int h=-1;
    if(linkerTeilbaum != null){
      if (h<linkerTeilbaum.gibHoehe())h=linkerTeilbaum.gibHoehe();
    }
    if(rechterTeilbaum != null){
      if (h<rechterTeilbaum.gibHoehe())h=rechterTeilbaum.gibHoehe();
    }
    return h+1;
  }

public int gibHoehe() { // Lsg von Marcel Scherzinger
  int l = (linkerTeilbaum == null) ? -1 : linkerTeilbaum.gibHoehe();
  int r = (rechterTeilbaum == null) ? -1 : rechterTeilbaum.gibHoehe();
  return (r > l) ? r + 1 : l + 1;
}

Binärer Suchbaum

Ist ein spezieller Binärbaum, bei dem alle Knoteninhalte des linken Teilbaums kleiner und des rechten Teilbaums größer sind als der Inhalt des Knotens.

Aufgabe BS1: Prüfen Sie von der Wurzel aus, ob in dem Baum der Wert 14 enthalten ist. Welchen Weg müssen Sie durch den Baum dazu gehen? Nennen Sie die Zahlenfolge.

Lösung BS1

11 15 14

Aufgabe BS2: Fügen Sie den Wert 6 in den Baum ein. Nennen Sie den Knoten, an dem der Wert eingefügt wird und ob es der rechte oder linke Kindsknoten ist.

Lösung BS2

6 wird linker Kindknoten von 7

Aufgabe BS3: Gegeben ist die Zahlenfolge
15 3 0 7 5 9 33 16 37.
Zeichen Sie den binären Suchbaum, der entsteht, wenn Sie diese Zahlen der Reihe nach in den Baum einfügen.

Lösung BS3

Aufgabe BS4: Gegeben ist die Zahlenfolge
2 5 7 8 9 20 15 23
Zeichen Sie den binären Suchbaum, der entsteht, wenn Sie diese Zahlen der Reihe nach in den Baum einfügen.

Lösung BS4

Aufgabe BS5: Bestehen in dem entstandenen Baum noch die Vorteile eines binären Suchbaums? Begründen Sie Ihre Antwort.

Lösung BS5

Nein, die Vorteile des binären Suchbaums bestehen nahezu nicht mehr. Da die Elemente in einer nahezu sortierten Reihenfolge eingefügt wurden, entstand weitestgehend eine verkettete Liste. Um ein Element darin zu finden, müssen jetzt wieder schlimmstenfalls fast n Elemente durchlaufen werden.

Aufgabe BS6: Gegeben ist oberer Beispiel-Binärer-Suchbaum. Beschreiben Sie stichwortartig Ihr Vorgehen um..

Suchbaum implementieren

Synopsis: Bäume hübsch ausgeben [Stackoverflow] Als Inhaltstyp verwende ich folgend int.

import java.util.*;
public class BinaererSuchbaum <Typ>{
  private Knoten <Typ> wurzel;
  public BinaererSuchbaum(){}

  public BinaererSuchbaum(int e){ // Typ e
    wurzel = new Knoten(e); 
  }

  public Knoten <Typ> gibWurzel(){
    return wurzel;
  }

  public Knoten <Typ> gibLinkenTeilbaum(){
    return wurzel.gibLinkenTeilbaum();
  }

  public Knoten <Typ> gibRechtenTeilbaum(){
    return wurzel.gibRechtenTeilbaum();
  }

  public boolean istLeer(){
    return wurzel==null;
  }

  public void ausgebenDatenInorder(){
    System.out.print(wurzel.returnDatenInorder());
  }

  public void ausgebenDatenPreorder(){
    wurzel.ausgebenDatenPreorder();  
  }

  public void ausgebenDatenPreorderIterativ(){ // ohne Rekursion mit Stack
    Deque<Knoten> stack = new ArrayDeque<Knoten>();
    Knoten k;
    if (wurzel!=null) stack.push(wurzel);
    while(!stack.isEmpty()){
      k=stack.pop();
      if(k.gibRechtenTeilbaum()!=null) stack.push(k.gibRechtenTeilbaum());
      if(k.gibLinkenTeilbaum()!=null) stack.push(k.gibLinkenTeilbaum());
      System.out.print(k.gibInhalt()+" ");
    }
  }

  public void ausgebenDatenPostorder(){
    wurzel.ausgebenDatenPostorder();  
  }

  public void ausgebenDatenLevelorder(){ // Ebene fuer Ebene ausgeben
    wurzel.ausgebenDatenLevelorder();
  }

  public void ausgebenBaum(){ // Baum auf Konsole ausgeben
    wurzel.ausgebenBaum();
  }

  public void einfuegenElement (int e){// sortiert e einfuegen
    if (wurzel==null){
      wurzel = new Knoten (e);
    }
    else wurzel.einfuegenElement(e);
  }

  public void erstelleBaumAusListe(String s){ // aus String erstellen
    String[] elemente = s.split(" "); // in Elemente aufspalten
    for(int i=0;i<elemente.length;i++){ // alle Elemente einfuegen
      einfuegenElement(Integer.parseInt(elemente[i]));
    }
  }

  public void erstelleBaumAusListeOptimal(String s){ // minimale Hoehe
    String[] elemente = s.split(" "); // in Elemente aufspalten
    List<Integer> werte = new ArrayList<>(); // Liste von Integern
    for(int i=0;i<elemente.length;i++){ // In die Liste einfuegen
      werte.add(Integer.parseInt(elemente[i]));
    }
    Collections.sort(werte); // Liste aufsteigend sortieren!
    einfuegenSortListe(werte); // Hilfsfunktion
  }

  public void erstelleBaumAusListeOptimal2(String s){ // Vorher Nachher Demo
    erstelleBaumAusListe(s); // Baum erstellen Vorher
    ausgebenBaum();
    String sortiert = wurzel.returnDatenInorder(); // Inorder ist sortiert
    System.out.println(sortiert);
    String[] elemente = sortiert.split(" ");
    List<Integer> werte = new ArrayList<>();
    for(int i=0;i<elemente.length;i++){
      werte.add(Integer.parseInt(elemente[i]));
    }
    wurzel=null;
    einfuegenSortListe(werte); // Hilfsfunktion
    ausgebenBaum();
  }

  public void einfuegenSortListe(List<Integer> l){ // teile und herrsche
    if (l.size()>0){ // wenn Liste nicht leer
      int m=l.size()/2; // Mitte der Liste
      einfuegenElement(l.get(m)); // mittleres Element einfuegen
      einfuegenSortListe(l.subList(0,m)); // unterer Rest: Index von 0 bis m-1
      einfuegenSortListe(l.subList(m+1,l.size())); // oberer Rest: Index von m+1 bis size()-1
    }
  }

  public void ausgeben2D(){ // Danke Sabine
    wurzel.ausgebenBaum2D("", false, true);
  }

  public static void teste(){
    System.out.print("\f"); // Konsole leeren
    BinaererSuchbaum<Integer> b = new BinaererSuchbaum();
    b.erstelleBaumAusListe("7 10 6 12 8 4 9 24");
    //b.erstelleBaumAusListe("15 3 0 7 5 9 33 16 37");
    System.out.print("\n Inorder: ");
    b.ausgebenDatenInorder();
    System.out.print("\n Preorder: ");
    b.ausgebenDatenPreorder();
    System.out.print("\n PreorderIterativ: ");
    b.ausgebenDatenPreorderIterativ();
    System.out.print("\n Postorder: ");
    b.ausgebenDatenPostorder();
    System.out.print("\n Höhe: ");
    System.out.println(b.gibWurzel().gibHoehe());
    System.out.print("\n Levelorder: ");
    b.gibWurzel().ausgebenDatenLevelorder();
    System.out.println();
    b.gibWurzel().ausgebenBaum();
    b.ausgeben2D();
    System.out.println("Element 10 enthalten: "+(b.gibWurzel().enthaltenElement(10) ? "Ja":"Nein"));
    System.out.println("Element 16 enthalten: "+(b.gibWurzel().enthaltenElement(16) ? "Ja":"Nein"));
    System.out.println("Tiefe von 9: "+ b.gibWurzel().returnTiefe(9));
    System.out.println("Tiefe von 34: "+ b.gibWurzel().returnTiefe(34));
    System.out.println("Pfad zu 9: "+ b.gibWurzel().returnPfad(9));
    System.out.println("Pfad zu 34: "+ b.gibWurzel().returnPfad(34));
    System.out.println("Minimum: "+ b.gibWurzel().returnMin());
    System.out.println("Maximum: "+ b.gibWurzel().returnMax());
  }
  public static void testeOptEinfuegen(){
    System.out.print("\f"); // Konsole leeren
    BinaererSuchbaum<Integer> b = new BinaererSuchbaum();
    b.erstelleBaumAusListeOptimal2("15 3 0 7 5 9 33 16 37");
  }
}

import java.util.ArrayList;
public class Knoten <Typ>{
  private int inhalt; // Typ inhalt
  private Knoten<Typ> linkerTeilbaum;
  private Knoten<Typ> rechterTeilbaum;
  public Knoten(int e){ //Typ e
    inhalt = e;    
  }

  public int gibInhalt(){
    return inhalt;
  }

  public Knoten <Typ> gibLinkenTeilbaum(){
    return linkerTeilbaum;
  }

  public Knoten <Typ> gibRechtenTeilbaum(){
    return rechterTeilbaum;
  }

  public void setzeLinkenTeilbaum(Knoten <Typ> k){
    linkerTeilbaum = k;
  }

  public void setzeRechtenTeilbaum(Knoten <Typ> k){
    rechterTeilbaum = k;
  } 

  public boolean istBlatt(){
    return linkerTeilbaum==null && rechterTeilbaum==null;
  }

  public String returnDatenInorder(){ // gibt String in Inorder zurueck
    String s="";
    if(linkerTeilbaum != null){
      s+= linkerTeilbaum.returnDatenInorder();
    }
    s+= inhalt +" ";
    if(rechterTeilbaum != null){
      s+=rechterTeilbaum.returnDatenInorder();
    }
    return s;
  }

  public void ausgebenDatenPreorder(){
    System.out.print(inhalt+" "); // inhalt.ausgebenDaten()
    if(linkerTeilbaum != null){
      linkerTeilbaum.ausgebenDatenPreorder();
    }
    if(rechterTeilbaum != null){
      rechterTeilbaum.ausgebenDatenPreorder();
    }
  }

  public void ausgebenDatenPostorder(){
    if(linkerTeilbaum != null){
      linkerTeilbaum.ausgebenDatenPostorder();
    }
    if(rechterTeilbaum != null){
      rechterTeilbaum.ausgebenDatenPostorder();
    }
    System.out.print(inhalt+" "); // inhalt.ausgebenDaten()
  }

  public int gibHoehe(){
    int h=-1;
    if(linkerTeilbaum != null){
      if (h<linkerTeilbaum.gibHoehe())h=linkerTeilbaum.gibHoehe();
    }
    if(rechterTeilbaum != null){
      if (h<rechterTeilbaum.gibHoehe())h=rechterTeilbaum.gibHoehe();
    }
    return h+1;
  }

  public void ausgebenDatenLevelorder(){ // Ebene fuer Ebene ausgeben
    ArrayList <Knoten> schlange = new ArrayList<>(); // fuer Levelorder-Ausgabe
    Knoten k;
    schlange.add(this);
    while (!schlange.isEmpty()){
      k=schlange.remove(0); // hole den ersten Knoten
      System.out.print(k.gibInhalt()+" "); // Knoteninhalt ausgeben.
      if(k.gibLinkenTeilbaum() != null){
        schlange.add(k.gibLinkenTeilbaum());
      }
      if(k.gibRechtenTeilbaum() != null){
        schlange.add(k.gibRechtenTeilbaum());
      }
    }
  }

  public void ausgebenBaum(){ // Auf Konsole ausgeben
    ArrayList <Knoten> ebeneOben = new ArrayList<>(); // Schlange
    ArrayList <Knoten> ebeneUnten;
    int i,h,l,hoehe,leerzeichen;
    ebeneOben.add(this);
    hoehe = gibHoehe();
    leerzeichen = (int)Math.pow(2,hoehe);
    for(h=0;h<=hoehe;h++){ // alle Ebenen ausgeben
      ebeneUnten= new ArrayList<>(); // darunterliegende Ebene
      for (i=0;i<ebeneOben.size();i++){ // alle Knoten der Ebene
        for(l=0;l<leerzeichen;l++)System.out.print("  "); // Einruecken
        if(ebeneOben.get(i)!=null){
          System.out.printf("%2d",ebeneOben.get(i).gibInhalt());
          ebeneUnten.add(ebeneOben.get(i).gibLinkenTeilbaum());
          ebeneUnten.add(ebeneOben.get(i).gibRechtenTeilbaum());
        }
        else{
          System.out.print("  ");
          ebeneUnten.add(null); // Dummys hinzufuegen
          ebeneUnten.add(null);
        }
        for(l=0;l<leerzeichen-1;l++)System.out.print("  ");
      }
      System.out.println();
      ebeneOben=ebeneUnten;
      leerzeichen/=2; // halb so viel einruecken
    }
  }

  public void ausgebenBaum2D(String praefix, boolean istLinks, boolean istOberster) { // Danke Sabine
    if (rechterTeilbaum != null) {  // Rechten Teilbaum ausgeben
      if (istLinks && !istOberster)
        rechterTeilbaum.ausgebenBaum2D(praefix + "|   ", false, false); // Richtungsumkehr --> Strich zeichnen
      else 
        rechterTeilbaum.ausgebenBaum2D(praefix + "    ", false, false);
    }
    if (istLinks) // Knoten selbst ausgeben
      System.out.println(praefix + "└── " + gibInhalt());
    else if (istOberster)
      System.out.println(praefix + "─── " + gibInhalt());
    else 
      System.out.println(praefix + "┌── " + gibInhalt());
    if (linkerTeilbaum != null) { // Linken Teilbaum ausgeben
      if (istLinks || istOberster)
        linkerTeilbaum.ausgebenBaum2D(praefix + "    ", true, false);
      else 
        linkerTeilbaum.ausgebenBaum2D(praefix + "|   ", true, false); // Richtungsumkehr --> Strich zeichnen
    }
  }

  public boolean enthaltenElement(int e){ // Aufgabe
    
    return false;
  }

  public void einfuegenElement(int e){ // Aufgabe nochmal selber programmieren, hier nicht spicken
    if(inhalt==e){
      System.out.println("Element schon enthalten: "+e);
    }
    else{
      if(e < inhalt){
        if(linkerTeilbaum==null){
          linkerTeilbaum= new Knoten(e);
        }
        else linkerTeilbaum.einfuegenElement(e);
      }
      else{
        if(rechterTeilbaum==null){
          rechterTeilbaum= new Knoten(e);
        }
        else rechterTeilbaum.einfuegenElement(e);
      }
    }
  }

  public int returnTiefe(int e){ // Aufgabe
    int t;
    
    return -1;
  }

  public String returnPfad(int e){ // Aufgabe
    
    return "Nicht gefunden";
  }
}

Aufgaben zu Suchbaum

Vervollständigen Sie diese Operationen der Klasse Knoten:

• enthaltenElement(int e):Boolean, die in einem sortierten Baum das Vorhandensein eines Elements zurück gibt.
• einfügenElement2(int e), die ein Element e sortiert in den Baum einfügt. Vereinfachend wird hier vom Typ Integer ausgegangen bei anderen Element-Typen müssen wir uns Gedanken über eine Metrik, also eine Verlgeichsfunktion für Inhalte machen. Versuchen Sie es nochmal selber ohne auf einfügenElement(int e) zu spicken. Diese Funktion wird elementar benötigt um überhaupt bequem Bäume bauen zu können.

  public boolean enthaltenElement(int e){ //Typ e
    if(inhalt==e) return true;
    if(linkerTeilbaum!=null && linkerTeilbaum.enthaltenElement(e)
    || rechterTeilbaum!=null && rechterTeilbaum.enthaltenElement(e)) return true;
    return false;
  }

  public void einfuegenElement(int e){ // sortiertes Einfuegen
    if(inhalt==e){
      System.out.println("Element schon enthalten: "+e);
    }
    else{
      if(e < inhalt){
        if(linkerTeilbaum==null){
          linkerTeilbaum= new Knoten(e);
        }
        else linkerTeilbaum.einfuegenElement(e);
      }
      else{
        if(rechterTeilbaum==null){
          rechterTeilbaum= new Knoten(e);
        }
        else rechterTeilbaum.einfuegenElement(e);
      }
    }
  }

Erstellen Sie Operationen der Klasse Knoten:

• returnMin():GZ, die das Minimum des (Teil-) Baums zurückgibt.
• returnMax():GZ, die das Maximum des (Teil-) Baums zurückgibt.
• returnTiefe(int e):GZ, die die Tiefe des Elementknotens von e zurückgibt. Wird der Knoten nicht gefunden wird -1 zurück gegeben.
• returnPfad(int e):Text, die den Such-Pfad zu einem Element e zurückgibt. Wenn das Element am Ende nicht gefunden wird steht am Ende des Textes “Nicht gefunden”.

  public int returnMin(){
    if(linkerTeilbaum==null) return inhalt;
    return linkerTeilbaum.returnMin();
  }
  public int returnMax(){
    if(rechterTeilbaum==null) return inhalt;
    return rechterTeilbaum.returnMax();
  }
  public int returnTiefe(int e){ //Typ e
    int t;
    if(inhalt==e) return 0;
    if(e<inhalt && linkerTeilbaum!=null){
      t=linkerTeilbaum.returnTiefe(e);
      if(t<0)return-1;
      return 1+t;
    }
    else{
      if(rechterTeilbaum!=null){
        t=rechterTeilbaum.returnTiefe(e);
        if(t<0)return-1;
        return 1+t;
      }
    }
    return -1;
  }
  public String returnPfad(int e){ //Typ e
    String s ="";
    s+=inhalt;
    if(inhalt==e) return s;
    if(e<inhalt && linkerTeilbaum!=null){
      return s+=" "+linkerTeilbaum.returnPfad(e);
    }
    else{
      if(rechterTeilbaum!=null){
        return s+=" "+rechterTeilbaum.returnPfad(e);
      }
    }
    return "Nicht gefunden";
  }

Bonus: loescheElement(int e):Boolean, das ein Element e aus dem Baum löscht. Die Rückgabe ist false, wenn das Element nicht gefunden wurde.

Ich habe noch keine Lösung…

Syntaxbaum

Synopsis: [Syntaxbaum] [Umgekehrte polnische Notation]

Hier vereinfacht auf Terme beschränkt.
Der Auswertebaum für diesen Term 3 * 4 + 8, wie wird der Baum ausgewertet?

Wir sind es gewohnt, Terme in Inorder-Darstellung zu schreiben. In den 80ern nutzte ich einen genialen Taschenrechner (HP-41CV) der UPN beherrschte, man gab den Term in Postorder ein und brauchte keine Klammern.
Geben Sie den Syntaxbaum in Postorder aus:

Lösung

3 4 * 8 +

Aufgaben

Erstellen Sie den Auswertebaum und ermitteln Sie die Ergebnisse [Prioritäten der Operatoren] für:

• (2 + 7) * 10
• 2 – 3 * -2
• sqrt(2+3)+Pi
• 4 | 2 == 4 / 2
• 3 & 4 << 2 + 3
• a = b = 0b10 << 4

ToDo: Parser für Ausdrücke, eval-Operation für Knoten