用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c代码库

哈夫曼树(最优二叉树)的构造算法

2012-10-09 作者: 神马举报

[c]代码库

#define MAXVALUE 10000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树中叶子结点个数*/
#define MAXNODE MAXLEAF*2-1
typedef struct
{
	int weight;
	int parent;
	int lchild;
	int rchild;
} HNodeType;
void HaffmanTree ( HNodeType HuffNode [ ] )
{/*哈夫曼树的构造算法*/
	int i,j,m1,m2,x1,x2,n;
	scanf ( “%d”,&n ); /*输入叶子结点个数*/
	for ( i=0; i<2*n-1; i++ ) /*数组HuffNode[ ]初始化*/
	{
		HuffNode[i].weight=0;
		HuffNode[i].parent=-1;
		HuffNode[i].lchild=-1;
		HuffNode[i].rchild=-1;
	}
	for ( i=0; i<n; i++ ) scanf ( “%d”,&HuffNode[i].weight ); /*输入n 个叶子结点的权值*/
	for ( i=0; i<n-1; i++ ) /*构造哈夫曼树*/
	{
		m1=m2=MAXVALUE;
		x1=x2=0;
		for ( j=0; j<n+i; j++ )
		{
			if ( HuffNode[j].weight<m1 && HuffNode[j].parent==-1 )
			{
				m2=m1;
				x2=x1;
				m1=HuffNode[j].weight;
				x1=j;
			}
			else if ( HuffNode[j].weight<m2 && HuffNode[j].parent==-1 )
			{
				m2=HuffNode[j].weight;
				x2=j;
			}
		}
		/*将找出的两棵子树合并为一棵子树*/
		HuffNode[x1].parent=n+i;
		HuffNode[x2].parent=n+i;
		HuffNode[n+i].weight= HuffNode[x1].weight+HuffNode[x2].weight;
		HuffNode[n+i].lchild=x1;
		HuffNode[n+i].rchild=x2;
	}
}


网友评论    (发表评论)


发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

输入口令后可复制整站源码

加载中,请稍后...