Preorder / Postorder Traversierung

[MrTiger]

Hallo

Ich habe ein kleines Problem mit der Baumtraversierung. Und zwar ist ein Baum vorhanden (ein DOM Tree). Alle Knoten des Baumes sind vom selben Typ XML_NODE. Der root des Baumes ist durch root: XML_NODE referenziert (Eiffel Syntax), d.h. 'root' vom Typ XML_NODE zeigt auf den root node. Die Kinder sind durch die Methode elements abrufbar, welches eine Liste mit den Kindern zurückgibt. Also z.B. root.elements.

Nun möchte ich zwei Funktion 'next_preorder' und 'next_postorder' implementieren, die mir bei jedem Aufruf das nächste Element in preorder bzw. postorder Reihenfolge zurückgibt.

Ich habe zwar bereits Algorithmen gefunden, die einen Baum in postorder bzw. preorder Reihenfolge durchlaufen, aber da wird eben gerade der ganze Baum durchlaufen (ich möchte nur das jeweils nächste Element) und zudem sind diese Algorithmen meisten für 2 Kinder, ich habe aber eine Liste von Kindern.

Könnte da vielleicht kurz jemand mit Pseudocode (oder in Java) zu Hilfe eilen?

Ich danke vielmals.

 

[timestamp]

Übernehme doch einfach den Code, und wandel ihn so ab, das nur jeweils das erste Element holt. Das Startelement gibt's du dann vor, was dann entsprechend immer das zuletzt geholte Element ist.

 

[MrTiger]

Vielen Dank. Ich werde es ausprobieren.

 

[MrTiger]

So Preorder habe ich erfolgreich hinbekommen. Das sieht bei mir wie folgt aus.

class TreeNode {
        String data;        
        Collection<TreeNode> children;
}


class TreePreorderIterator implements Iterator {

        private final List<TreeNode> toVisit;

        TreePreorderIterator(TreeNode root) {
                toVisit = new LinkedList<>();
                toVisit.push(root);
        };

        boolean hasNext() {
                return toVisit.size() > 0;
        }

        TreeNode next() {
                TreeNode node = toVisit.pop();
                for (child : node.children) {
                        toVisit.push(child);
                }
                return node;
        }
}

Der Durchlauf ist iterativ mit einem Stack und nicht rekursiv, da mit der next Methode immer nur der nächste Knoten zurückgegeben werden soll.

Nun möchte ich das genau gleiche auch noch für Postorder machen, aber das krieg ich irgendwie nicht hin. Das Problem ist halt, dass nicht immer zuerst der Vater Knoten besucht wird, wie bei Preorder, da ist es dann mit dem Stack ja ganz leicht.

Könnte mir vielleicht kurz jemand den obigen Code in Postorder umwandeln? Wäre sehr lieb.