明白的看看代码就行，不明白的好好看看文章差不多就懂了

目     录

一、哈夫曼树是什么？

二、代码及画法（操作步骤）

1.代码

2.操作步骤

 3.画法（算法）

总结

---

---

前言

想必我们高校大学生和一些小白在日常学习以及工作当中都会遇到哈夫曼树，特别是在学习数据结构和C语言的时候仔细听，下课还听不懂；不仔细听更是一塌糊涂；权值较多或权值相同时更是愁上加愁，就算写了出来也会发现上面的权值比下面的小，这还会让你重新再写。反反复复的从头再来也没能让你找到规律。那么接下来下面这些文字及代码就是关于哈夫曼树简单的算法，过程就只需要输入计算的权值总数以及依次输入权值，方可出现运算结果，详情如下：

一、哈夫曼树是什么？

      哈夫曼树是一种特殊的二叉树，这种树的所有的叶子节点都有权值，从而构造出带权路径长度最短的二叉树，即哈夫曼树，又称最优树。

【内容来源：数据结构（C语言版）上海交通大学出版社】

二、代码及画法（操作步骤）

1.代码

代码如下：

#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");
 else
    printf("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  ");
}

2.操作步骤

操作步骤如下：

1. 请将上面代码复制到C语言编程软件中并对其运行

    2.首先输入要输入权值的总数

    3. 依次输入各项权值

    4. 在输入完上面两项数值后哈夫曼树的两边数值及编码的结果就出来了

---

 3.画法（算法）

首先要画出哈夫曼编码树，上面的显示结果已经明确给出，只不过就是不能系统画出“树”，只能通过数值表示。画法如下：

        1.建议从下往上画，即最下边一行的和为229—其分左边值91和右边值138（在树的顶点画229，其分左右边的数值）

        2.接着倒数第二行两边和为138，左边值为65、右边值为73（在顶点229分出的右边值138下在分左右边的数值）    依次类推，一个哈夫曼编码树就画出来了

        3.哈夫曼编码是在“树”画完之后，按照 左“0” 右“1”排序的。此程序代码是由下往上排序的，正常来讲应该是由上往下排序。所以只需将运行结果的编码颠倒写就可以（程序当中也可以改动） 

        下面的图片便是上面运行举例和画法（算法）的结果

总结

哈夫曼编码树要确保一行的数值是由小到大，上一行数值要比下行数值大，相同的数值 旧>新（即新在就的左边）这几项原则就可以了（兴许有偏差，因为这是老师教我的）

以上为哈夫曼树的代码、操作步骤以及画法，其中代码是我在上学时跟老师所敲的，画法是我个人理解并画的；

另外这个程序还有很多欠缺，如：

哈夫曼编码树不能完全画出；

遇到相同数值容易发生错误；

哈夫曼树编码与实际相反（这个有的人觉得是对的，有的认为不对，在程序上略加改动即可）；

文中若有不妥之处请谅解！有不明白的请在评论区问哦