java - 霍夫曼得到树高

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

我有其他班级：

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

最佳答案

你在做

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时，您必须同时考虑这两种情况。