Kurs:Algorithmen und Datenstrukturen/Vorlesung/Traversierung

Traversierung

Auf dieser Seite wird das Thema Traversierung behandelt.

Traversierung kann durch die Methoden Preorder, Inorder, Postorder oder Levelorder erfolgen. Des weiteren kann sie mit Hilfe von Iteratoren erfolgen, dabei muss aber der Traversierungszustand zwischengespeichert werden.

Bei der Traversierung werden systematisch alle Knoten des Baumes durchlaufen.

Preorder: $A\to B\to D\to E\to C\to F\to G$

Inorder: $D\to B\to E\to A\to F\to C\to G$

Postorder: $D\to E\to B\to F\to G\to C\to A$

Levelorder: $A\to B\to C\to D\to E\to F\to G$

Traversierung mit Iteratoren

Bei der Traversierung sind Iteratoren erlaubt. Diese werden schrittweise abgearbeitet und es werden Standardschleifen für die Baumdurchläufe verwendet.

 for  (Integer i : tree) 
              System.out.print(i);

Dabei ist es allerdings notwendig, dass der Bearbeitungszustand zwischengespeichert wird.

public class BinarySearchTree<K extends Comparable<K>>
      implement Iterable<K> {

   public static final int INORDER = 1;  
   public static final int PREORDER = 2;
   public static final int POSTORDER = 3;
   public static final int LEVELORDER = 4;

   private int iteratorOrder;
    ...

  public void setIterationOrder(int io) {
      if (io < i || io > 4)
          return;
      iteratorOrder = io;
  }
 public Iterator<K> iterator() {
     switch (iterationOrder) { 
         case INORDER:
            return new InorderIterator<K>(this);
         case PRORDER:
            return new PreorderIterator<K>(this);
         case POSTORDER:
            return new PostorderIterator<K>(this);
         case LEVELORDER:
            return new LevelorderIterator<K>(this);
         default:
            return new InorderIterator<K>(this);
     }
 }

Preorder Traversierung

Bei der Preorder Traversierung wird der aktuelle Knoten zuerst behandelt und dann der linke oder rechte Teilbaum.

static class TreeNode<K extends Comparable<K>> {
  ...
  public void traverse() {
      if (key==null)
          return;
      System.out.print(” ” + key);
      left.traverse();
      right.traverse();   
  }

Preorder Iteratoren

Der Wurzelknoten wird auf den Stack gelegt, anschließend der rechte Knoten und dann der linke Knoten.

 class PreorderIterator<K extends Comparable <K>>
         implements Iterator<K> {

     java.util.Stack<TreeNode<K>> st =
         

     public PreorderIterator(BinarySearchTree<K> tree){
                st.push(tree.head.getRight());
                
     }
  public boolean hasNext() { 
          return !st.isEmpty();
  } 
  
   public K next(){ 
       TreeNode<K> node = st.pop();
       K obj = node.getKey(); 
       node = node.getRight();
       if(node != nullNode) {
          st.push(node); 
       }
       if(node != nullNode) {
          st.push(node);
       } 
       return obj;
   } 
}

Inorder Traversierung

Bei der Inorder Traversierung wird zuerst der linke Teilbaum behandelt, dann der aktuelle Knoten und dann der rechte Teilbaum. Als Ergebnis erhällt man den Baum in sortierter Reihenfolge.

static class TreeNode<K extends Comparable<K>> {
  ...
  public void traverse() {
      if (key==null)
          return;
      left.traverse();
      System.out.print(” ” + key);
      right.traverse();   
  }

Inorder Iteratoren

Der Knoten head hat immer einen rechten Nachfolger. Es wird vom Wurzelknoten begonnen alle linken Knoten auf den Stack zu legen.

 class InorderIterator<K extends Comparable <K>>
         implements Iterator<K> {

     java.util.Stack<TreeNode<K>> st =
         new java.util.Stack<TreeNode<K>>();

     public InorderIterator(BinarySearchTree<K> tree) {
           TreeNode<K> node = tree.head.getRight();
           while (node != nullNode) {
                st.push(node);
                node = node.getLeft();
           }
    }
  public boolean hasNext() {
          return !st.isEmpty();
  }
  
   public K next(){
       TreeNode<K> node = st.pop();
       K obj = node.getKey();
       node = node.getRight();
       while (node != nullNode) {
          st.push(node);
          node = node.getLeft();
       }
       return obj;
   }

}

Postorder Traversierung

Bei der Postorder Traversierung wird zuerst der linke Teilbaum behandelt und dann der aktuelle Knoten.

static class TreeNode<K extends Comparable<K>> {
  ...
  public void traverse() {
      if (key==null)
          return;
      left.traverse();
      right.traverse();   
      System.out.print(” ” + key);
  }

Levelorder Iteratoren

Der Wurzelknoten wird in der Warteschlange eingefügt. Dann wird zuerst der linke und dann der rechte Knoten in die Warteschlange eingefügt.

 class LevelorderIterator<K extends Comparable <K>>
         implements Iterator<K> {

   java.util.Queue<TreeNode<K>> q =
         new java.util.LinkedList<TreeNode<K>>();

   public LevelorderIterator(BinarySearchTree<K> tree){
         TreeNode<K> node = tree.head.getRight();
         if (node != nullNode)
                q.addLast(node);}
  
   public K next(){
       TreeNode<K> node = q.getFirst();
       K obj = node.getKey();
       if (node.getLeft() != nullNode)
            q.addLast(node.getLeft());
       if (node.getRight() != nullNode)
            q.addLast(node.getRight());
       return obj;
   }
}

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14.2.2 zu finden.