huffmantree.h

霍夫曼树的代码..实现了用霍夫曼编码的功能,经测试能成功输出

#include <iostream>
#include <cstring>
#include <string>

#include <MinHeap.h>

using namespace std;

class HuffmanTreeNode
{
	friend class HuffmanTree;
	public:
		char word[30];
		int info;
		int path[15];
		HuffmanTreeNode * left;
		HuffmanTreeNode * right;
		HuffmanTreeNode * parent;
//		HuffmanTreeNode();
//		HuffmanTreeNode(const char & ele);
//		HuffmanTreeNode(const char & ele,HuffmanTreeNode * l,HuffmanTreeNode * r,HuffmanTreeNode * p);
		HuffmanTreeNode * leftchild() const
		{
			return left;
		}
		HuffmanTreeNode * rightchild() const
		{
			return right;
		}
		HuffmanTreeNode * Parent() const
		{
			return parent;
		}
		bool isLeaf() const
		{
			if(left==NULL&&right&&NULL) return true;
			else return false;
		};
}

class HuffmanTree
{
	private:
		HuffmanTreeNode * root;
		void MergeTree(HuffmanTreeNode & ht1,HuffmanTreeNode & ht2,HuffmanTreeNode * parent);
		void DeleteTree(HuffmanTreeNode * root);
	public:
		HuffmanTree(int weight[],int n);
		void Travel(HuffmanTreeNode * head);
		void Reverse(HuffmanTreeNode * head,HuffmanTreeNode * current);
		bool RootPath(HuffmanTreeNode * head,HuffmanTreeNode * current);
}

HuffmanTree::HuffmanTree(int weight[],int n)
{
	MinHeap <HuffmanTreeNode> heap(n);
	HuffmanTreeNode *parent,firstchild,secondchild;
	HuffmanTreeNode *Nodelist = new HuffmanTreeNode [n];
	for(i=0;i<n;i++)
	{
		Nodelist[i].info=weight[i];
		Nodelist[i].parent=Nodelist[i].left=Nodelist[i].right=NULL;
		heap.insert(NodeList[i]);
	}
	for(i=0;i<n-1;i++)
	{
		parent=new HuffmanTreeNode;
		firstchild=heap.RemoveMin();
		secondchild=heap.RemoveMin();
		MergeTree(firstchild,secondchild,parent);
		root=parent; 
	}
	delete []Nodelist;
}

void HuffmanTree::MergeTree(HuffmanTreeNode &ht1, HuffmanTreeNode &ht2, HuffmanTreeNode *par)
{
	if(ht1.info<ht2.info)
	{
		par->left=ht1;
		ht1->parent=par;
		par->right=ht2;
		ht2->parent=par;
	}
	else
	{
		parent->left=ht2;
		parent->left=ht1;
		ht1->parent=par;
		ht2->parent=par;
	}
	parent->info=ht1.info+ht2.info;
	return;
}

void HuffmanTree::Travel(HuffmanTreeNode *head)
{
	if(head==!NULL)
	{
		Travel(head->leftchild());
		if(head->isLeaf())
		{
			Reverse(head);
		}
		Travel(head->rightchild());
	}
}

void HuffmanTree::Reverse(HuffmanTreeNode * current)
{
	int revPath[15];
	int i=0;
	HuffmanTreeNode *temppar=current->parent(),*temp=current;
	while(temppar!=NULL)
	{
		if(temppar->leftchild()==temp) revPath[i++]=0;
		else revPath[i++]=1;
		temp=temppar;
		temppar=temppar->parent;
	}
	for(int j=0;j<i;j++)
	{
		current->path[j]=revPath[i-j-1];
	}
}