Как преобразовать это двоичное дерево с помощью рекурсии?

Question

Я очень застрял. Я понимаю рекурсию, но этот проект потерял меня.

В основном, это дерево берет что-то вроде

(a(b()())(c(d()())())) 

и выходов

a b 
a c d 

Это, как говорится, каждый узел может иметь 0, 1 или 2-х детей. Поэтому, если узел содержит 0 дочерних элементов, я знаю, что это означает, что пришло время для рекурсии предпринять действие & вернуться к корню дерева и перейти в правую часть дерева (потому что он сначала читает левую сторону). В целом, я просто очень смущен.

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Scanner; 


public class BinaryTreeFinal { 
    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)); 
     //System.out.println(tree2("a", "(a(b()())(c(d()())()))")); 
    } 

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

Это когда код становится грязным:

public static char tree2(String root, String path) 
{ 

    int counter = 0; 
    String[] trees = splitTree(path); 

    if(trees[1].charAt(counter) == '(' && trees[1].charAt(counter++) == ')') 
    { 
     counter++; 
     //return trees[1].charAt(counter); 
     return tree2(String, String); 
     //System.out.println(trees[1].charAt(counter)); 


    } 
    else 
     //System.out.println(trees[1].charAt(counter)); 
     return trees[1].charAt(counter); 
    //counter++; 


} 

Большое спасибо, и мне очень жаль, что это сбивает с толку. Я не знаю, как это сказать.

Answer 1

Немного что я написал, используя Stack s.

Input: `(a(b()())(c(d()())()))` 

Output: a b 
     a c d 

Input: `(a(b()())(c(d()())(e)))` 

Output: a b 
     a c d 
     a c e 

Как вы понимаете, я не проверил это полностью. Пройдите еще несколько тестов и посмотрите, работает ли он по мере необходимости.

Позвольте мне выразить свой мыслительный процесс в нескольких словах. Я видел, что character предшествовал (. a или родительская часть печаталась только в том случае, если было больше детей. Итак, я думал, всякий раз, когда был найден , я бы проверил свой стек, чтобы увидеть, был ли элемент на вершине (. Если да, отлично. Если нет, я буду продолжать выскакивать, пока не найду соответствующие круглые скобки. Как только это было сделано, я понял, что мне нужно перейти к следующей строке консоли. Затем мне нужно будет отслеживать, какие алфавиты я уже имел в своем стеке, в том случае, если они будут переизданы как родители нового ребенка. Итак, я сделал это. Когда встречается новый ребенок, родители печатаются, и все кажется золотым. Дайте мне знать, если это не так (с тестами он не работает).

Stack<Character> stack = new Stack<Character>(); 
String st = "(a(b()())(c(d()())(e)))"; 
String parent = null; 
for (int i = 0; i < st.length(); i++) { 
    char c = st.charAt(i); 

    if (c != ')') { 

     // if it is an alphabet 
     if (c != '(') { 
      // will require printing of parents 
      // iff there are more characters to print 
      if (parent != null) { 
       System.out.print(parent); 
       parent = null; 
      } 
      System.out.print(c + " "); 
     } 
     stack.push(c); 
    } else { 
     // is the character on top a matching opening bracket? 
     // if it is, then nothing to do, if not 
     char curTop = stack.pop(); 
     if (curTop != '(') 
      while (curTop != '(') 
       curTop = stack.pop(); 
     else 
      continue; 

     // done working with a character; move to next line 
     System.out.println(); 

     // now, need to reprint the `a` portion 
     // iff more children are present 
     Stack<Character> temp = new Stack<Character>(); 
     while (!stack.isEmpty()) 
      temp.push(stack.pop()); 

     while (!temp.isEmpty()) { 
      Character ch = temp.pop(); 
      if (!(ch == '(' || ch == ')')) { 
       // store content 
       if (parent == null) 
        parent = ""; 
       parent += ch + " "; 
      } 

      stack.push(ch); 
     } 

    } 
}