Preorder / Postorder Traversierung

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Preorder / Postorder Traversierung

    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.

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

    Quellcode

    1. class TreeNode {
    2. String data;
    3. Collection<TreeNode> children;
    4. }
    7. class TreePreorderIterator implements Iterator {
    9. private final List<TreeNode> toVisit;
    11. TreePreorderIterator(TreeNode root) {
    12. toVisit = new LinkedList<>();
    13. toVisit.push(root);
    14. };
    16. boolean hasNext() {
    17. return toVisit.size() > 0;
    18. }
    20. TreeNode next() {
    21. TreeNode node = toVisit.pop();
    22. for (child : node.children) {
    23. toVisit.push(child);
    24. }
    25. return node;
    26. }
    27. }
    Alles anzeigen



    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.

  • Also ich weiß nicht ob das klar ist, aber preorder und postorder sagen erst mal "nichts" über die Reihenfolge aus, in der die einzelnen Knoten besucht werden. Preorder und Postorder sind nur Reihenfolgen wie man die einzelnen Knoten eines Graphen linear in ner Liste aufschreiben kann.

    Meines wissens benutzt man preorder und postorder auch nur im Zusammenhang mit einer Tiefensuche, was du implementiert hast ist allerdings eine Breitensuche.

    Ich glaube nicht, dass man bei einer postorder Sortierung immer direkt den nächsten Knoten bennenen kann. Man muss dazu vorher den Baum durchlaufen haben. Dabei ist auch zu beachten, dass Tiefensuche ein rekursiver Algorithmus ist. Man muss ihn zwar nicht durch explizite Rekursion in der jeweiligen Programmiersprache umsetzen, aber die Iterative implementierung ist letztendlich auch eine Rekursion mit explizitem Stack (statt dem Aufruf-Stack der Programmiersprache).