需要在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的

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

哇！

對不起，遲到的迴應，有點趕上了一些遊戲，但我終於明白了這一點。

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和2的冪的基本原理來計算需要完成的工作以及應該如何完成。正如你所看到的，第一行將有0b1 X，第二行將有0b10 X等等。從那裏，你還可以看到x之前所需的破折號數量。如果有4行，第一行需要0b111破折號，第二行需要0b11。從那裏，它只是重複做破折號相反的衰減。第一個需要0個重複，第二個需要1.

如果您需要更多的解釋，我會很樂意這樣做。

編輯1：更多解釋

對於下面的說明，我將使用rows = 4進行分析。因此，輸出應該類似於：

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

讓我們分解一行。使用第二個作爲一個例子，我們可以得出這樣的結論，該邏輯流程是：

1. 打印出緩衝器（在這種情況下3個破折號） - >---
2. 打印出孤X - >---x
3. 重複打印n次。 n = 1，（-------x） - >---x-------x
4. 打印出緩衝器（3再次破折號） - >---x-------x---

這可以被複製爲所有的情況下。

第一種情況：緩衝液= 7，n = 0時 - >由於n = 0
第二種情況不產生重複部分：在緩衝液中緩衝液= 3，n = 1時，短劃線= 7
第三種情況：緩衝液= 1中，n = 3，在緩衝液中破折號= 3
第四種情況：在緩衝器緩衝液= 0，N = 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（的次數的中間部分的每行重複的量）

用於計算公式中使用的上述模的右

mod >>= 1移「中間部分」破折號的量2 * mod - 1。這允許第一個公式從7的初始值變爲3，然後變爲0.