4 
    template<class T>
    void huffman(MinHeap<TreeNode<T>*> heap, int n)
    {
      for(int i=0;i<n-1;i++)
      {
        TreeNode<T> *first = heap.pop();
        TreeNode<T> *second = heap.pop();
        TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data, second.data);
        heap.push(bt);
      }
    }

私のC++ 教科書のデータ構造の基礎では、ハフマンコーディングの2ページの定義と、上記のコードが示されています。私にとって、この本は十分に詳細ではなかったので、グーグルを行い、ハフマン符号化のプロセスがどのように機能するかを学びました。教科書は、上記のコードの最後にハフマンツリーが作成されると主張しています。しかし、ハフマンツリーは完全なツリーである必要はないので、私には間違っているように見えますが、上記のコードは、のために常に完全なツリーを提供するようですheap.push()。では、誰かがこのコードが間違っていないことを私に説明できますか？

4

2 に答える 2

5

ヒープのツリー構造は、結果のハフマンツリーと必ずしも一致しません。ヒープには、部分的なハフマンツリーのフォレストが含まれ、最初はそれぞれが単一のシンボルノードで構成されます。次に、ループは、重みが最小の2つのノードを繰り返し取得し、それらを1つのノードに結合して、結果の結合されたノードを元に戻します。プロセスの最後に、ヒープには1つの完成したツリーが含まれます。

于 2010-07-16T23:47:37.670 に答える
0

ハフマン符号化は、各ステップで最も価値の低い2つの項目を取得することによって機能します。最初に関数を呼び出すと（MinHeapは値でソートされるため）、値が最も低い2つの項目がポップオフされ、決定ノードに「結合」されて、ヒープに戻されます。そのノードは、その子スコアの合計によってスコアリングされ、ヒープに戻されます。ヒープに戻すと、スコアに基づいて適切な場所に配置されます。それでも他のどのアイテムよりも低い場合は最初になり、そうでない場合は別の場所になります。

したがって、このアルゴリズムはツリーを下から上に構築し、ヒープを空にするまでに完全なツリーが作成されます。ただし、「n」の意味はわかりません。ループはである必要がありますwhile (heap.size() > 1)。とにかく、ツリーは「満杯」ではなく、最初のヒープ内のアイテムの頻度がどのようにスコアリングされるかに応じて、異なるブランチは異なる長さになります。

于 2010-07-16T23:49:02.057 に答える