霍夫曼得到树高

Question

我是新来的Java。我试图获得我树的高度以及霍夫曼树中每个节点的深度。 我一直在尝试不同的方法来获得高度，但它仍然无法正常工作。 我无法弄清楚什么是问题。 现在，我得到一个错误：

Exception in thread "main" java.lang.ClassCastException: HuffmanLeaf cannot be cast to HuffmanNode 
    at HuffmanCode.findHeight(HuffmanCode.java:95) 
    at HuffmanCode.printResults(HuffmanCode.java:71) 
    at Main.main(Main.java:31) 

请，我坚持这一点。

import java.util.*; 

public class HuffmanCode { 
    int numberOfNode = 1; 
    int height; 
    String fullcode = ""; 
    String realcode = ""; 

    // input is an array of frequencies, indexed by character code 
    public HuffmanTree createTree(int[] charFreqs) { 
     PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>(); 
     // initially, we have a forest of leaves 
     // one for each non-empty character 
     for (int x = 0; x < charFreqs.length; x++) { 
      if (charFreqs[x] > 0) 
       /* 
       * My first step of Huffman coding Create a leaf node for each 
       * character and add it to the priority queue with the offer 
       * method 
       */ 
       trees.offer(new HuffmanLeaf(charFreqs[x], (char) x)); 
     } 

     while (trees.size() > 1) { 
      // Poll the two nodes with least frequency 
      HuffmanTree a = trees.poll(); 
      HuffmanTree b = trees.poll(); 

      // put into new node and re-insert into queue 
      trees.offer(new HuffmanNode(a, b)); 
      numberOfNode++; 
     } 
     return trees.poll(); 
    } 

    public void printResults(HuffmanTree tree, StringBuffer prefix) { 
     // assert tree != null; 
     if (tree instanceof HuffmanLeaf) { 
      HuffmanLeaf leaf = (HuffmanLeaf) tree; 

      System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix); 
      encodedInput(prefix); 
      for (int x = 0; x < leaf.frequency; x++) { 
       realcode = realcode + prefix; 
      } 

     } else if (tree instanceof HuffmanNode) { 
      HuffmanNode node = (HuffmanNode) tree; 
      numberOfNode++; 

      // move left 
      prefix.append('0'); 
      printResults(node.left, prefix); 
      prefix.deleteCharAt(prefix.length() - 1); 
      findHeight(node); 

      // move right 
      prefix.append('1'); 
      printResults(node.right, prefix); 
      prefix.deleteCharAt(prefix.length() - 1); 
      height = findHeight(node);  
     } 
    } 

    public void encodedInput(StringBuffer prefix) { 
     fullcode = fullcode + " , " + prefix; 

    } 

//Method to get height  
public int findHeight(HuffmanNode node) { 
     if (node == null) { 
      return -1; 
     } 

     int lefth = findHeight((HuffmanNode) node.left); 
     int righth = findHeight((HuffmanNode) node.right); 

     if (lefth > righth) { 
      return lefth + 1; 
     } else { 
      return righth + 1; 
     } 
    } 
} 

其他I类有：

class HuffmanNode extends HuffmanTree { 
    public HuffmanTree left; 
    public HuffmanTree right; 

    public HuffmanNode(HuffmanTree left, HuffmanTree right) { 
     super(left.frequency + right.frequency); 
     this.left = left; 
     this.right = right; 
    } 
} 

class HuffmanLeaf extends HuffmanTree { 
    public char value; // the character this leaf represents 
    public HuffmanLeaf(int frequency, char value) { 
     super(frequency); 
     this.value = value; 
    } 
} 

public class HuffmanTree implements Comparable<HuffmanTree> { 
    public int frequency; // the frequency of this tree 

    public HuffmanTree(int frequency) { 
     this.frequency = frequency; 
    } 
    public int compareTo(HuffmanTree tree) { 
     return frequency - tree.frequency; 
    } 
} 

Answer 1

你正在做

trees.offer(new HuffmanLeaf(charFreqs[x], (char) x)); 

事后，你这样做：

HuffmanTree a = trees.poll(); 
HuffmanTree b = trees.poll(); 

// put into new node and re-insert into queue 
trees.offer(new HuffmanNode(a, b)); 

所以实际上a或b威力是HuffmanLeaf

在这种情况下，例如，

(HuffmanNode) node.left 

导致错误，因为node.left实际上是HuffmanLeaf

实例所以这里的，工程的代码。

// Method to get height 
    public int findHeight(HuffmanTree tree) { 
    if (tree == null) { 
     return -1; 
    } 

    if (tree instanceof HuffmanLeaf) { 
     return 1; 
    } else if (tree instanceof HuffmanNode) { 
     int lefth = findHeight(((HuffmanNode) tree).left); 
     int righth = findHeight(((HuffmanNode) tree).right); 

     if (lefth > righth) { 
     return lefth + 1; 
     } else { 
     return righth + 1; 
     } 
    } else { 
     return -1; // does not happen, you might want to raise exception. 
    } 
    } 

你必须要考虑两个情况下的HuffmanTree实际情况是要么HuffmanNode或HuffmanLeaf。