好资源导航 » 文章资讯 » C语言实现哈夫曼树的构建

C语言实现哈夫曼树的构建

2023-07-26 13:00:05 78

哈夫曼树（霍夫曼树）又称为最优树.

1、路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL

#include
#include
#include


/*哈夫曼树的结构体*/
typedefstructstHuNode
{
intdata;//权值
structstHuNode*lchild,*rchild;
}HUNODE;


/*
*找出权值数组里面,最小的两个权值下标
*函数请参：HUNODE*pArray[]存放节点的指针数组
intn数组里面的元素个数
int*p1存放最小权值的下标
int*p2存放第二小权值的下标
*/
intfindSmallData(HUNODE*pArray[],intn,int*p1,int*p2)
{
intindex=0;
intfir_small=0xffff,sec_small=0xffff;

if(pArray==NULL)
{
return1;
}

for(index=0;indexdatadata;

*p2=*p1;
*p1=index;
}
elseif(pArray[index]->datadata;
*p2=index;
}
}
}

return0;
}
/*
*函数功能：构建哈夫曼树
*函数请参：int*a权值数组
intn这个数组里面有多少个数据
*/

HUNODE*createHuTree(int*a,intn)
{
intindex=0;

intfir_small=0,sec_small=0;

/*定义一个指针数组,最大是100*/
HUNODE*pArray[100];
HUNODE*pNewNode=NULL;


/*先创建n个root节点*/
memset(pArray,0,sizeof(HUNODE)*n);
for(index=0;indexdata=a[index];
pNewNode->lchild=NULL;
pNewNode->rchild=NULL;

/*把这个节点存放在指针数组中去*/
pArray[index]=pNewNode;
}

/*构建哈夫曼树*/
for(index=0;indexdata=pArray[fir_small]->data+pArray[sec_small]->data;

/*最小的是左孩子，第二小的是右孩子*/
pNewNode->lchild=pArray[fir_small];
pNewNode->rchild=pArray[sec_small];

/*把新的节点放入到指针数组里面去*/
pArray[fir_small]=NULL;
pArray[sec_small]=pNewNode;

}
returnpNewNode;
}

/*前序遍历该二叉树*/
voidpreOrderHuffMan(HUNODE*root)
{
if(root)
{
printf("%d",root->data);
preOrderHuffMan(root->lchild);
preOrderHuffMan(root->rchild);
}
}

intmain()
{
inta[4]={7,5,2,4};
HUNODE*root=NULL;

/*构建哈夫曼树*/
root=createHuTree(a,4);

/*前序遍历*/
preOrderHuffMan(root);
printf("\n");

return0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

返回顶部
514930285
czq8825@qq.com

C语言实现哈夫曼树的构建

热门推荐

随机推荐