huffman.cpp

提供文本的无损压缩功能

#include"stdafx.h"
#include "huffman.h"
BinaryTree<int>Huffman :: HuffmanTree(/*int*/UINT a[], BYTE /*STR_*/ t[],int n)
{ 	
   Huffman  *w = new Huffman   [n+1];
   BinaryTree<int> z, zero;
   for (int i = 1; i <= n; i++)
   {
	   z.MakeTree(t [i-1], zero, zero);
	  w[i].weight = a[t [i-1]]/*t[i].frequency;*/;
      w[i].tree = z;

    }

   // make array into a min heap
   MinHeap<Huffman> H(1);
   H.Initialize(w,n,n);

   // repeatedly combine trees from heap
   Huffman  x, y;
   for (int i = 1; i < n; i++)
   {
      H.DeleteMin(x);
      H.DeleteMin(y);
      z.MakeTree(0, x.tree, y.tree);
      x.weight += y.weight; x.tree = z;
      H.Insert(x);
   }
   H.DeleteMin(x); // final tree
   H.Deactivate();
   delete [] w;
   return x.tree;
}