TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 13

Der abstrakte Datentyp Stack stellt die folgenden Operationen bereit:

• S.size(): gibt die Anzahl der Elemente auf dem Stack S zurück
• S.push(x): legt das Element x auf dem Stack S ab
• S.pop(): gibt das oben liegende, d.h. das zuletzt eingefügte Element zurück und löscht es aus dem Stack S

Schreiben Sie detaillierten Pseudocode für eine iterative Version der Inorder-Durchmusterung eines Binärbaumes. Verwenden Sie dazu die oben beschriebene Datenstruktur Stack. Auf die Wurzel des Binärbaumes kann über die Zeigervariable root zugegriffen werden. Weiters enthält jeder Knoten k des Baumes die Eigenschaften:

• k.key: der Schlüssel des Knotens
• k.left: ein Verweis auf das linke Kind (oder NULL)
• k.right: ein Verweis auf das rechte Kind (oder NULL)

Möglichkeit A: Javacode

Hier eine Möglichkeit, wie dieses Beispiel zu lösen wäre - funktioniert übrigens auch wirklich!

public static void InOrderStack(Knoten root)
{
   Stack<Knoten> s = new Stack<Knoten>();
   boolean end = false;
		
   while(!end)
   {
        if(root!=null)
        {
	    s.push(root);
            root = root.left;
        }
        else
        {
	    if(s.size() > 0)
            {
		root = s.pop();
		System.out.print(root.key + " ");
		root = root.right;
	    }
            else
		end = true;
	}
   }
}

Quelle: Informatik-Forum

Möglichkeit B: Pseudocode

solange fertig = falsch {
  wenn root <> NULL {
    s.push(root.left);
  } anderfalls {
    wenn s.size() > 0 {
      root = s.pop();
      gib root.key aus;
      root = root.right;
    } andernfalls {
      fertig = wahr;
    }
  }
}