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

1、路径和路径长度

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

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

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

3、树的带权路径长度

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

#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; HUNODE *pArray[100]; HUNODE *pNewNode = NULL; 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++) { 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;}

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