Rekursive Baum-Traversal-Methode Mit Rückgabetyp Array

Gibt es eine Möglichkeit, rekursiv Durchlaufen einen Baum und gibt ein array zurück, das den Gültigkeitsbereich, die rekursive Methode?

Also ich habe letztens antwortete jemand auf die Frage in diesem Thema. Diese Frage kann hier gefunden werden: ALSO Frage. Meine Lösung verwendet ein array außerhalb des Bereichs der Rekursion, und daher die Methode nicht (oder zumindest sollte wohl nicht) return array. Jedoch ist es ein Weg, um schreiben Sie eine rekursive Methode für die Traversierung von Bäumen, so dass es ein array zurückgibt? Auch das schreiben einer ersten Methode, die Aufrufe der rekursiven wäre gut, aber ich kann nicht denken, ein guter Weg, dies zu tun.

Hier ist der code, den ich schlug vor:

private List nodeValues = new ArrayList();

public void traversePreRecursive(BinarySearchTreeNode node) 
{
    if (node != null)
    {
        nodeValues.add(node.getValue());
        traversePreRecursive(node.getLeft());
        traversePreRecursive(node.getRight());
    }
}

Wie Sie sehen können die ArrayList ist außerhalb des Bereichs der rekursions - Und daher wieder nicht sehr viel Sinn machen. Gibt es einen besseren Weg, dies zu tun?

Es wäre gut, wenn ein java-tag auf diese Frage
Hinzugefügt. War nicht sicher, ob es wäre eine Hilfe oder eine Behinderung, viele Sprachen konnte, haben ein ähnliches Problem.

InformationsquelleAutor sage88 | 2013-06-08

  1. 5
    public static List traversePreRecursive(Node node) {
    if (node == null) return new ArrayList();

    List nodeValues = new ArrayList();
    nodeValues.add(node.getValue());
    nodeValues.addAll(traversePreRecursive(node.getLeft()));
    nodeValues.addAll(traversePreRecursive(node.getRight()));

    return nodeValues;
}
    Hey sorry, ich glaube, ich war nicht vollkommen klar darüber. Ich Frage mich, ob es gibt einen Weg, es zu tun mit nur einem einfachen array statt einer ArrayList als gut.
    Auch während dieser Arbeit, ich bekomme das Gefühl, dass dies wird viel weniger effizient als die Verwendung eines Arrays außerhalb des Anwendungsbereichs der recurions...
    Ich bezweifle, es wäre wesentlich effizienter, um ein array zu verwenden. Das grundlegende problem ist, zu wissen, wie viele Elemente Sie hinzufügen, um das array. Wenn Sie wüßten, dann könnten Sie presize die array-Liste zu und erhalten die gleichen Leistungen. Die array-Liste ist eine eher einfache wrapper um ein array, das schafft der ausbau des array für Sie, so ohne wissen über die Größe des Arrays im erweiterten Sie würde am Ende schreiben den code selbst, und das wäre wahrscheinlich weniger effizient als die standard-array list-Implementierung.
    Richtig, ich weiß, wie ArrayList erstellt wird. Vielleicht bin ich auch nur naiv, aber wäre es nicht aufrufen addAll verursacht haben, neu zu schreiben, um die Liste jedes element in der Liste so weit nach jeder Rückkehr von traversePreRecursive? Anstatt also eine O(n) - operation, haben Sie jetzt eine O(n^2) - operation?
    Sie konnten verziehen werden für das denken so, aber java ist hoch optimiert für diese Art von operation. Unter der Decke der addAll() Methode verweist auf eine native Implementierung von arrayCopy() auf die System Objekt, das umgesetzt wird in die Schnellste Methode möglich (in Anbetracht der Einschränkungen der Plattform/jvm-Implementierung) -- in der Regel ist es mit blitters-und Speicher-mapping. Was bedeutet, dass der Betrieb umfasst die Zuweisung von Speicher-und block-kopieren von Daten aus einzelnen Listen zu einem einzigen block des Speichers in einem einzigen Vorgang pro Liste.

    InformationsquelleAutor Engineer Dollery

  2. 2

    Gibt es eine alternative, aber es beinhaltet zwei Pässe über den Baum. Sie würde nur beschäftigen diese alternative, wenn die array-Operationen in meiner ersten Antwort gab Sie Trauer. Dieser Ansatz beginnt, indem ein index für die einzelnen Knoten (die index() Methode) - im Grunde arbeiten Sie heraus, welches element des Arrays einen Knoten besetzen sollten, bevor wir tatsächlich das array erstellen. Dies gibt mir auch die eine Anzahl von Knoten (size). Ich habe dann alloziert ein array (list) groß genug, um alle Knoten und übergeben Sie es in eine Methode ( addToList ), die Kopien der Knoten-Referenzen in den zuvor identifizierten element in dem array. 

    public static List<Node> getNodes(Node a) {
    int size = index(a, 0);
    List<Node> list = new ArrayList<Node>(size);
    addToList(a, list);
    return list;
}

private static int index(Node node, int index) {
    if (node == null) return index;

    node.setIndex(index);
    int iLeft = index(node.getLeft(), index++);
    int iRight = index(node.getRight(), iLeft++);

    return iRight + 1;
}

private static void addToList(Node node, List<Node> list) {
    if(node == null) return;
    list.add(node.getIndex(), node);
    addToList(node.getLeft(), list);
    addToList(node.getRight(), list);
}

    InformationsquelleAutor Engineer Dollery

  3. 0

    In c können Sie die statische Funktion von Variablen(Dh, indem ein Wert in eine Liste in eine iteration einer Funktion bedeutet, dass dieser Wert wird in die Liste in der nächsten iteration--wenn die Liste statisch ist), aber mit Ihnen ist nicht die beste (optimale) Lösung für das problem, das Sie vorschlagen. So, ich denke, Sie sind auf der Suche für statische Variablen, aber dies nicht in einem entsprechenden Fall, Sie zu nutzen.

    InformationsquelleAutor jmpyle771

Schreibe einen Kommentar