Traversierung

[minzee]

Hi

Ich habe mir einen Iterator für eine inorder-Traversierung durch einen Binärbaum programmiert.

Es geht um die Klasse InOrderTraverse (die restlichen Klassen einfach ignorieren, sie dienen nur zum Testen).

import java.util.Enumeration;
import java.util.Stack;

class O
{
   public int value;
   public O(int value)
   {
      this.value = value;
   }
}

class BinaryTree
{
   public BinaryTree left = null;
   public BinaryTree right = null;
   public O o = null;
   
   /**
    * Sortiert einfügen.
    * In linken subtree alle Werte < dem eigenen Wert. Ansonst in rechten subtree.
    * @param O o
    */
   public void insert(O o)
   {
      if(this.o == null)
      {
         this.o = o;
      }
      else if(o.value < this.o.value)
      {
         // links weiter
         if(left == null)
         {
            // noch kein subtree vorhanden
            left = new BinaryTree();
         }
         left.insert(o); // insert-Befehl in subtree weiterdelegieren
      }
      else
      {
         // rechts weiter
         if(right == null)
         {
            // noch kein subtree vorhanden
            right = new BinaryTree();
         }
         right.insert(o); // insert-Befehl in subtree weiterdelegieren
      }
   }
}

class BinaryTreeTraverse
{
   static void inOrder(BinaryTree t)
   {
      if(t != null)
      {
         inOrder(t.left); // linker subtree
         System.out.println(t.o.value);
         inOrder(t.right); // rechter subtree
      }
   }
}

class InOrderTraverse implements Enumeration<O>
{
   private Stack<BinaryTree> stack;
   
   public InOrderTraverse(BinaryTree t)
   {
      stack = new Stack<BinaryTree>();
      left(t);
   }
   private void left(BinaryTree t)
   {
      while(t != null)
      {
         stack.push(t);
         t = t.left;
      }
   }
   public boolean hasMoreElements()
   {
      return !stack.isEmpty();
   }
   public O nextElement()
   {
      BinaryTree t = stack.pop();
      left(t.right);
      return t.o;
   }
}

class Tree
{
   public static void main(String[] args) 
   {        
      /*
      // Test 1:
      
      BinaryTree t = new BinaryTree();
      t.insert(new O(7));
      t.insert(new O(2));
      t.insert(new O(1));
      t.insert(new O(0));
      t.insert(new O(3));
      t.insert(new O(5));
      t.insert(new O(4));
      t.insert(new O(6));
      t.insert(new O(8));
           
      BinaryTreeTraverse.inOrder(t);
      System.out.println("-----------------");
      
      Enumeration<O> e = new InOrderTraverse(t);
      while(e.hasMoreElements())
      {
         O o = e.nextElement();
         System.out.println(o.value);
      }*/
      
      // Test 2:
      
      BinaryTree t = new BinaryTree();
      t.insert(new O(1));
      t.insert(new O(0));
      t.insert(new O(6));
      t.insert(new O(5));
      t.insert(new O(3));
      t.insert(new O(2));
      t.insert(new O(4));
      t.insert(new O(7));
      t.insert(new O(8));
      
      BinaryTreeTraverse.inOrder(t);
      System.out.println("-----------------");
      
      Enumeration<O> e = new InOrderTraverse(t);
      while(e.hasMoreElements())
      {
         O o = e.nextElement();
         System.out.println(o.value);
      }
   }
}

Programmiert man eine inorder-Traversierung auf diese Weise? Mit 2 Beispielen scheint das zu funktionieren. Ist das OK? Oder programmiert man das irgendwie anders?

 

[JavaMeister]

Ich habe es nicht laufen lassen, aber das sieht total verdreht aus. Es könnte eine in Order sein, aber sehen tut man das hier nicht.

Ich frage mich, wieso du sowas machst. Klar ist, dass man ein Problem auf hundert Arten lösen kann. Es gibt auch viele richtige.

Aber diese Lösung ist eher durch den Rücken in die Nase und dann wird das Essen in den Mund geschoben Variante.

Und dann auch noch teilweise iterativ und teilweise rekursiv. Ich glaube das kann man sich hier sparen ;D

Wo man eine schöne Muster-Implementierung findet, überlasse ich deiner Kreativität.

 

[minzee]

Ich hätte schon was gefunden gehabt im Internet, aber dort wurden auch im hasMoreElements Einträge in den Stack gemacht. Das wollte ich mir sparen. Danach hatte ich ehrlich gesagt nicht weitergesucht, sondern selbst überlegt, wie man das machen könnte.

Eine postOrder-Traversierung hätte ich jetzt vielleicht auch hinbekommen. Aber die schaut im Grunde genommen so ähnlich aus (aber leider noch komplizierter).

class BinaryTreeTraverse
{
   static void postOrder(BinaryTree t)
   {
      if(t != null)
      {
         postOrder(t.left); // linker subtree
         postOrder(t.right); // rechter subtree
         System.out.println(t.o.value);
      }
   }
}

class EnumerationElement
{
   public BinaryTree t;
   public boolean down;
   
