Traversing eines binären Baumes rekursiv

Question

Ich bin hoffnungslos verloren, wenn es um rekursive Funktionen geht. Ich muss eine rekursive Funktion erstellen, um einen Binärbaum zu durchlaufen und einen neuen Knoten zwischen bestimmten Werten einzufügen. Müsste ich meine Traverse-Funktion erneut kopieren und in jeder anderen Funktion ändern, in der ich sie verwende? Würde jemand bitte die Traversierungsfunktion auswerten?

Ich denke, dass mein Verfahrcode in Ordnung ist.

Node traverse (Node currentNode){ 
    if (!currentNode.left.equals(null)){ 
     traverse (currentNode.left); 
     return currentNode.left; 
    } 
    if (!currentNode.right.equals(null)){ 
     traverse (currentNode.right); 
     return currentNode.right; 
    } 
    return currentNode; 
} 

Answer 1

Wenn es um binäre Bäume geht, gibt es mehrere verschiedene Arten von Durchläufen, die rekursiv durchgeführt werden können. Sie werden in der Reihenfolge geschrieben, in der sie referenziert und dann besucht wurden (L = linkes Kind, V = besuche diesen Knoten, R = rechtes Kind).

• In-Order Traversal (LVR)
• Reihenfolge umkehren Traversal (RVL)
• Vorordnungsdurchquerung (VLR)
• Nachordnungsdurchquerung (LRV)

Ihr Code leistungsfähiger zu sein scheint die Postorder Traversal Methode, aber Sie bekommen ein paar Dinge durcheinander. Zuerst ist der Knoten, was Sie durchlaufen möchten; Die Daten ist, was Sie besuchen möchten. Zweitens haben Sie keinen Grund, den Knoten selbst zurückzuliefern, so wie dies implementiert ist. Ihr Code erlaubt keine Bedingung zu sagen: "Ich bin auf der Suche nach dieser bestimmte Daten, haben Sie es Mr. Node @ 0xdeadbeef?", Die mit einer Art von zusätzlichen Suchparameter gefunden werden würde.

Ein akademischer BST-Traversal druckt nur die Knoten selbst. Wenn Sie eine Suchfunktionalität hinzufügen möchten, ist dies nur ein weiterer Parameter sowie eine zusätzliche Überprüfung für den richtigen Knoten.

Hier ist ein Ausschnitt:

// Academic 

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
} 

// Search with a valid node returned, assuming int 

public Node traverse (Node root, int data){ // What data are you looking for again? 
    if(root.data == data) { 
     return root; 
    } 
    if (root.left != null){ 
     return traverse (root.left, data); 
    } 
    if (root.right != null){ 
     return traverse (root.right, data); 
    } 
    return null; 
} 

Answer 2

Eine rekursive Funktion gibt den Wert von sich selbst mit einem modifizierten Parameter oder einer Beendigung (exit) Zustand. zB Factorial:

int factorial(int param) { 
    if (param > 1) { 
     return param * factorial(param -1); 
    } else { 
     return 1; 
    } 
} 

In Ihrem Code, rufen Sie eine ‚Traverse‘, aber dann nichts mit dem Ergebnis zu tun ... Wenn Ihre rekursive Funktion endet, Ihre endgültige Rückkehr wird zuerst linkes Kind sein, wenn es vorhanden ist, sonst das erste rechte Kind, wenn es existiert, sonst der Wurzelknoten.

Bitte geben Sie detaillierter an, warum Sie den Baum durchqueren müssen (auch nicht sicher, was Sie mit "Kopieren der Funktion und Ändern in jeder anderen Funktion" gemeint haben), die ganze Idee einer Funktion ist einmal zu codieren -all-viele)

Answer 3

Es scheint, als ob Sie in der Preorder-Methodik verfahren, aber ich bin ein wenig skeptisch, was genau Sie erreichen möchten, ohne Ihren aktuellen Knoten mit einem Basiswert zu vergleichen, der definiert, dass Sie ur erreicht haben Ziel. Ich würde vorschlagen, einen einfachen Baum zu zeichnen und die Schritte zu visualisieren. Dann versuche es in Code zu schreiben.