2

这个网站上基本上有同样的问题，除了它说不要在问题中发布问题这里是一个链接。 二叉树递归函数

我需要打印出一个看起来像这样但任意大小的二叉树：

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

}

快乐编码：}

4

2 回答 2

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 次方和二进制的基本原理来计算需要做什么以及应该如何完成。如您所见，第一行将有0b1X，第二行将有0b10X，依此类推。从那里，您还可以看到 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 的幂（梅森素数）有关。

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

(1 << (rows - 1)) - 1)使用行数 (4) 将 的值0001移到1000，然后减去 1，0111剩下 7，即初始缓冲区。

(1 << i) - 1使用我们所在的当前行（范围 0-3）来产生重复的次数。将 0、1、2 和 3 插入到我们分别得到的公式中：0、1、3、7（次数中间部分每行重复）

2 * mod - 1用于计算上面公式中使用的“中间部分”中的破折号数量

mod >>= 1向右移动模组。这允许第一个公式从初始值 7 变为 3，变为 1，然后变为 0。

于 2013-03-16T01:04:00.220 回答
0

尝试直接显示输出会使您的递归变得繁琐。此外，您可能需要重新考虑您的参数。我相信叶子数应该足够了。

我会做不同的事情，通过为每个调用返回一个字符串列表，而不是立即打印输出。这样，您可以通过使用 {leaf count}/2 运行它，将列表与自身合并（通过连接同一索引中的行），然后为根添加一个新的标题行来实现您的 main 方法。

以下是我的解决方案。请注意，它只接受 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;
}
于 2013-03-15T23:56:59.337 回答