哈夫曼.cpp

数据结构哈夫曼树

#include<iostream.h>

#include"二叉树.h"

BTreeNode* CreateHuffman(ElemType a[], int n)
//根据数组a中n个权值建立一棵哈夫曼树，返回树根指针
{
	BTreeNode** b, * q;
	//动态分配一个由b指向的指针数组
	b=new BTreeNode* [n];
	int i, j;
	//初始化b指针树组，使每个指针元素指向a数组中对应元素结点
	for (i=0; i<n; i++) {
		b[i]=new BTreeNode;
		b[i]->data=a[i];  b[i]->left=b[i]->right=NULL;
	}
	//进行n-1次循环建立哈夫曼树
	for (i=1; i<n; i++) {
		//用k1表示森林中具有最小权值的树根结点的下标，
		//用k2表示森林中具有次最小权值的树根结点的下标
		int k1=-1, k2;
		//让k1初始指向森林中第一棵树，k2初始指向森林中第二棵树
		for (j=0; j<n; j++) {
			if(b[j]!=NULL && k1==-1) {k1=j; continue;}
			if(b[j]!=NULL) {k2=j; break;}
		}
		//从当前森林中求出最小权值树和次最小权值树
		for(j=k2; j<n; j++) {
			if(b[j]!=NULL) {
				if(b[j]->data<b[k1]->data) {k2=k1; k1=j;}
				else if (b[j]->data<b[k2]->data) k2=j;
			}
		}
		//由最小权值树和次小权值树建立一棵新树，q指向树根结点
		q=new BTreeNode;
		q->data=b[k1]->data+b[k2]->data;
		q->left=b[k1]; q->right=b[k2];
		//将指向新树的指针赋给b指针数组中k1位置，k2位置置为空
		b[k1]=q; b[k2]=NULL;
	}
	//删除动态建立的数组b
	delete []b;
	//返回整个哈夫曼树的树根指针
	return q;
}

ElemType WeightPathLength(BTreeNode* FBT, int len)
//根据FBT指针所指向的哈夫曼树求出带权路径长度,len初值为0
{
	if(FBT==NULL) return 0;  //空树则返回0
	else {
		//访问到叶子结点时返回该结点的带权路径长度，其中值参len保存
		//当前被访问结点的路径长度（即层数）
		if(FBT->left==NULL && FBT->right==NULL) {
			return FBT->data* len;
		}
		//访问到非叶子结点时进行递归调用，返回左右子树的带权
		//路径长度之和，向下深入一层时len值增1
		else {
			return WeightPathLength(FBT->left, len+1)+
				WeightPathLength(FBT->left, len+1);
		}
	}
}

void HuffManCoding(BTreeNode* FBT, int len)
//根据FBT指针所指向的哈夫曼树输出每个叶子结点的编码，len初值为0
{
	static int a[10];   //数组长度至少要等于哈夫曼树的深度减1
	if(FBT!=NULL) {
		//访问到叶子结点时输出其保存在数组a中的0和1序列编码
		if(FBT->left==NULL && FBT->right==NULL) {
			cout<<"结点权值为"<<FBT->data<<"的编码：";
			for (int i=0; i<len; i++) cout<<a[i]<<' ';
			cout<<endl;
		}
		//访问到叶子结点时分别向左右子树递归调用，并分别把分支上
		//的0,1编码保存到数组a的对应元素中，向下深入一层时len值增1
		else {
			a[len]=0; HuffManCoding(FBT->left,len+1);
			a[len]=1; HuffManCoding(FBT->right,len+1);
		}
	}
}


void main()
{
	cout<<"从键盘输入待构造的哈夫曼树中带权叶子结点数n：";
	int n;
	while(1) {cin>>n; if(n>1) break; else cout<<"重输n值：";}
	cout<<"输入"<<n<<"个权值：";
	ElemType* a=new ElemType[n];
	for(int i=0; i<n; i++) cin>>a[i];
	//根据数组a建立哈夫曼树
	BTreeNode* fbt=CreateHuffman(a,n);
	//以广义表形式输出哈夫曼树
	cout<<"广义表形式的哈夫曼树:";
	PrintBTree(fbt); cout<<endl;
	//输出哈夫曼树的权值，即带权路径的长度
	cout<<"哈夫曼树的权：";
	cout<<WeightPathLength(fbt,0)<<endl;
	//输出哈夫曼编码，即每个叶子结点所对应的0,1序列
	cout<<"哈夫曼编码：";
	HuffManCoding(fbt,0);
	//清除以bt为树根指针的二叉树
	ClearBTree(fbt);
}