0

我正在编写一个霍夫曼编码树，我收到了这个错误。

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

我的完整代码和输入文件可以在这里看到。

4

2 回答 2

1

第一步后，您的树如下所示：

root
/  \
    -
   / \
  M   Z

当您执行第二步时，您将新result节点附加到 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(" ");
于 2012-12-07T20:23:54.127 回答
0

在 setParent(HuffmanNode right) 你做 this.left=left 什么都不做。这一定是你的错误

于 2012-12-07T20:07:31.790 回答