Vorlesung Informatik 2 - Teil B: Theorie

4.3 Binärbaum erzeugen

Nehmen wir an, wir wollen eine Datenquelle, z.B. die Buchstaben ABCDEFG in einem Binärbaum anordnen. Ohne nachzudenken würden wir wahrscheinlich folgenden Baum aufzeichnen:

                       A
                      / \
                     B    C
                    / \  / \
                   D   E F  G

Wir haben angenommen, dass unsere Buchstaben in der sogenannten Level-Order des Baumes angeordnet sind - aber dazu später.

Wenn wir statt unseres intuitive Vorgehens einem Algorithmus formulieren sollen, wird es kniffliger. Es ist klar, dass wir eine Schleife über unsere Datenquelle machen müssen, aber woher wissen wir, welches der Vaterknoten zum jeweils nächsten Wert aus der Datenquelle ist?

Der entsprechende Algorithmus nutzt verwendet eine Queue als Pufferspeicher:

Zunächst wird das erste Objekt aus der Quelle genommen und in den Puffer eingefügt. Dieses Objekt wird die Wurzel das Baums.

  • In einer Schleife über die restlichen Element der Quelle wird:
    1. das  nächste Objekt aus der Queue geholt und als aktueller Knoten gespeichert .
    2. die beiden nächsten Objekte aus der Quelle als linkes und rechtes Kind an den aktuellen Knoten gehängt
    3. die beiden  Kind-Objekte in den Puffer eingefügt.

Im Beispiel sehen die Schritte so aus:

Quelle als Queue   --> GFEDCBA  -->
Schritt     Quelle                                      Baum                                 Puffer ---------------------------------------------------------------------------------------------------- Start GFEDCBA leer - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 GFEDCB A - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 A / \ GFED B C CB - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 B / \ GF D E ECD - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3 c C / \ leer F G GFED ----------------------------------------------------------------------------------------------------

Man sieht wie aus dem Puffer immer der richtige Knoten geholt wird, der zum Vater der nächsten zwei Objekte der Quelle wird. 

Wenn der Algorithmus terminiert, befinden sich im Puffer nur noch die Blätter des Baumes.


Als pseudo-Code:

  Baum wurzel = new Baum(quelle.poll())
  puffer.offer(wurzel);
  while(!quelle.isEmpty()){
      Baum aktuellerKnoten = puffer.poll();
      Baum kindLinks = new Baum(quelle.poll());
      aktuellerKnoten.setLinks(kindLinks);
      puffer.offer(kindLinks);
      if(!quelle.isEmpty()){
           Baum kindRechts = new Baum(quelle.poll());
           aktuellerKnoten.setRechts(kindRechts);
           puffer.offer(kindRechts);
     }
   }


Lehrvideo