用c语言实现哈夫曼树的建立（哈夫曼树的构造c语言代码）

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

1、路径和路径长度

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

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

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

3、树的带权路径长度

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 #include <stdio.h> #include <stdlib.h> #include <string.h> /* 哈夫曼树的结构体 */ 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 < n; index++) { /* 当前的下标下面是有节点的*/ if(pArray[index] != NULL) { if(pArray[index]->data < fir_small) { sec_small = fir_small; fir_small = pArray[index]->data; *p2 = *p1; *p1 = index; } else if(pArray[index]->data < sec_small) { sec_small = pArray[index]->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); for(index = 0; index < n; index++) { pNewNode = (HUNODE*)malloc(sizeof(HUNODE)); memset(pNewNode,0,sizeof(HUNODE)); pNewNode->data = a[index]; pNewNode->lchild = NULL; pNewNode->rchild = NULL; /* 把这个节点存放在指针数组中去 */ pArray[index] = pNewNode; } /* 构建哈夫曼树 */ for(index = 0; index < n-1; index++) { /* fir_small 存放最小权值的下标 sec_small存放第二个小的权值下标*/ findSmallData(pArray,n,&fir_small,&sec_small); /* 分配节点内存 */ pNewNode = (HUNODE*)malloc(sizeof(HUNODE)); memset(pNewNode,0,sizeof(HUNODE)); pNewNode->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; }