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.

[Xin]

Nur, damit wir uns nicht missverstehen, wiederhole ich, was ich verstanden habe.

Du hast einen beliebigen Knoten und möchtest dessen Nachfolger, bzw. dessen Vorgänger wissen!? Du hast eine Liste von Kindern pro Knoten.

Nehmen wir an, Du hast einen Baum mit Root (r), der zwei Kinder hat (a,b) und a hat ebenfalls zwei Kinder (aa, ab). Wenn Du aa fragst, wer der nächste ist, dann sind da keine Kinder, also muss man hoch zu Parent (a). In der Liste müsstest Du Dich selbst dann finden, der Nachfolger wäre also ab.

Der Nachfolger von ab ist in der Kinderliste nicht zu finden, also wäre Parent (a) bei PostOrder, bei PreOrder wäre (a) ja bereits gedruckt und man müsste zum Parent (r), dort in der Liste a suchen und den Nachfolger nehmen: b. b hat keine Kinder, also wieder Parent (r) und bei PostOder nehmen, weil es keinen Nachfolger in der Liste gibt oder bei PreOrder sehen, dass es kein Parent gibt und fertig.

Hier hätten wir also einen Algorithmus.
Du könntest noch einen Stack nehmen, um Dir zu merken, wen Du schon besucht hast, um nicht laufend Dich selbst in der Parent-Liste zu suchen.

[MrTiger]

Vielen Dank Xin. Jetzt ist mir ein Licht aufgegangen und ich denke ich kann es implementieren, sonst frage ich nochmal nach.

[Xin]

Tu Dir keinen Zwang an... für Pseudocode war die Zeit zu knapp, deswegen hoffte ich, dass das reichte.

[MrTiger]

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

Code: Alles auswählen

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.

[Xin]

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.

Im Prinzip musst Du den Stack nur andersrum aufbauen. has Next ist true, wenn size() > 1 ist oder size() == 1 und der Node Kinder besitzt.
Ein Node, denn Du abgearbeitet hast, nimmst Du aus Deiner Liste vorne raus und schiebst seine Kinder vorne rein.

Also root rein: Hasnext? Ja, weil root Kinder hat.
Next(): root ist abgearbeitet, also root raus also die Kinder rein.