StackOverFlow Ошибка/нерегулярная рекурсия

Question

Я кодирую дерево кодирования huffman, и я получаю сообщение об ошибке.

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) 

Очевидно, что у меня есть бесконечный метод recusive при 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

В setParent (HuffmanNode справа) вы делаете это.left = left, который абсолютно ничего не делает. Это должно быть ваша ошибка

Answer 2

После первого шага, ваше дерево выглядит следующим образом:

root 
/\ 
    - 
/\ 
    M Z 

Когда вы делаете второй шаг прикрепить новый result узел к Z, который является неправильным. После второго шага ваше дерево сломано, а третий шаг - к бесконечной рекурсии.

EDIT: хорошо, я просто прочитал алгоритм еще раз, и я думаю, что все, что вам нужно сделать, это создать узел результата. Просто удалите эти строки:

 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(" ");