java - 堆栈溢出错误/无休止的递归

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用， visit the help center 。

已关闭 10 年前。

我正在编码霍夫曼编码树，但收到此错误。

5:1
5:4
5:2
5:1
5:4
5:2
5:1
5:4
5:2
5:1
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByteEncoder.java:130)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:544)
at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:252)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:190)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111)
at java.io.PrintStream.write(PrintStream.java:476)
at java.io.PrintStream.print(PrintStream.java:619)
at java.io.PrintStream.println(PrintStream.java:756)
at HuffmanNode.buildTree(hw4.java:65)
at HuffmanNode.buildTree(hw4.java:66)
at HuffmanNode.buildTree(hw4.java:66)
at HuffmanNode.buildTree(hw4.java:66)
at HuffmanNode.buildTree(hw4.java:66)

显然我在 buildTree() 有一个无限递归方法，但是我不明白它在做什么。

public void buildTree(HuffmanNode node) {
    if (node.compareTo(this) <= 0 && left != null) {
        System.out.println(node.getCount() + ":" + this.count);
        left.buildTree(node);
    }
    else if (node.compareTo(this) <= 0 && left == null) {
        this.left = node;
        node.parent = this;
    }
    else if (node.compareTo(this) > 0 && right != null) {
        System.out.println(node.getCount() + ":" + this.count);
        right.buildTree(node);
    }
    else if (node.compareTo(this) > 0 && right == null) {
        this.right = node;
        node.parent = this;
    }
}

我的完整代码和输入文件可以看到 here .

Answer 1

第一步之后，你的树看起来像这样:

root
/  \
    -
   / \
  M   Z

当您执行第二步时，您将新的结果节点附加到Z，这是错误的。第二步之后，你的树就被破坏了，第三步进入无限递归。

编辑:好的，我刚刚再次阅读了算法，我认为您需要做的就是创建结果节点。只需删除这些行:

        if (root == null) {
            root = result;
        } else {
            root.buildTree(result);
        }

然后，当循环结束时，huffmanList 中将只有一个节点，即root:

    while (huffmanList.size() > 1) {
        HuffmanNode x = huffmanList.poll();
        HuffmanNode y = huffmanList.poll();
        HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
        huffmanList.add(result);
    }
    huffmanList.poll().genCode(" ");