Prof. Uwe Schulz

Vorlesung Informatik 2 - Teil B: Theorie

4.5 Der Level-Order Algorithmus

Um die Level Order eine Baumes zu generieren, brauchen wir wieder eine Queue als Pufferspeicher, ähnlich wie beim Erzeugen eins Binärbaumes aus seiner Level-Order (siehe Kapitel 4.3).

Der Algorithmus besteht aus fogenden Schritten:

• Die Wurzel des Baums wird in den Pufferspeicher eingefügt,
• Solange der Puffer nicht leer ist, werden:

1. das oberste Element aus dem Puffer geholt und bearbeitet,
2. das linke und rechte Kind in den Puffer eingefügt

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

Als Pseudo-Code:

   while(!puffer.isEmpty()){
         Baum aktuellerKnoten = puffer.poll();
         bearbeiter.bearbeite(aktuellerKnoten);
         if(aktuellerKnoten.links!=null) puffer.offer(aktuellerKnoten.links);              
         if(aktuellerKnoten.rechts!=null) puffer.offer(aktuellerKnoten.rechts);
   }