欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

构造哈夫曼树

程序员文章站 2024-01-09 20:17:16
...

1.算法说明

就是建造哈夫曼树树,从而使得构造出的树带权路径长度最小

 

2.步骤

 

输入叶子结点个数n;

创建长度为2*n-1的数组并初始化;

while(i<n) 循环输入n个叶子结点的权值;

while(n-1次循环建立树){

在parent==-1的元素中查找权最小的两个结点;

合并两个叶子结点,并加入新结点到数组;

}

 

3.代码

//构造haffman树
#include <iostream>
using namespace std;
const int MAX = 10000;
struct Node{
	int weight;			//权值
	int parent;			//双亲
	int lchild;			
	int rchild;
};

//创建一个haffman树
void createHaffman(Node* &a, int n){
	int m1,m2, x1, x2;//m1,m2是最小的两个值,x1,x2是他们的位置
	//n个结点,只需要n-1次就可以构造好
	for(int i=0; i<n-1; i++){
		m1 = m2 = MAX;
		x1 = x2 = 0;
		//查找最小值,在查找到最小的两个值后,构造新的节点,并加入到a中(数组的n+i个节点之后),长度加1,故而查找过程中长度不断增加n+i
		for(int j=0; j<n+i; j++){
			//首先必须满足,还没有双亲的孤立节点,查找m1,m2都是最小
			if(a[j].parent == -1 && a[j].weight < m1){
				m1 = a[j].weight;
				x1 = j;
			}else if(a[j].parent == -1 && a[j].weight < m2){
				m2 = a[j].weight;
				x2 = j;
			}
		}
		//新的节点存入n+i,并设置x1, x2的双亲
		a[x1].parent = n+i;
		a[x2].parent = n+i;
		a[n+i].weight = a[x1].weight + a[x2].weight;
		a[n+i].parent = -1;
		a[n+i].lchild = x1;
		a[n+i].rchild = x2;
	}
}

//测试得到最小和次小的值
void test(){
	int a[] = {3,4,7,0,79,9,12,1,4};
		int m = MAX,k = MAX;
	for(int i=0; i<9; i++){
		if(a[i]<m){
			 m = a[i];
		}else if(a[i]<k){
			 k = a[i];
		}
		
	}
	cout<<m<<" "<<k<<endl;
}


int main(){
	int n;
	cout<<"输入叶子节点个数:";
	cin>>n;
	Node* a = new Node[2*n - 1];
	for(int i=0; i<2*n-1; i++){//初始化
		a[i].weight = 0;
		a[i].parent = -1;
		a[i].lchild = -1;
		a[i].rchild = -1;
	}
	
	cout<<"输入前n个叶子结点的权值"<<endl;
	for(int i=0; i<n; i++){
		cin>>a[i].weight;
	}
	
	cout<<"输出构造好的haffman树"<<endl;
	createHaffman(a, n);
	for(int i=0; i<2*n-1; i++){
		cout<<"["<<a[i].weight<<","<<a[i].parent<<","<<a[i].lchild<<","<<a[i].rchild<<"]"<<endl;
	}
	
	delete[] a;
	return 0;
}