这篇文章主要为大家详细介绍了C语言实现哈夫曼树的构建，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
哈夫曼树（霍夫曼树）又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
#include #include #include /* 哈夫曼树的结构体 */ typedef struct stHuNode { int data; //权值 struct stHuNode* lchild, *rchild; }HUNODE; /* * 找出权值数组里面,最小的两个权值下标 * 函数请参：HUNODE *pArray[] 存放节点的指针数组 int n 数组里面的元素个数 int* p1 存放最小权值的下标 int* p2 存放第二小权值的下标 */ int findSmallData(HUNODE *pArray[] ,int n,int* p1, int* p2) { int index = 0; int fir_small = 0xffff, sec_small = 0xffff; if(pArray == NULL) { return 1; } for(index = 0; index data data; *p2 = *p1; *p1 = index; } else if(pArray[index]->data data; *p2 = index; } } } return 0; } /* * 函数功能：构建哈夫曼树 * 函数请参：int* a 权值数组 int n 这个数组里面有多少个数据 */ HUNODE* createHuTree(int* a, int n) { int index = 0; int fir_small = 0, sec_small = 0; /* 定义一个指针数组,最大是100 */ HUNODE *pArray[100]; HUNODE *pNewNode = NULL; /* 先创建n个root节点*/ memset(pArray,0,sizeof(HUNODE)*n<div style="color:transparent">来源gaodai^.ma#com搞#代!码网</div>); for(index = 0; index data = a[index]; pNewNode->lchild = NULL; pNewNode->rchild = NULL; /* 把这个节点存放在指针数组中去 */ pArray[index] = pNewNode; } /* 构建哈夫曼树 */ for(index = 0; index data = 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; } return pNewNode; } /* 前序遍历该二叉树 */ void preOrderHuffMan(HUNODE* root) { if(root) { printf("%d ",root->data); preOrderHuffMan(root->lchild); preOrderHuffMan(root->rchild); } } int main() { int a[4] = {7,5,2,4}; HUNODE* root = NULL; /* 构建哈夫曼树 */ root = createHuTree(a,4); /* 前序遍历 */ preOrderHuffMan(root); printf("\n"); return 0; }
以上就是C语言实现哈夫曼树的构建的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C语言实现哈夫曼树的构建
转载请注明原文链接：C语言实现哈夫曼树的构建
