Die Traversierung eines Baumes rekursiv in die Tiefe, erste Probleme

Ich versuche zu durchqueren, ein Baum mit ANTLR tree-Befehle und Rekursion. Der code, den ich derzeit habe ist:

public void traverseTree(Tree tree){
        int counter = 0;
        System.out.println(tree.toString());
        if (tree.getChildCount() > 0 && tree.getChild(0) != null){
            System.out.println(tree.toString() + counter++);
            tree = tree.getChild(0);
            traverseTree(tree);

        }
        while (tree.getParent().getChild(tree.getChildIndex() + 1) != null){
            System.out.println(tree.toString() + counter++);
            tree = tree.getParent().getChild(tree.getChildIndex() + 1);
            traverseTree(tree);

        }
    }

Aber gut, es funktioniert nicht. Ich bin immer in der Menge der Einträge in der Baumstruktur, aber keine offensichtliche Ordnung. Kann jemand sehen, wo ich bin mache ich falsch?

Dank.

EDIT:

Kommentar, den ich gemacht unten das sollte hier beginnen mit:

Sorry, sollte ich entfernte die print-Anweisungen, Sie waren nur da, um zu versuchen und zu Debuggen. Das problem ich bin der Begegnung ist, dass es nur die Suche der Knoten beginnt es und alle Geschwister des Knotens, sollte es nicht gehen eine Ebene nach oben, aber es funktioniert, druckt er alles. (Ich werde Bearbeiten Sie diese in der main, es sollte dort gewesen sein, um mit zu beginnen, sorry).

Ich es geschafft, der code funktioniert schließlich wie so:

public void traverseTree(Tree tree){
        System.out.println(tree);
        if (tree.getChild(0) != null){
            traverseTree(tree.getChild(0));
        }
        if(tree.getParent().getChildCount() > 1){
            if(tree.getParent().getChild(tree.getChildIndex() + 1) != null)
            traverseTree(tree.getParent().getChild(tree.getChildIndex() + 1));
        }
    }

"In der Tiefe zuerst"... meinst du level um? Reverse level order? Ich bin verwirrt.. Andere Möglichkeiten sind die preorder, inorder, postorder

InformationsquelleAutor djcmm476 | 2012-03-15

5

Der einfachste Weg, um sicherzustellen, es geht nie, bis Sie eine Ebene, um sicherzustellen, Sie nie rufen Sie getParent(). Wenn Sie keine Ahnung haben, es gibt eine Obere Ebene, können Sie nicht dorthin zu gehen.
```
public void traverseTree(Tree tree) {

    //print, increment counter, whatever
    System.out.println(tree.toString());

    //traverse children
    int childCount = tree.getChildCount();
    if (childCount == 0) {
        //leaf node, we're done
    } else {
        for (int i = 0; i < childCount; i++) {
            Tree child = tree.getChild(i);
            traverseTree(child);
        }
    }
}
```
Den ganzen Punkt der Rekursion ist, dass Sie nicht brauchen, um zurück zu gehen. Wenn traverseTree() auf dieser Ebene beendet ist, wird die Schleife in der vorherigen Ebene weiter zum nächsten Geschwister.

(Beachten Sie, dass die if ist nicht wirklich notwendig, es sei denn, Sie wollen etwas besonderes zu tun, wenn Sie erreichen, ein Blatt-Knoten. Ich legte es es so der Kommentar würde klar machen, was Los ist. Konzeptionell, es ist immer eine gute Idee, die Rekursion zu starten, indem Sie herausfinden, wie Sie wissen, Wann zu stoppen recursing.)

Aber das ist die Sache, die ich nie verwenden, getParent (), außer, wenn ich dabei bin getParent.getChild(getChildIndex() + 1), die nur zu verschieben es auf den nächsten Geschwisterknoten (es scheint nicht zu sein ein anderer Weg, dies zu tun).
Sie brauchen nicht zu bewegen, um den nächsten Geschwisterknoten. Die Schleife auf der übergeordneten Ebene übernimmt.
(Natürlich, Sie haben tatsächlich eine Schleife. Ich kann mir vorstellen es ist möglich, es zu tun, ohne eine Schleife, aber ich weiß nicht, warum Sie wollen würde.)
Okay, bei näherer Betrachtung sehe ich, was Los ist. Sie Durchlaufen Ihre Geschwister statt Schleifen über Ihre Kinder. Da haben Sie zu gehen bis zu den Eltern, um Ihre Geschwister, es gibt keine Möglichkeit (ohne zusätzliche Informationen) zu stoppen, das traversal von kriechen den ganzen Weg bis zu der Wurzel des Baumes.
Ich werde markieren Sie Ihre Antwort als richtig an, wie Sie mir geholfen mit ein paar bugs. Das Ding, was das wirkliche Problem war eigentlich ein bisschen früher in den code. Ich poste die Arbeiterklasse code in Fall, dass jemand läuft in ein ähnliches problem. Danke!

InformationsquelleAutor David Moles
2

Sieht es aus wie Sie drucken wollen, aus den gleichen Knoten mehrmals. Wenn Sie nur wollen, um print out der Knoten, als Sie nach unten gehen,
```
   1
 2   3
4 5   6

Depth first - 1 2 4 5 3 6
Breadth first - 1 2 3 4 5 6

//For depth first
public void traverseTree(Tree tree){        
    System.out.println(tree.toString());
    for (int x = 0; x < tree.getChildCount(); x++)
        traverseTree(tree.getChild(x));
}
```
Wechseln 4 5 6 2 3 1 bewegen Sie einfach die println, um nach der for-Schleife.

Sorry, sollte ich entfernte die print-Anweisungen, Sie waren nur da, um zu versuchen und zu Debuggen. Das problem ich bin der Begegnung ist, dass es nur die Suche der Knoten beginnt es und alle Geschwister des Knotens, sollte es nicht gehen eine Ebene nach oben, aber es funktioniert, druckt er alles. (Ich werde Bearbeiten Sie diese in der main, es sollte dort gewesen sein, um mit zu beginnen, sorry).
Thomas' Lösung ist (fast) funktioniert, an was Knoten, den Sie geben (es sollte null exit-Anweisungen). Wenn Sie anfangen wollen, an ein Kind, nur es passieren, dass statt der Wurzel. Sie wirklich brauchen, um genauer zu sein über, wie Sie versuchen, zu besuchen jeden Knoten, was Sie zu tun beabsichtigen, und in welcher Reihenfolge.
Ich war der Annahme, die Kinder waren nicht null, so würde es beenden, aufgrund getChildCount() 0. In jedem Fall, es beantwortet nicht die eigentliche Frage.

InformationsquelleAutor Thomas

Versuchen Sie dies:

int counter = 0;
public void traverseTree(Tree tree) {

    for (int i=0; i<tree.getChildCount(); i++) {
        Tree child = tree.getChild(i);
        System.out.println(tree.toString() + counter++);
        traverseTree(tree);
    }
}

InformationsquelleAutor darijan

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.