C++实现哈夫曼树编码解码

本文实例为大家分享了C++实现哈夫曼树的编码解码，供大家参考，具体内容如下

代码：

				?

									#pragma once

									#include<iostream>

									#include<stack>

									using namespace std;

									#define m 20

									stack<int> s;

									/*哈夫曼树结点类HuffmanNode声明*/

									template<class T>

									class HuffmanNode {

									private:

									 HuffmanNode<T> * left;

									 HuffmanNode<T> * right;

									 T data;

									 int weight;

									public:

									 HuffmanNode(){}

									 HuffmanNode(const T& item, HuffmanNode<T> * l, HuffmanNode<T> * r):data(item),left(l),right(r){}

									 HuffmanNode<T> * getLeft() { return left; }

									 void setLeft(HuffmanNode<T> * left) { this->left = left; }

									 HuffmanNode<T> * getRight() { return right; }

									 void setRight(HuffmanNode<T> * right) { this->right=right; }

									 T& getData() { return data; }

									 void setData(const T& item) { data = item; }

									 int getWeight() { return weight; }

									 void setWeight(int weight) { this->weight = weight; }

									};

									/*哈夫曼树类HuffmanTree声明*/

									template<class T>

									class HuffmanTree {

									private:

									 HuffmanNode<T> * root;

									 T data[m];

									 int weight[m];

									 int count;

									public:

									 HuffmanTree(HuffmanNode<T> * t=NULL):root(t){}

									 void CreateHuffmanTree();//创建哈夫曼树

									 HuffmanNode<T> * getRoot() { return root; }

									 void setRoot(HuffmanNode<T> * t) { root = t; }

									 void inputNodes();//输入各个结点的data和weight值

									 HuffmanNode<T> * deCode(HuffmanNode<T>*t,T item);

									 void showCode();

									};

									template<class T>

									inline void HuffmanTree<T>::CreateHuffmanTree()

									{

									 inputNodes();

									 HuffmanNode<T> ** H = new HuffmanNode<T>*[count];

									 HuffmanNode<T> * p1 = NULL, *p2 = NULL, * p,* t;

									 for (int i = 0; i < count; i++) {

									 H[i] = new HuffmanNode<T>();

									 H[i]->setData(data[i]);

									 H[i]->setWeight(weight[i]);

									 H[i]->setLeft(NULL);

									 H[i]->setRight(NULL);

									 }

									 for (int i = 0; i < count - 1; i++) {

									 p = new HuffmanNode<T>();

									 p1 = H[i];

									 p2 = H[i + 1];

									 p->setLeft(p1);

									 p->setRight(p2);

									 p->setWeight(p1->getWeight() + p2->getWeight());

									 //将新的结点插入结点数组中的合适位置,并将被合并的两个结点删除

									 t = p;

									 int j = i + 2;

									 while ( j < count &&H[j]->getWeight() < t->getWeight()) {

									  H[j - 1] = H[j];

									  j++;

									 }

									 H[j - 1] = t;

									 }

									 root = H[count - 1];

									}

									template<class T>

									inline void HuffmanTree<T>::inputNodes()

									{

									 int i = 0;

									 for (int j = 0; j < m; j++) {

									 data[j] = NULL;

									 weight[j] = 0;

									 }

									 while (cin >> data[i] >> weight[i]) {

									 i++;

									 }

									 count = i;

									}

									template<class T>

									inline HuffmanNode<T>* HuffmanTree<T>::deCode( HuffmanNode<T> * t,T item)

									{

									 HuffmanNode<T> * p, * q;

									 if(t==NULL)

									 return NULL;

									 if (t->getData() == item)

									 return t;

									 if ((p = deCode(t->getLeft(), item))!=NULL) {

									 s.push(0);

									 return p;

									 }

									 else if((q = deCode(t->getRight(), item))!=NULL){

									 s.push(1);

									 return q ;

									 }

									}

									template<class T>

									inline void HuffmanTree<T>::showCode()

									{

									 cout << root->getWeight() << endl;

									 cout << (root->getLeft())->getRight()->getData() << endl;

									 for (int i = 0; i < count; i++) {

									 cout << data[i] << "——";

									 deCode(root, data[i]);

									 while (!s.empty()) {

									  cout << s.top();

									  s.pop();

									 }

									 cout << endl;

									 }

									}

测试程序：

				?

									#include<iostream>

									#include"HuffmanTree.h"

									using namespace std;

									int main() {

									 HuffmanTree<char> * tree = new HuffmanTree<char>();

									 tree->CreateHuffmanTree();

									 tree->showCode();

									 system("pause");

									 return 0;

									}