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

哇哦!

很抱歉回复晚了，有点玩游戏了，不过我终于弄明白了。

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 次。

如果您需要对此进行更多解释，我很乐意这样做。

编辑 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---

这可以复制到所有案例中。

第一种情况:buffer = 7, n = 0 -> 自 n=0 以来没有生成重复部分
第二种情况:缓冲区 = 3，n = 1，缓冲区中的破折号 = 7
第三种情况:缓冲区 = 1，n = 3，缓冲区中的破折号 = 3
第四种情况:buffer = 0, n = 7, buffer = 1 中的破折号

您可以看到在所有这些情况下，变量都与 2 减 1 的幂(梅森素数)相关。

使用该技术，我们得出一些基本公式的结论:

(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将 mod 右移。这允许第一个公式从初始值 7 变为 3，变为 1，然后变为 0。