哈夫曼树

一棵裸的哈夫曼树，看点可能在于封装（

嘛，反正是留档给自己看的

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<vector>
using namespace std;

typedef char Type;
typedef struct NODE{
	Type data;
	int weight;
	NODE* Lchild;
	NODE* Rchild;
	NODE* Parent;
}NODE,*node;//树的结点 
struct cmp{
	Type data;
	int weight;
	node selfroot;
	friend bool operator >(const cmp& a,const cmp& b)
	{
		return a.weight>b.weight;
	}
};//为了使用优先队列，必须重载大于号，而重载大于号不能针对指针，故有此类型 

class HuffmanTree
{
	private:
		int n;
		node root;
		cmp temp[100];
		map<string,char>m;//序列对字符的映射 
		void print(char x,string y)
		{
			cout<<x<<" "<<y<<endl;
		}
		void cal(node T,string num)
		{
			if(n==1)
			{
				print(root->data,"0");
				return;
			}
			if(T->data=='#')
			{
				cal(T->Lchild,num+"0");
				cal(T->Rchild,num+"1");
				return;
			}
			print(T->data,num);
			m[num]=T->data;
		}
		void destroy(node T)
		{
			if(T->Lchild!=NULL) destroy(T->Lchild);
			if(T->Rchild!=NULL) destroy(T->Rchild);
			delete T;
		}
	public:
		HuffmanTree()
		{
			root=NULL;
		}
		void init()
		{
			cout<<"请输入字符个数n（n<100）。接下来n行，每行输入一个字符及其权重。（输入的字符不可以是#）\n";
			cin>>n;
			for(int i=0;i<n;i++)
			{
				cin>>temp[i].data>>temp[i].weight;
				temp[i].selfroot=new NODE;
				node p=temp[i].selfroot;
				p->data=temp[i].data;
				p->weight=temp[i].weight;
				p->Lchild=p->Rchild=p->Parent=NULL;
			}
		}
		void build()
		{
			priority_queue<cmp,vector<cmp>,greater<cmp> >q;
			for(int i=0;i<n;i++) q.push(temp[i]);
			while(!q.empty())
			{
				cmp p1=q.top();
				q.pop();
				if(q.empty())
				{
					root=p1.selfroot;
					break;
				}
				cmp p2=q.top();
				q.pop();
				cmp tmp;
				tmp.data='#';
				tmp.weight=p1.weight+p2.weight;
				tmp.selfroot=new NODE;
				
				node kp=tmp.selfroot;
				kp->data=tmp.data;
				kp->weight=tmp.weight;
				kp->Parent=NULL;
				p1.selfroot->Parent=p2.selfroot->Parent=kp;
				if(p1.weight<p2.weight)
				{
					kp->Lchild=p1.selfroot;
					kp->Rchild=p2.selfroot;
				}
				else
				{
					kp->Rchild=p2.selfroot;
					kp->Lchild=p1.selfroot;
				}
				q.push(tmp);
			}
		}
		void show()
		{
			cout<<"所求出的对应编码表如下（不按顺序）：\n";
			cal(root,"");
			cout<<endl;
		}
		void solve()
		{
			string str,ans="";
			cout<<"请输入待解码的合法01序列\n";
			cin>>str;
			int len=str.length();
			for(int i=0;i<len;i++)
			{
				int cnt=1;
				string tmp=str.substr(i,1);
				map<string,char>::iterator it=m.find(tmp);
				while(it==m.end())
				{
					cnt++;
					if(i+cnt>len)
					{
						cout<<"输入序列不合法！\n";
						return;
					}
					tmp=str.substr(i,cnt);
					it=m.find(tmp);
				}
				ans+=m[tmp];
				i+=cnt-1;
			}
			cout<<"解码后的序列为："<<ans<<endl<<endl; 
		}
		void del()
		{
			destroy(root);
			cout<<"该哈夫曼树已经成功销毁！\n";
		}
};

int main()
{
	HuffmanTree ht;
	ht.init();
	ht.build();
	ht.show();
	ht.solve();
	ht.del();
	return 0;
}