-1

我有一个霍夫曼树和一个字符，我想返回该字符在霍夫曼树中的编码应该是什么。

我已经使用广度优先遍历方法实现了它，每次检查左右树时，我都会检查树的数据是否等于我正在寻找的字符。不过，每次我向右或向左走时，我都会在编码中添加 0 或 1。最终，当我找到等于树数据的字符时，我返回该树的编码值。

代码：

    public static String findCharEncoding(BinaryTree<CharProfile> bTree, char character) {
        Queue<BinaryTree<CharProfile>> treeQueue = new LinkedList<BinaryTree<CharProfile>>();

        // Create a TreeWithEncoding object from the given arguments and add it to the queue
        treeQueue.add(bTree);

        while (!treeQueue.isEmpty()) {
            BinaryTree<CharProfile> t = treeQueue.remove();

->          if (t.getLeft().getData().getCharacter() == character) {
                return t.getLeft().getData().getEncoding();
            }
            if (t.getLeft() != null) {
                t.getLeft().getData().setEncoding(t.getLeft().getData().getEncoding() + "0");
                treeQueue.add(t.getLeft());
            }

            if (t.getRight().getData().getCharacter() == character) {
                return t.getRight().getData().getEncoding();
            }
            if (t.getRight() != null) {
                t.getRight().getData().setEncoding(t.getRight().getData().getEncoding() + "1");
                treeQueue.add(t.getRight());
            }
        }

        // If it gets to here, the while loop was unsuccessful in finding the encoding
        System.out.println("Unable to find.");
        return "-1";
    }

我已经实现如下：

        for (int i = 0; i < charOccurrences.size(); i++) {
            char character = charOccurrences.get(i).getCharacter();

            charOccurrences.get(i).setEncoding(findCharEncoding(huffmanTree, character));
            System.out.println(charOccurrences.get(i).getEncoding());
        }

CharProfile 是一个自定义类，包含字符值、字符概率和编码。

它不断在行返回 NullPointerExceptionError if (t.getLeft().getData().getCharacter() == character) {，我用箭头表示了这一点。我已经尝试过，但我似乎无法弄清楚为什么。

4

2 回答 2

1

要么t是null，要么t.getLeft()返回null，要么t.getLeft().getData()返回null。正如我们只看到您展示的代码一样，调试它是您的工作。

您可以在错误上方插入一行：

if (t == null) {
    System.out.println("t = null");
} else if (t.getLeft() == null) {
    System.out.println("t.getLeft() returns null");
} else if (t.getLeft().getData() == null) {
    System.out.println("t.getLeft().getData() returns null");
}
于 2012-11-05T15:44:21.493 回答
0

正如评论中指出的那样，您正在检查是否在某个时间t.getLeft()返回null而不在其他时间返回。另外，就我个人而言，我只是讨厌一遍又一遍地调用相同的 get 方法的代码。我可能会选择这一部分：

        if (t.getLeft().getData().getCharacter() == character) {
            return t.getLeft().getData().getEncoding();
        }
        if (t.getLeft() != null) {
            t.getLeft().getData().setEncoding(t.getLeft().getData().getEncoding() + "0");
            treeQueue.add(t.getLeft());
        }

并将其重写为：

left = t.getLeft();
if ( left != null ) {
  data = t.getData();
  encoding = data.getEncoding();
  if ( data.getCharacter() == character ) {
    return encoding;
  else {
    data.setEncoding( encoding + "0" );
    treeQueue.add( left )
  }
}

（我已经为我添加的变量省略了类型声明，因为我不确定正确的类型名称。）

这应该避免NullPointerExceptionif t.getLeft()is what's return null; 否则，您至少应该更清楚地看到null发生异常时哪个引用是因为您不会在一行中有多个取消引用。右侧的部分可以以相同的方式重写（实际上，您可以创建一种方法，只需将左右值传递给，因为您对两者执行相同的操作）。

于 2012-11-05T15:54:04.780 回答