huffman.h

霍夫曼编码对于不同权值的字母进行编码,根据优先级输出.

#include <cstring>
#include <iostream>
#include "TreeNode.h"
#include "MinHeap.h"

using namespace::std;

class HuffmanTree{
public:
	 HuffmanTree():root(NULL) {}
	 HuffmanTree(int value[], int n);
	 ~HuffmanTree() {delete []nodes;}

public:
	void Encode(TreeNode *t);
	void HuffmanEncode();

public:
	TreeNode *JoinTree(TreeNode *node1, TreeNode *node2);
	TreeNode *root;
	TreeNode *nodes;
};

HuffmanTree::HuffmanTree(int value[],int n):root(NULL)
{
  nodes = new TreeNode[n*2];
  TreeNode leftNode,rightNode;

  int i, j = 0;

  TreeNode *l;
  MinHeap m_heap(value, n);
 
  if(1 > n) root = NULL;

  root = m_heap.RemoveMin();
  for(i = 0; i < n - 1; i++)
  {
	  /*nodes[j++] = m_heap.RemoveMin();
	  nodes[j++] = m_heap.RemoveMin();
	  */
	  l=m_heap.RemoveMin();
	  /*
	  r=m_heap.RemoveMin();*/
	  root = JoinTree(l,root);
      //m_heap.Insert(*root);
  }
}

TreeNode *HuffmanTree::JoinTree(TreeNode* node1, TreeNode* node2)
{
	TreeNode *r = new TreeNode;
	r->left = node1;
	r->right = node2;
	r->data = node1->data + node2->data;
	//strcpy(r->code,"");
	return r;
}


void HuffmanTree::Encode(TreeNode *t)
{
	if(t == NULL)
		return;

	if(t->left != NULL)
	{
		strcpy(t->left->code, t->code);
		strcat(t->left->code, "0");
		Encode(t->left);
	}

	if(t->right != NULL)
	{
		strcpy(t->right->code, t->code);
		strcat(t->right->code, "1");
		Encode(t->right);
	}

	if(NULL == t->right && NULL == t->left)	//是数据节点
		cout<<"value: "<<t->data<<'\t'<<"code: "<<t->code<<endl;
	
	
}

void HuffmanTree::HuffmanEncode()
{
  Encode(root);
}