Java遞歸和二叉樹

Question

我的課一直在努力使用遞歸創建像河內塔，斐波納契和所有有趣的東西。問題是，我不是很瞭解所有事情。我理解遞歸的一般概念，但在編寫程序時將其付諸實踐對我來說感覺如此複雜。我知道它一直在調用一遍又一遍的方法，在它下面會出現一個基本情況，但是我很難編寫代碼來執行我想要的操作。

我們正在研究二叉樹。我們應該使用由我的教授提供的一些代碼來分割一棵樹，然後編寫一個遞歸方法來打印出樹所包含的所有路徑。我們的投入會像(a(b()())(c()()))這將是一個樹：

a 
b c 

B和C會低於他們0孩子。 (a)是一個可能的節點，()將是一個空的節點，這將是該路徑的結束。我們的目標是打印出所有的路徑，所以我的例子中，輸出將是：

a b 

a c 

我們給出的代碼包含，我們可以用它來寫我們的遞歸方法的helper方法：

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; 
} 

此方法基本上轉換一個字符串如(a(b()())(c()()))並使它們爲[a, (b()()), (c()())]。基本上把樹分開。

我真的不知道如何從這裏繼續寫我的遞歸方法。我真的很失落（並因此而感到沮喪）。我想我需要讓我的方法檢查是否存在「（）」，那麼這就是路徑的結束。那是否會成爲我退出循環所需的基礎案例？我不知道如何指定樹的哪一邊。如果有人可以提供任何幫助，提示，或讓我處理這個問題的正確思路，我將不勝感激。

Answer 1

我覺得像「打印路徑」這一步對於一棵樹的對象來說會更容易，所以我們來定義它。

toString方法遞歸實現以重新打印您將解析到此對象中的內容。

public class BinaryTreeNode { 
    public String root; 
    public BinaryTreeNode left; 
    public BinaryTreeNode right; 

    public BinaryTreeNode(String root) { 
     this.root = root; 
    } 

    @Override 
    public String toString() { 
     String s = root; 

     if (left != null) { 
      s += left.toString(); 
     } else { 
      s += "()"; 
     } 

     if (right != null) { 
      s += right.toString(); 
     } else { 
      s += "()"; 
     } 

     return "(" + s + ")"; 
    } 
} 

我也有一個輔助的方法來算括號，如果任何不匹配拋出一個錯誤。

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; 
} 

然後，關於解析字符串，我留下了一些有用的代碼註釋。

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; 
}