huffmantree.h

利用霍夫曼树进行文件压缩和解压

#pragma once

# include "minheap.h"
# include <iostream>
# include <string>

using namespace std;

const int DefaultSize = 256;

class Coding;
class Code;

template < class Type > class ExtBinTree;

//扩充二叉树节点
template < class Type > class ExtBinNode{
	friend class ExtBinTree<Type>;
    friend void HuffmanTree (Type* da , int *fr , int n, ExtBinTree < Type > &newtree )	;
public:
	ExtBinNode(){key = 0;  }
	ExtBinNode( ExtBinNode &a):data(a.data),key(a.key),num(a.num),
		                      leftChild(a.leftChild),rightChild(a.rightChild){ }

	Type GetData() const{ return data ;}              //返回数据值
	int GetKey () const{ return key; }                //返回权值
	string GetCode () const{ return code ; }          //返回编码
	ExtBinNode* GetLeft()const {return leftChild;}    //返回左子女指针
	ExtBinNode* GetRight()const {return rightChild;}  //返回右子女指针

public:
	Type data;                                       //存放数据
	int key;                                         //存放权值
	string code;                                     //存放编码
	ExtBinNode < Type > *leftChild, *rightChild;     //左子女，右子女
};


//扩充二叉树
template < class Type > class ExtBinTree {
	friend void HuffmanTree (Type* da , int *fr , int n, ExtBinTree < Type > &newtree )	;
public:
	ExtBinTree ( const ExtBinTree< Type > &b );       //拷贝构造函数

	ExtBinTree (){root = new ExtBinNode< Type >();	} //构造函数
	~ExtBinTree (){}
	void DelAll() { DelAll(root); }
	void DelAll( ExtBinNode < Type > * b );
	void operator = (const ExtBinTree< Type > *b) ;   //重载运算符＝
	void uniontree ( ExtBinTree< Type > &bt1, ExtBinTree< Type > &bt2 ){//合并扩充二叉树
		root->leftChild = bt2.root; root->rightChild = bt1.root;
		root->key = bt1.root->key +bt2.root->key;
	}
	int getkey () { return root->key; }
	ExtBinNode<Type> * GetRoot()const { return root ;}//返回根节点
	void setcode (){ setcode(root); root->code = "0";}//设置节点编码
	void setcode(ExtBinNode <Type> *&r);              //设置节点编码

public:
	ExtBinNode <Type> *root;                          //扩充二叉树的根

};

template < class Type >                               //拷贝构造函数
ExtBinTree<Type>::ExtBinTree ( const ExtBinTree< Type > &b ){
		root = new ExtBinNode< Type >();
		root->leftChild = b.root->leftChild;
		root->rightChild = b.root->rightChild;
		root->key = b.root->key;
		root->data = b.root->data;
		root->code = b.root->code;
}

template < class Type >                               //重载运算符＝
void ExtBinTree<Type>::operator = (const ExtBinTree< Type > *b) {
		if( root == NULL ) root = new ExtBinNode< Type >();
		root->leftChild = b->root->leftChild;
		root->rightChild = b->root->rightChild;
		root->key = b->root->key;
		root->data = b->root->data;
		root->code = b->root->code;
}

template < class Type >                               //删除以节点b为根节点的树，递归算法
void ExtBinTree< Type >::DelAll(ExtBinNode < Type > * b )
{
	if( b != NULL ){
	   if(b->leftChild)DelAll( b->leftChild );
	   if(b->rightChild)DelAll( b->rightChild );
       if(!b->leftChild && !b->rightChild)delete b; 
	   }
}

template < class Type >                               //设置节点编码，递归算法
void ExtBinTree< Type >::setcode(ExtBinNode <Type> *&r){
	string temp = r->code;
	if(r->leftChild != NULL ){
		string zero = "0";
		if(temp.length())r->leftChild->code =  temp + zero;
		else r->leftChild->code = "0";
		setcode(r->leftChild);
	}
	if(r->rightChild != NULL ){
		string one = "1";
		if(temp.length())r->rightChild->code =  temp + one;
		else r->rightChild->code = "1";
		setcode(r->rightChild);
	}
	if(!r->leftChild&&!r->rightChild)return;	
}


template <class Type>                               //建立huffman树
void HuffmanTree ( Type * da , int *fr , int n, ExtBinTree < Type > &newtree ) {
	//fr指向存放n个权值的数组，newtree返回Huffman树
	ExtBinTree < Type >  first,  second;
	ExtBinTree < Type > Node[DefaultSize];
	
	if ( n> DefaultSize ){
		cerr<<"Size n " << n <<" exceeds the boundary of Array" << endl; return;
	}
	int i,j=0;
	for ( i=0; i<n; i++ ){
		if(fr[i])
		{
	    Node[j].root->key = fr[i];
		Node[j].root->data = da[i];
		Node[j].root->leftChild = Node[j].root->rightChild = NULL;
		j++;
		}//传送初始权值
	}
	MinHeap <ExtBinTree< Type> > hp ( Node, j);

	//建立霍夫曼树的过程，做n-1趟
	for ( i=0; i<j-1; i++ ){
		hp.RemoveMin( first ); hp.RemoveMin( second );//选根权值最小和次小的树
		newtree.uniontree(first , second );           //建新的根结点
		hp.Insert ( newtree );                        //形成新树插入
	}
}