0

ハフマン ツリーと文字があり、ハフマン ツリー内でのその文字のエンコーディングを返す必要があります。

幅優先走査法を使用して実装しました。左右のツリーをチェックするたびに、ツリーのデータが探している文字と等しいかどうかをチェックしています。ただし、右または左に移動するたびに、これまでのエンコーディングに 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 は、文字値、文字の確率、およびエンコーディングを保持するカスタム クラスです。

if (t.getLeft().getData().getCharacter() == character) {矢印で示した行で NullPointerExceptionError を返し続けます。私は試してみましたがt.getLeft().getData()、全体ではなくエラーを返しているという事実を除いて、理由を理解できないようですがt.getLeft()、それでも理由がわかりません。

4

1 に答える 1

1

左または右のツリー ブランチが実際に発生する可能性があるnull場合 (これがハフマンの場合、おそらくリーフ ノードでのみ発生するはずです) 、チェックする前getDataにそれらを呼び出すのはなぜですか? それは間違いなく NullPointerExeption を引き起こします。

if (t.getLeft() != null) {
  // check nullity and THEN check match
  if (t.getLeft().getData().getCharacter() == character) {
    return t.getLeft().getData().getEncoding();
  }
  t.getLeft().getData().setEncoding(t.getLeft().getData().getEncoding() + "0");
  treeQueue.add(t.getLeft());
}

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

0ps また、そうでなければs と1s のビット文字列を返す場合は "-1" を返さないようにしたいかもしれませんfindCharEncoding。:)

于 2012-11-06T04:43:53.580 に答える