哈夫曼树的带权路径长度怎么求（哈夫曼树）

大家好，我是小华，我来为大家解答以上问题。哈夫曼树的带权路径长度怎么求，哈夫曼树很多人还不知道，现在让我们一起来看看吧！

1、#include#include #define MAXSIZE 30/*自定义哈夫曼的最大个数*/ typedef struct { int weight;/*结点的权值*/ int parent;/*结点的双亲*/ int lchild;/*结点的左孩子*/ int rchild;/*结点的右孩子*/ int flag;/*是否用过的标志*/ }HufmTree; int p1,p2;/*定义全局下标数字，用于Select（）函数返回当前哈夫曼树中最小 两个未用的结点/森林的下标*/ void CreatHuffman(HufmTree tree[] ,int n );/*构造哈夫曼树函数*/ void Select(HufmTree tree[] ,int i );/*选择最小两个森林的函数*/ void DisplayTree(HufmTree tree[],int Number);/*输出哈夫曼树函数*/ void main() { int InputNumber;/*输入森林结点的个数*/ printf("******本程序用于演示哈夫曼树的构造结果***** "); HufmTree mytree[MAXSIZE];/*声名一个棵哈夫曼树*/ printf("请输入结点个数： "); scanf("%d",&InputNumber); CreatHuffman( mytree,InputNumber );//构造哈夫曼树 DisplayTree(mytree,InputNumber);//输出哈夫曼树 } /*-------------------------------------------- *函数功能：构造哈夫曼树 *函数参数：自定义构造体，结构体数组 *函数返回值：没有 --------------------------------------------*/ void CreatHuffman(HufmTree tree[] ,int n ) { int i,m; if(n<=1)/*森林个数小于或等于一退出*/ { return; } m=2*n;/*所建哈夫曼树最后结点的最大个数-1*/ for(i=1;itree[j].weight))/*跳过于用过的结点（用过后不是森*/ { /*林中的结点）*/ MinValue1=tree[j].weight;/*如果后面森林的结点值比MinValue1小*/ p1=j; /*P1就指向它*/ } } tree[p1].flag=1;/*把tree[p1]从森林中去掉，它已经用过*/ /*也为了p1 p2 不为同一个值*/ for( i=1;tree[i].flag!=0;i++)/*找到前中tree[i]没有个的第一个结点*/ { /*找到森林中的一个结点*/ } MinValue2=tree[i].weight;/*把找到的结点当做最小的结点*/ p2=i;/*第二小值结点的下标值*/ for(j=i+1;j<=number;j++) { if((tree[j].flag!=1)&&(MinValue2>tree[j].weight))/*跳过于用过的结点（用过后不是森*/ { /*林中的结点）*/ MinValue2=tree[j].weight;/*如果后面森林的结点值比MinValue1小*/ p2=j; /*P1就指向它*/ } } } /*-------------------------------------------- *函数功能：输出哈夫曼树 *函数参数：参数1 自定义构造体，结构体数组。

2、 * 参数2 输入结点的个数 *函数返回值：没有 --------------------------------------------*/ void DisplayTree(HufmTree tree[],int Number) { for(int i=1;i<2*Number;i++) { printf("%5d",tree[i].weight); } printf(" "); for(i=1;i<2*Number;i++) { printf("HufmTree[%2d].parent=%3d ",i,tree[i].parent);//输出当前元素的parent值 printf("HufmTree[%2d].weight=%3d ",i,tree[i].weight);//输出当前元素的weight值 printf("HufmTree[%2d].lchild=%3d ",i,tree[i].lchild);//输出当前元素的lchild值 printf("HufmTree[%2d].rchild=%3d ",i,tree[i].rchild);//输出当前元素的rchild值 } }。

本文到此讲解完毕了，希望对大家有帮助。