необходимо отобразить поток полного двоичного дерева в java

Question

В этом вопросе есть практически такой же вопрос, за исключением того, что он говорит, что не задавайте вопросы на вопросы, вот ссылка. Binary Tree Recursive Function

мне нужно распечатать бинарное дерево, которое выглядит, как это, но для произвольного размера:

--------x------- 
----x-------x--- 
--x---x---x---x- 
-x-x-x-x-x-x-x-x 
xxxxxxxxxxxxxxxx 

однако, когда я исполняю ошибки кода выводит вместе с бесконечной печати

:::X:::::X::X:XXXXX 

и есть синяя линия под этим, на который я могу щелкнуть, и он вызывает окно с надписью «источник, не найденный для» с бесконечным X's

at sun.nio.cs.SingleByte.withResult(Unknown Source) 
at sun.nio.cs.SingleByte.access$000(Unknown Source) 
at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source) 
at sun.nio.cs.SingleByte$Encoder.encodeLoop(Unknown Source) 
at java.nio.charset.CharsetEncoder.encode(Unknown Source) 
at sun.nio.cs.StreamEncoder.implWrite(Unknown Source) 
at sun.nio.cs.StreamEncoder.write(Unknown Source) 
at java.io.OutputStreamWriter.write(Unknown Source) 
at java.io.BufferedWriter.flushBuffer(Unknown Source) 
at java.io.PrintStream.write(Unknown Source) 
at java.io.PrintStream.print(Unknown Source) 
at BinaryBuilder.display(BinaryBuilder.java:25) 
at BinaryBuilder.display(BinaryBuilder.java:31) 
at BinaryBuilder.display(BinaryBuilder.java:31) 

код, который я до сих пор не работает должным образом, и у меня были проблемы с рекурсией и понимание порядка выполнения стековых фреймов. Пожалуйста, помогите, я подумал, что я на правильном пути, используя строку, чтобы вернуться из рекурсии. Мне нужна некоторые рекомендации и толчок в правильном направлении :)

import java.util.Scanner; 
public class BinaryBuilder { 
    int levels = 0; 
    int width = 0; 
    int leaves = 0; 
    Scanner sn = new Scanner(System.in); 
    public BinaryBuilder() { 
     //prt("how many leaves?"); 
     //leaves = sn.nextInt(); 
     //levels = (int)Math.sqrt((double)leaves); 
    } 
    public void setLevelLeaves(int l,int le){ 
     levels = l; 
     leaves = le; 
    } 

    public void display(int left, int right, int row){ 
     int i =left; 
     int mid = (left+right)/2;   //maybe a +1 
     if(row>levels){ 
      return; 
     } 
     while(i <= right){ 
      if(i==mid){ 
       System.out.print("X"); 
      }else{ 
       System.out.print(":"); 
      } 
      i++; 
     } 
     display(left, mid, row++); 
     display(mid, right, row++); 
    } 

    public void prt(String n){ 
     System.out.println(n); 
    } 

} 

Главной

public class PartBTest { 

    public PartBTest() { 
    } 

    public static void main(String[] args) { 
     BinaryBuilder bb = new BinaryBuilder(); 
     //bb.prt("width will be reduced to a factor of 2"); 
     bb.setLevelLeaves(3, 8); 
     bb.display(0, bb.leaves-1, 0); 
    } 

} 

День кодирования:}

Answer 1

Попытку отобразить выходы непосредственно делает ваши рекурсии громоздкими. Кроме того, вы можете захотеть переосмыслить свои параметры. Я считаю, что количество листьев должно быть достаточно.

Я бы сделал это по-другому, возвратив список строк для каждого вызова, вместо того, чтобы сразу печатать выходные данные. Таким образом, вы можете реализовать свой основной метод, выполнив его с помощью {leaf count}/2, объединив список с собой (путем объединения строк в один индекс), а затем добавив новую строку заголовка для корня.

---

Ниже приводится мое решение. Обратите внимание, что он принимает только аргумент, который равен 2:

