数据结构——哈夫曼树编程，输入权值实现流程图代码

一、须知

       本代码是在数据结构——哈夫曼树编程上建立的，使用时需将代码剪切到C++等软件中。需要输入权值方可实现流程图，但是还需要按照编程换算出的结果自己用笔画出流程图。
       下面将代码粘贴到文章中，同时举一个例子：
二、代码段

#include "stdio.h"
#define MAXLEN 100
typedef struct                       //定义本机构体
{int weight;                      //定义一个整形权值的变量int lchild,rchild,parent;        //分别定义左孩子、右孩子及双亲指针
}HTNode;
typedef HTNode HT[MAXLEN];           //表明向量的类型
int n;                               //定义整形变量n
//-----------------初始化子函数---------------------------------------------
void InitHFMT (HT T)
{ int i;printf("\n请输入权值的总数(需小于100):");scanf("%d",&n);for(i=0;i<2*n-1;i++){T[i].weight=0;T[i].lchild=-1;T[i].rchild=-1;T[i].parent=-1;}
}
//-----------------输入权值子函数-------------------------------------------- 
void InputWeight (HT T)
{int w,i;for(i=0;i<n;i++){printf("请输入第%d个权值:",i+1);scanf("%d",&w);getchar();T[i].weight=w;}
}
//-----------------选择两个结点中小的结点------------------------------------ 
void SelectMin (HT T,int i,int *pl,int *p2)
{long minl=888888,min2=888888;    //设两个长整型数值，并使它大于可能会出现的最大权值int j;for(j=0;j<=i;j++){if(T[j].parent==-1){if(minl>T[j].weight){   minl=T[j].weight;        //找出最小权值*pl=j;                   //通过*p1带回序号}}
}for (j=0;j<=i;j++){  if(T[j].parent==-1){ if (min2>T[j].weight&&j!=(*pl)){ min2=T[j].weight;      //找出第二最小权值*p2=j;                   //通过*p2带回序号}}}
}
//-----------------构造哈夫曼树，T[2*n-1]为根节点-----------------------------void CreatHFMT (HT T){int i,pl,p2;InitHFMT (T);InputWeight(T);for(i=n;i<2*n-1;i++){  SelectMin(T,i-1,&pl,&p2);T[pl].parent=T[p2].parent=i;T[i].lchild=T[pl].weight;T[i].rchild=T[p2].weight;T[i].weight=T[pl].weight+T[p2].weight;}}
//-----------------输出向量状态表----------------------------------------------  
void printHFMT (HT T)
{ int i;printf("\n哈夫曼树的两边显示为(建议由下往上看/画):\n");for(i=0;i<2*n-1;i++)while(T[i].lchild!=-1){printf("(两边和为%d,左边值为%d,右边值为%d)\n",T[i].weight,T[i].lchild,T[i].rchild);break;}
}
//-----------------哈夫曼编码函数----------------------------------------------
void hfnode(HT T,int i,int j)
{j=T[i].parent;if (T[j].rchild==T[i].weight)printf("1");elseprintf("0");if(T[j].parent!=-1)i=j,hfnode (T,i,j);
}
//-----------------求哈夫曼树编码----------------------------------------------  
void huffmannode(HT T)
{int i,j,a;printf("\n输入的权值的对应哈夫曼树编码(下面的哈夫曼编码树是由下往上排序的!!!):");for (i=0;i<n;i++){j=0;a=i;printf("\n%i的编码为:",T[i].weight);hfnode(T,i,j);i=a;}
}
//-----------------主函数-------------------------------------------------------
void main()
{   HT HT;CreatHFMT(HT);printHFMT(HT);huffmannode(HT);printf("\n  ");
}

三、举例（流程图）

1.首先输入：权值总数以及各个权值，编程便可实现；
 

 2.按照代码画流程图，以上面图片的权值举例，在编程结果出来后：首先看两面的数值，

先看最后一行的和为37，那么流程图的总数（最高点）便变为37
其次37的下面左边值为17，右边值为20
在看上一行，和为20，那么对照代码下一行两边的值可知，右边值为20
所以在右边值下的左边值和右边值分别为10
依次往上，就不都举例了······

本编程的哈夫曼树编码有问题，其所给的数值与实际答案是相反的列入9的变为为10，那么他真正的编码为01。就是1为0，0为1.

 四、结语

       本编程是能快速实现哈夫曼树的编码结果，有基础的同学看一下流程就知道是什么回事了，基础差的需要慢慢理解，本文章就不详细再讲了，同时这个代码有些错误，用能力者可以修改调试，实现更加完美的程序！