Java-Rekursion und binärer Baum

Question

Meine Klasse hat daran gearbeitet, Rekursionen zu benutzen, um Dinge wie die Türme von Hanoi, Fibonacci und all die anderen spaßigen Dinge zu erschaffen. Das Problem ist, ich verstehe nicht wirklich alles sehr gut. Ich verstehe das allgemeine Konzept der Rekursion, aber es ist für mich so kompliziert, es in die Praxis umzusetzen, wenn ich ein Programm mache. Ich bekomme, dass es die Methode immer und immer wieder aufruft, unter der es einen Basisfall erreicht, wo es endet, aber es ist schwer für mich, Code zu schreiben, der tut, was ich tun soll.

Wir arbeiten gerade an binären Bäumen. Wir sollen einen von meinem Professor bereitgestellten Code verwenden, um einen Baum aufzuteilen, und dann eine rekursive Methode schreiben, um alle Pfade auszudrucken, die der Baum enthält. Unser Eingang wird so etwas wie (a(b()())(c()())) sein, die ein Baum wäre:

a 
b c 

b und c unter ihnen würde haben 0 Kinder. (a) ist ein möglicher Knoten und () wäre ein leerer Knoten, der das Ende dieses Pfades wäre. Unser Ziel ist es, alle Wege zu drucken, so dass für mein Beispiel würde der Ausgang sein:

a b 

a c 

Der Code, den wir gegeben werden, beinhaltet eine Hilfsmethode, die wir unsere rekursive Methode können Sie schreiben:

public class BinaryTree { 


public static void main(String[] args) { 
    Scanner scan = new Scanner(System.in); 
    String tree = scan.nextLine();//correct format : (a()()) 
    String[] t = splitTree(tree); 
    System.out.println(Arrays.toString(t)); 

} 
public static String[] splitTree(String tree) 
{ 
    //expected format 
    //(node tree tree) 
    //0 1 2-x x-(length-2) length-1 
    if(tree.length() <= 2)//tree not long enough to process 
     return new String[]{tree}; 

    String[] temp = new String[3]; 
    temp[0] = "" + tree.charAt(1);//grab tree node 
    tree = tree.substring(2, tree.length()-1);//remove node and outer paren 
    int parenCount = 0;//count of open paren 
    int endTreeOne = 0;//end of first tree 
    for(int i = 0; i < tree.length(); i++) 
    { 
     if(tree.charAt(i) == '(') 
      parenCount++; 
     if(tree.charAt(i) == ')') 
      parenCount--; 
     if(parenCount == 0) 
     { 
      endTreeOne = i; 
      break;//ends for loop early 
     } 
    } 
    temp[1] = tree.substring(0, endTreeOne+1);//left tree 
    temp[2] = tree.substring(endTreeOne+1);//right tree 
    return temp; 
} 

Diese Methode konvertiert im Grunde eine Zeichenkette wie (a(b()())(c()())) und macht sie [a, (b()()), (c()())]. Den Baum im Grunde aufteilen.

Ich bin nur wirklich nicht sicher, wie ich von hier fortfahren soll, um meine rekursive Methode zu schreiben. Ich fühle mich ziemlich verloren ehrlich (und frustriert als Ergebnis). Ich denke, ich muss meine Methode überprüfen lassen, ob "()" existiert, dann ist das das Ende eines Pfades. Wäre das mein Basisszenario, um aus der Schleife zu kommen, die ich brauchen würde? Ich bin mir nicht sicher, wie ich angeben soll, welche Seite des Baumes ich auch nehmen soll. Wenn mir jemand helfen oder Tipps geben kann, oder mich auf den richtigen Gedankengang bringe, um das anzugehen, würde ich es sehr zu schätzen wissen.

Answer 1

Ich habe das Gefühl, dass der Schritt "Druckpfade" mit einem Objekt eines Baumes einfacher ist, also lassen Sie uns das definieren.

Die Methode wird rekursiv implementiert, um den Inhalt dieses Objekts erneut zu drucken.

Ich habe auch eine Hilfsmethode, um die Klammer zu zählen, und einen Fehler zu werfen, wenn eine Nichtübereinstimmung vorliegt.

private static int getParenCount(String s) { 
    int parenCount = 0; 
    int opened = 0; 

    for (int i = 0; i < s.length(); i++) { 
     char c = s.charAt(i); 
     if (c == '(') { 
      parenCount++; 
      opened++; 
     } else if (c == ')') { 
      parenCount++; 
      opened--; 
     } 
    } 
    if (opened != 0) { 
     throw new IllegalArgumentException("Paren mismatch." + s + " is not a valid tree."); 
    } 
    return parenCount; 
} 

Dann, in Bezug auf das Parsen der Zeichenfolge, habe ich einige hilfreiche Code-Kommentare hinterlassen.

public static BinaryTreeNode getTree(String treeString) { 
    // Initialize variables 
    String root; 
    String leftTree; 
    String rightTree; 
    BinaryTreeNode tree = new BinaryTreeNode(""); 

    System.out.println("Input: " + treeString); 

    if (treeString.equals("()")) { 
     System.out.println("Empty tree. Returning!"); 
     return null; 
    } 

    // Check for even parenthesis 
    int parenCount = getParenCount(treeString); 
    if (parenCount % 2 == 0) { 

     // Strip the outside parenthesis 
     treeString = treeString.substring(1, treeString.length()-1); 
     System.out.println("tree: " + treeString); 

     // Find the first '(' because the root is everything before it 
     int leftTreeStart = treeString.indexOf('('); 
     root = treeString.substring(0, leftTreeStart); 

     // Find the complete left-tree 
     int leftTreeEnd = leftTreeStart + 1; 
     int leftTreeParenCount = 0; 
     for (int i = leftTreeStart-1; i < treeString.length(); i++) { 
      char c = treeString.charAt(i); 
      if (c == '(') { 
       leftTreeParenCount++; 
      } else if (c == ')') { 
       leftTreeParenCount--; 
       if (leftTreeParenCount == 0) { 
        leftTreeEnd = i; 
        break; 
       } 
      } 
     } 

     System.out.println("root: " + root); 
     tree.root = root; 

     leftTree = treeString.substring(leftTreeStart, leftTreeEnd + 1); 
     System.out.println("\nleft: " + leftTree); 
     System.out.println("Recurse left..."); 
     tree.left = getTree(leftTree); // recurse here 

     // The right-tree is just the remainder of the string 
     rightTree = treeString.substring(leftTreeEnd + 1); 
     System.out.println("\nright:" + rightTree); 
     System.out.println("Recurse right..."); 
     tree.right = getTree(rightTree); // recurse here 

    } 

    return tree; 
}