public static List<String> buildTree(int leafs) { 
    if (leafs == 1) 
     return Arrays.asList("x"); 

    // Recursive call 
    List<String> subTree = buildTree(leafs/2); 

    ArrayList<String> merged = new ArrayList<String>(); 
    // Add new header 
    String blanks = String.format("%-" + (leafs/2) + "s", "").replace(' ', '-'); 
    String header = blanks + "x" + blanks.substring(1); 
    merged.add(header); 

    // Duplicate subtree 
    for (String row : subTree) 
     merged.add(row + row); 

    return merged; 
} 

Answer 2

Woah!

Извините за поздний отклик, в некоторых играх добрался, но я, наконец, понял это.

import java.util.Scanner; 

public class Testing { 

    public static void main(final String[] args) { 

     final Scanner in = new Scanner(System.in); 

     System.out.print("How many rows would you like?"); 

     final int rows = in.nextInt(); 
     int mod = (1 << (rows - 1)) - 1; 

     for(int i = 0; i < rows; i++){ 
      for(int j = 0; j < mod; j++){ 
       System.out.print("-"); 
      } 
      System.out.print("X"); 
      for (int j = 0; j < (1 << i) - 1; j++){ 
       for(int k = 0; k < 2 * mod + 1; k++){ 
        System.out.print("-"); 
       } 
       System.out.print("X"); 
      } 
      for(int j = 0; j < mod; j++){ 
       System.out.print("-"); 
      } 
      mod >>= 1; 
      System.out.println(); 
     } 

     in.close(); 

    } 

} 

Это довольно простой логический подход. Он использует основы полномочий 2 и двоичные для расчета того, что необходимо сделать и как это сделать. Как вы можете видеть, первая строка будет иметь 0b1 X, вторая - 0b10 X и так далее. Оттуда вы также можете увидеть количество тире, необходимое до x. Если есть 4 строки, первая строка нуждается в пунктах 0b111, второй - 0b11. Оттуда он просто повторяет выполнение противоположного распада числа тире. Сначала нужно 0 повторений, второй потребности 1.

Если вам нужно больше объяснить это, я был бы счастлив сделать это.

Edit 1: Больше Объясняя

Для дальнейшего объяснения я буду использовать rows = 4 для анализа. Поэтому выход должен напоминать:

-------X------- 
---X-------X--- 
-X---X---X---X- 
X-X-X-X-X-X-X-X 

Давайте разложим одну строчку. Использование второй в качестве примера мы можем прийти к выводу, что логический поток является:

1. Распечатайте буфера (в данном случае 3 черточки) ->---
2. Распечатайте одинокого х ->---x
3. Распечатайте повторяющуюся секцию n раз. n = 1 (-------x) ->---x-------x
4. Распечатайте буфер (3 черточки снова) ->---x-------x---

Это может быть воспроизведен для всех случаев.

Первый случай: буфер = 7, п = 0 -> нет повторения раздела генерируется так как п = 0
Второй случай: буфер = 3, п = 1, черточек в буфере = 7
Третий случай: буфер = 1 , п = 3, тире в буфере = 3
Четвертый случай: буфер = 0, п = 7, черточки в буфере = 1

Вы можете увидеть во всех этих случаях переменные все связанные с мощностью 2 минус один (простые числа Мерсенна).

Используя эту технику, мы приходим к выводу некоторых основных формул:

(1 << (rows - 1)) - 1) использует количество строк (4) сдвинуть значение 0001 к 1000, затем вычитает один, 0111 оставив нас с 7, начальный буфер.

(1 << i) - 1 использует текущую строку, в которой мы находимся (начиная с 0-3), чтобы произвести повторяющееся количество раз. Используя 0, 1, 2 и 3 в эту формулу, получаем соответственно: 0, 1, 3, 7 (количество раз средняя секция повторяется для каждой строки)

2 * mod - 1 используется для расчета количества дефисов в средней секции «», используемой в приведенной выше формуле

mod >>= 1 сдвигает вправо моды. Это позволяет первой формуле перейти от начального значения от 7 до 3, к 1, а затем к 0.