   public EnumerationElement(BinaryTree t, boolean down)
   {
      this.t = t;
      this.down = down;
   }
}

class PostOrderTraverse implements Enumeration<O>
{
   private Stack<EnumerationElement> stack;
   
   public PostOrderTraverse(BinaryTree t)
   {
      stack = new Stack<EnumerationElement>();
      down(t);
   }
   private void down(BinaryTree t)
   {
      while(t != null)
      {
         if(t.left != null)
         {
            stack.push(new EnumerationElement(t, true));
            t = t.left;
         }
         else
         {
            stack.push(new EnumerationElement(t, false));
            t = t.right;
         }
      }
   }
   public boolean hasMoreElements()
   {
      return !stack.isEmpty();
   }
   public O nextElement()
   {
      EnumerationElement e = stack.peek();
      if(e.down)
      {
         e.down = false;
         down(e.t.right);
      }
      e = stack.pop();
      return e.t.o;
   }
}

class Tree
{
   public static void main(String[] args) 
   {      
      /*BinaryTree t = new BinaryTree();
      t.insert(new O(7));
      t.insert(new O(2));
      t.insert(new O(1));
      t.insert(new O(0));
      t.insert(new O(3));
      t.insert(new O(5));
      t.insert(new O(4));
      t.insert(new O(6));
      t.insert(new O(8));
      
      BinaryTreeTraverse.postOrder(t);
      System.out.println("-----------------");
      
      Enumeration<O> e = new PostOrderTraverse(t);
      while(e.hasMoreElements())
      {
         O o = e.nextElement();
         System.out.println(o.value);
      }*/
      
      BinaryTree t = new BinaryTree();
      t.insert(new O(1));
      t.insert(new O(0));
      t.insert(new O(6));
      t.insert(new O(5));
      t.insert(new O(3));
      t.insert(new O(2));
      t.insert(new O(4));
      t.insert(new O(7));
      t.insert(new O(8));
      
      BinaryTreeTraverse.postOrder(t);
      System.out.println("-----------------");
      
      Enumeration<O> e = new PostOrderTraverse(t);
      while(e.hasMoreElements())
      {
         O o = e.nextElement();
         System.out.println(o.value);
      }
   }
}

Als Vorlage hatte ich eine PreOrder-Traversierung. Ein Professor unterrichtet die folgendermaßen:

class PreOrderTraverse implements Enumeration<O>
{
   private Stack<BinaryTree> stack;
   
   public PreOrderTraverse(BinaryTree t)
   {
      stack = new Stack<BinaryTree>();
      if(t != null)
      {
         stack.push(t);
      }
   }
   public boolean hasMoreElements()
   {
      return !stack.isEmpty();
   }
   public O nextElement()
   {
      BinaryTree t = stack.pop();
      if(t.right != null)
      {
         stack.push(t.right);
      }
      if(t.left != null)
      {
         stack.push(t.left);
      }
      return t.o;
   }
}

Wenn das noch einfacher geht, dann bin ich auf jeden Fall daran interessiert!

 

[minzee]

Ich glaube, ich habe eine bessere Möglichkeit für die postOrder-Traversierung gefunden:

/**
 * Einen Binär-Baum traversieren in der postOrder-Variante.
 */
class PostOrderTraverse implements Enumeration<O>
{
   private Stack<BinaryTree> stack;
   private BinaryTree previous;
   
   /**
    * @param BinaryTree t
    */
   public PostOrderTraverse(BinaryTree t)
   {
      stack = new Stack<BinaryTree>();
      previous = null;
      down(t); // stack auf die erste Abfrage vorbereiten
   }
   /**
    * Ausgehend von t immer weiter den subtree immer weiter nach unten durchlaufen bis ein leaf erreicht wird.
    * Dabei immer möglichst weit links halten.
    * @param BinaryTree t   
    */
   private void down(BinaryTree t)
   {
      while(t != null)
      {
         if(t.left != null)
         {
            stack.push(t);
            t = t.left;
         }
         else
         {
            stack.push(t);
            t = t.right;
         }
      }
   }
   /**
    * Ob es noch weitere Knoten im Baum gibt.
    * @return boolean
    */
   public boolean hasMoreElements()
   {
      return !stack.isEmpty();
   }
   /**
    * Holt den nächsten Knoten aus den Baum.
    * @return O 
    */
   public O nextElement()
   {
      BinaryTree t = stack.peek();

      // stack auf die nächste Abfrage vorbereiten:
      if(t.right != previous)
      {
         down(t.right);
      }
      previous = t = stack.pop(); // BinaryTree in previous merken
      // Eigentlich könnte man sich die t-Zuweisung sparen. Man könnte danach statt dem return t.o gleich
      // ein previous.o programmieren. Allerdings verwirrt das. Darum erfolgt hier aus Gründen der Lesbarkeit
      // auch eine t-Zuweisung.

      return t.o;
   }
}

Statt EnumerationElement-Instanzen verwende ich jetzt previous. Darin merke ich mir, welcher Wert zuletzt ausgegeben wurde.

Damit erspart man sich etwas Arbeitsspeicher.

Was sagt ihr dazu?