二叉树的路径和？
所有叶子节点路径的总和。
什么是哈夫曼树？
路径和最短的二叉树


如何构造最优二叉树，也就是哈夫曼树


哈夫曼树的构建过程？
1.给出一个数组，以每个元素为基础，创建一个叶子节点数组。
2.从中找出权值最小的两个节点，构建一棵树。这棵树的权值等于两个节点权值之和。左子树等于权值最小的那个节点，右子树等于权值次小的那个节点。
3.将该树的根放入节点数组中原来权值最小的那个位置
4.不断执行2-3步骤，最终得到一棵哈夫曼树。


编程要点：找出最小的那个节点，再找出权值次小的那个节点。


代码实现过程：
#include<stdio.h>
#include<stdlib.h>

//二叉树的节点结构定义
struct _tree_node
{
	//用来存放数据
	int data;
	//存放左子树地址的指针
	struct _tree_node *left_tree;
	//存放右子树地址的指针
	struct _tree_node *right_tree;
};
//定义类型
typedef struct _tree_node t_tree_node;


//创建结点
t_tree_node *make_node(int data)
{
	//分配一个内存
	t_tree_node *tree_node_temp=malloc(sizeof(t_tree_node));
	//将数据放入该结点，且左右子树设为空
	tree_node_temp->data=data;
	tree_node_temp->left_tree=NULL;
	tree_node_temp->right_tree=NULL;

	//将该内存的首地址返回
	return tree_node_temp;
}


//结点插入到树里
t_tree_node *insert_tree_node(t_tree_node *root,t_tree_node *newnode)
{
	//如果根结点为空，则插入根节点
	if(root==NULL) //第二次进来则相当于if(root->right_tree==NULL)
	{
		root=newnode;
		return root;
	}
	else
	{	
		//如果数据大于根节点的数据则放到右边
		if(newnode->data>root->data)
		{
			root->right_tree=insert_tree_node(root->right_tree,newnode);
		}
		else
		{
			root->left_tree=insert_tree_node(root->left_tree,newnode);
		}
	}
	return root;
}

t_tree_node *del_tree(t_tree_node *root)
{
	//如果根非空
	if(root)
	{
		//先删左子树
		root->left_tree=del_tree(root->left_tree);
		//再删右子树
		root->right_tree=del_tree(root->right_tree);
		//才是除根
		free(root);
		root=NULL;
		return root;
	}
}


//中序遍历打印节点
void print_tree(t_tree_node *root)
{
	if(root)
	{
		print_tree(root->left_tree);
		printf("%d ", root->data);
		print_tree(root->right_tree);
	}
	
}

//二叉树的深度
int depth(t_tree_node *root)
{
	if(root==NULL)
	{
		return 0;
	}
	else
	{
		int ldepth=depth(root->left_tree);//40这个节点，左右子树为空
		int rdepth=depth(root->right_tree);//60这个节点，

		if(ldepth>rdepth)
		{
			return ldepth+1;			
		}
		else
		{
			return rdepth+1;
		}
	}
}

//构建哈弗曼树
t_tree_node *creat_huffman(int a[],int length)
{
	//定义一个节点指针的数组
	t_tree_node **array=malloc(length*sizeof(t_tree_node *));

	//定义一个节点用来创建树
	t_tree_node *q;
	
	int j;
	int zuixiao_idx,cixiao_idx;

	//创建节点数组
	int i;
	for (i=0;i<length;i++)
	{
		array[i]=malloc(sizeof(t_tree_node));
		array[i]->data=a[i];
		array[i]->left_tree=NULL;
		array[i]->right_tree=NULL;
	}
	//比较的循环，次数是数组长度-1
	for(i=0;i<length-1;i++)
	{
		
		j=0;
		//找出一个非空节点
		while(array[j]==NULL)
		{
			j++;
		}
		//第一个非空节点
		zuixiao_idx=j;

		for(j=0;j<length;j++)
		{
			if(array[j]&&array[j]->data<array[zuixiao_idx]->data)
			{
				zuixiao_idx=j;
			}
		}

		j=0;
		//找出一个非空节点
		while(array[j]==NULL||j==zuixiao_idx)
		{
			j++;
		}
		cixiao_idx=j;
		//和其它节点对比
		for (j=0;j<length;j++)
		{
			if(array[j]&&array[j]->data<array[cixiao_idx]->data&&j!=zuixiao_idx)
			{
				cixiao_idx=j;
			}
		}

		q=malloc(sizeof(t_tree_node));
		q->data=array[zuixiao_idx]->data+array[cixiao_idx]->data;
		q->left_tree=array[zuixiao_idx];
		q->right_tree=array[cixiao_idx];

		//创建之后放到原来权值最小节点的位置
		array[zuixiao_idx]=q;
		array[cixiao_idx]=NULL;

	}
	free(array);
	array=NULL;
	return q;
}

//带权路径和
int lengthsum(t_tree_node *root,int len)
{
	if(root==NULL)
	{
		return 0;
	}
	else if(root->left_tree==NULL&&root->right_tree==NULL)
	{
		return root->data*len;
	}
	else
	{
		return lengthsum(root->left_tree,len+1)+lengthsum(root->right_tree,len+1);
	}
}


int main(void)
{
	//创建一棵树
	t_tree_node *root=NULL;

	// //定义一个临时变量，用来存储输入的数据
	// int input;
	// //从键盘输入多个数，输入-1来结束输入
	// while(scanf("%d",&input)&&input!=-1)
	// {
	// 	//将创建的节点插入树里
	// 	root=insert_tree_node(root,make_node(input));

	// }
	int a[12]={85,63,27,89,64,74,13,15,67,68,94,46};
	root=creat_huffman(a,12);
	//遍历节点
	print_tree(root);

	//删除一棵树
	root=del_tree(root);

}

C语言 数据结构实验五 哈夫曼树的创建与哈夫曼编码
实验内容:

假设用于通信的电文仅由a,b,c,d,e,f,g,h几个字母组成，字母在电文中出现的频率分别为0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10，试为这些字母设计哈夫曼编码。
设计思想

哈夫曼树构造：每次把根结点权值最小的两个二叉树合并，新结点的权值等于两个根结点权值之和，得到新的二叉树。

结构体构造：包括数据、权值、以及父亲、左孩、右孩结点在数组中位置。

哈夫曼编码：规定哈夫曼树中全部左分支表示字符0，全部右分支表示字符1,将依次从根结点到每一个叶子结点所经过的分支的二进制位的序列作为该结点相应的字符编码。
代码如下：

哈夫曼树和编码结构体
#define N 100

typedef struct
/*静态三叉链的扩展存储，包括数据+权值+父亲、左孩、右孩结点在数组中位置*/
{
	char data;		/*结点值*/
	double weight;	/*权重*/
	int parent;		/*双亲结点*/
	int lchild;		/*左孩子结点*/
	int rchild;		/*右孩子结点*/
} HTNode;
typedef struct
{
    char cd[N];      //存放当前结点的哈夫曼码
    int start;       //表示cd[start…n0]部分是哈夫曼码
}HCode;

创建哈夫曼树
void createHT(HTNode ht[],int n0)
 {
     int i,k,lnode,rnode;
     double min1,min2;
     for(i=0;i<2*n0-1;i++)      //所有结点的相关域值初值为-1
        ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
     for(i=n0;i<=2*n0-2;i++)    //构造哈夫曼树的n0-1个分支结点
     {
         min1=min2=32767;       //lnode和rnode为最小权重的两个结点位置
         lnode=rnode=-1;
         for(k=0;k<=i-1;k++)   //在ht[0…i-1]中找权值最小的两个结点
             if(ht[k].parent==-1)  //只在尚未构造二叉树的结点中查找
             {
                 if(ht[k].weight<min1)
                 {
                     min2=min1;rnode=lnode;
                     min1=ht[k].weight;lnode=k;
                 }
                 else if(ht[k].weight<min2)
                 {
                     min2=ht[k].weight; rnode=k;
                 }
             }
         ht[i].weight=ht[lnode].weight+ht[rnode].weight;
         ht[i].lchild=lnode; ht[i].rchild=rnode;        //ht[i]作为双亲结点
         ht[lnode].parent=i; ht[rnode].parent=i;
     }
 }

哈夫曼编码
void createHCode(HTNode ht[],HCode hcd[],int n0,int L[])
{
    int i,f,c;
    HCode hc;
    for(i=0;i<n0;i++)              //根据哈夫曼树求哈夫曼编码
    {
        hc.start=n0;c=i;
        f=ht[i].parent;
        while(f!=-1)              //循环直到无双亲结点，即达到根结点
        {
            if(ht[f].lchild==c)   //当前结点是双亲结点的左孩子
                hc.cd[hc.start--]='0';
            else                  //当前结点是双亲结点的右孩子
                hc.cd[hc.start--]='1';
            c=f;f=ht[f].parent;    //再对双亲结点进行同样的操作
        }
        hc.start++;                //start指向哈夫曼编码最开始的字符
        hcd[i]=hc;
        L[i]=n0-hc.start+1;
    }
}

主函数
int main()
{
    //输入相应的值，构造哈夫曼树
    int n0;
    printf("请输入编码字符个数：");
    scanf("%d",&n0);
    HTNode ht[N];
    printf("请输入待编码字符：");
    getchar();
    for(int i=0;i<n0;i++)
    {
        scanf("%c",&ht[i].data);
    }
    getchar();
    printf("请输入相应的权值：");
    for( int i=0;i<n0;i++)
    {
        scanf("%lf",&ht[i].weight);
    }
    createHT( ht, n0);

    //对字符进行哈夫曼编码并输出
    int L[n0];
    HCode hcd[n0];
    createHCode(ht, hcd, n0,L);
    printf("\n输出哈夫曼编码：\n");
    for(int i=0;i<n0;i++)
    {
        printf("%c:\t",ht[i].data);
        for(int j=hcd[i].start;j<=n0;j++)      //输出哈夫曼码
        {
            printf("%c",hcd[i].cd[j]);
        }
        printf("\t length:%d\n",L[i]);
    }

    double WPL;            //WAP表示带权路径长度
    for (int i;i<n0;i++)
    {
        WPL += ht[i].weight*L[i];
    }
    printf("WPL:%lf",WPL);
}


运行如下



另外注意一点，我把权值定义了double型，但之前scanf输入时使用的确是%f,结果出现了乱码，后来改成了%lf。

看了下别人的博客，因为float和double的关系不像int和long的关系那样，简单的在后面增加4字节的位置。float和double有自己专门的数据排列格式，如下：



附上链接
感谢这位博主，关于哈夫曼树的构造原理这篇博客讲的很形象

 哈夫曼树的创建：给n个叶子节点及权值，把n个叶子节点看成n个树，由他们组成了森林，每次在森林中找到最小的两个节点，把他们作为新树的左子树右子树，并把这两个节点从森林中删除，把新树节点加进森林，重复操作直到森林中剩余一个或更少的节点；

哈夫曼树编码：从根节点开始，按左子树为'0',右子树为'1'编码，最后找到叶子节点的编码

#include <stdio.h>   
#include <malloc.h>  
#include <conio.h>   
#include <string.h>  
#include <iostream>  
using namespace std;  
  
#define MAX_LENGTH 100//叶子节点的最大数量   
typedef char **HuffmanCode;  
  
typedef struct HTNode{  
    unsigned int weight;//该节点所占的权重   
    unsigned int parent,lchild,rchild;// 该节点的父节点，左孩子，右孩子   
    HTNode(unsigned int a,unsigned int b,unsigned int c,unsigned int d){  
        weight=a,parent=b,lchild=c,rchild=d;  
    }  
}HTNode,*HuffmanTree;  
  
void Select(HuffmanTree HT,int i,int &s1,int &s2){//把没有父节点的所有节点中最小的两个值赋值给s1，s2   
    int j,k = 1;  
    while(HT[k].parent) //找最小的父节点为0，即没有父节点的点   
        k++;  
    s1 = k;  
    for(j = 1;j <= i;j++)  
        if(!HT[j].parent && HT[j].weight<HT[s1].weight)//找父节点为0的所有节点中的最小值，赋给s1     
            s1 = j;  
    k = 1;  
    while(HT[k].parent || k==s1)//找最小的父节点为0，即没有父节点的点，且不等于s1   
        k++;  
    s2 = k;  
    for(j = 1;j <= i;j++)  
        if(!HT[j].parent && HT[j].weight<HT[s2].weight && j!=s1)//找父节点为0的所有节点中的不为s1的最小值，赋给s2   
            s2 = j;  
}  
  
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){//创建哈夫曼树   
    if(n<=1) return;//只有一个节点，直接作为根节点返回，其他情况直接返回   
    int m,i,s1,s2,start,c,f;  
    HuffmanTree p;  
    m = 2*n-1;//哈夫曼树的总节点数量   
    for(p = HT+1,i=1;i<=n;i++,p++,w++){//给前n个节点赋值   
        *p=HTNode(*w,0,0,0);  
        cout<<endl<<"HT["<<i<<"].weight="<<p->weight<<"  ";//输出每个节点的权值   
    }  
    for(;i<=m;i++,p++)  
        *p=HTNode(0,0,0,0);//给后面m-n个节点赋值   
    cout<<endl<<endl<<"HuffmanTree is created in following order :";  
    for(i = n+1;i<=m;i++){  
        Select(HT,i-1,s1,s2);//每次选择节点中最小的两个节点作为新树的左子树，右子树；  
        // 把s1，s2作为节点i的左子树，右子树，  
        HT[s1].parent = i,HT[s2].parent = i;//给s1，s2的父节点赋值    
        HT[i].weight=HT[s1].weight+HT[s2].weight;//计算节点i的权重   
        cout<<endl<<"HT["<<s1<<"] and HT[" <<s2<<"] create";  
        cout<<" HT["<<i<<"], weight="<<HT[i].weight;  
    }  
    //从叶子结点到根结点逆向求每个字符的哈夫曼编码  
    HC = (HuffmanCode)malloc((n+1)*sizeof(char *));//为数组HC开辟空间  
    char cd[MAX_LENGTH];    
    cd[n-1]=0;//编码结束符'\0'的ascii码为0   
    cout<<endl<<endl<<"HuffmanTree Code is as follows :"<<endl;  
    for(i=1;i<=n;i++){//逐个字符求哈夫曼编码  
        start = n-1;//指向编码结束的位置   
        //每个节点的左子树编码为'0',右子树编码为'1', 按从根节点往下的顺序构造出叶子节点的编码   
        for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)//从叶子节点一直找到根节点   
            if(HT[f].lchild==c) cd[--start]='0';//若为左子树，编码位置编为'0'   
            else cd[--start]='1';//若为右子树，编码位置编为'1'   
        HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间，n-start为第i个字符的编码长。   
        strcpy(HC[i],&cd[start]);//从cd复制编码（串）到HC   
        printf("\nHT[%d] node 's  Huffman code is: %s",i,HC[i]);  
    }         
}  
  
int main()  
{  
    HuffmanTree HT;  
    HuffmanCode HC;  
    int n,i;  
    int *w,W[MAX_LENGTH];//W保存叶子节点的权值   
    cout<<endl<<endl<<"HuffmanCoding.cpp";  
    cout<<endl<<"============="<<endl;  
    cout<<endl<<"Please input the number of the element of HuffmanTree (eg.5):";  
    cin>>n;//输入叶子节点的数量   
    for(i = 0;i < n;i++){  
        cout<<"Please input the weight of the "<<i+1<<"th element (eg.8):";  
        cin>>W[i];//输入每个叶子节点的权值   
    }  
    w = W;  
    HuffmanCoding(HT,HC,w,n);//创建n个叶子节点构成的哈夫曼树   
    cout<<endl<<endl<<"...OK!...";//创建成功   
    getch();  
    return 0;  
} 

 

                                                                       哈夫曼树的创建和编码
   
       项目忙的要死，博客停了两天，做外包的真不好受，还是做产品的强。软件最后最值钱的不是代码，而是相关的文档，文档清楚，依葫芦画瓢照做出来应该不难。项目结束了至少要整理出需求规格说明书，系统设计文档，用户使用说明书，开发进度表，投标书，工作说明书等文档。
      本文根据《数据结构与算法》(C语言版)(第三版) 整理。

      本博文作为学习资料，源代码是VC++ 6.0上可执行程序，我挪到了VS2010中执行。

       1.哈夫曼树又称最优二叉树，是一类带权路径长度最短的树。
       对于最优二叉树，权值越大的结点越接近树的根结点，权值越小的结点越远离树的根结点。

       最优二叉树的构造算法步骤：

       (1)根据给定的n个权值w1,w2,...,wn构成n棵二叉树森林F={T1,T2,...,Tn}，其中每一棵二叉树Ti中都只有一个权为wi的根结点，其左、右子树为空。

       (2)在森林F中选出两棵根结点权值最小的树作为一棵新二叉树的左、右子树，新二叉树的根结点的权值为其左、右子树根结点的权值之和。

       (3)从F中删除这两棵二叉树，同时把新二叉树加入到F中。

       (4)重复步骤(2)、(3),直到F中只含有一棵树为止，此树便为最优二叉树。

       哈夫曼树的构造过程示意图如下：
                                                
       哈夫曼树的结点类型声明：
    struct TreeNode
    {
       int weight;
       int parent;
       int lchild;
       int rchild;
    };
    typedef struct TreeNode HFTreeNode;
    typedef HFTreeNode HuffmanTree;

        哈夫曼树的构造算法：
     #define MaxSize 1000     //叶子数目
     void Select(HuffmanTree *HT, int g, int &s1, int &s2);
     void CreateHuffmanTree(HuffmanTree T[MaxSize], int n)
     {
         int i,p1,p2;
         if(n<1)
           return 1;
         m=2*n;        //计算哈夫曼树的结点大小
         for(i=1; i<m; i++)
         {
            T[i].parent=0;
            T[i].lchild=0;
            T[i].rchild=0;
            T[i].weight=0;
         }

         for(i=1; i<n; i++)     //读入叶子结点的权值
         {
           scanf("%d",&weight);
           T[i].weight=weight;
          }

         for(i=n; i<m-1; i++)
         {
            SelectMin(T, i-1, p1, p2);
            //在T[0...i-1]中选择两个权值最小的根结点，其序号分别为p1和p2
            T[p1].parent=T[p2].parent=i;
            T[i].lchild=p1;      //最小权的根结点是新结点的左孩子
            T[i].rchild=p2;      //次小权的根结点是新结点的右孩子
            T[i].weight=T[p1].weight+T[p2].weight;
        }
    }

    void selectMin(HuffmanTree *HT, int g, int &s1, int &s2)
    {
       int j, k, m, n;
       for(k=1; k<=g; k++)     //找到一个parent为-1的子树
       {
          if(HT[k].parent==0)
          {
            s1=k;
            break;
           }
       }

       for(j=1; j<=g; j++)
       {
          if((HT[j].weight<=HT[k].weight)&&(HT[j].parent==0))
          //找到一个parent为-1权值最小的子树
          s1=j;
       }

       for(m=1; m<=g; m++)
       {
          if((HT[m].parent==0)&&(m!=s1))
          {
            s2=m;
            break;
           }
       }

       for(n=1; n<=g; n++)
       {
         if((HT[n].weight<HT[m].weight)&&(HT[n].parent==0)&&(n!=s1))
           s2=n;
       }
   }
      2.哈夫曼编码
       哈夫曼编码是一种变长编码。其定义如下：

       对于给定的字符集D={d1,d2,...,dn}及其频率分布F={w1,w2,...,wn}，用d1,d2,...,dn作为叶结点，w1,w2,...,wn作为结点的权，利用哈夫曼算法构造一棵最优二叉树，将树中每个分支结点的左分支标上"0"；右分支标上"1"，把从根到每个叶子的路径符号("0"或"1")连接起来，作为该叶子的编码。

       哈夫曼编码是在哈夫曼树的基础上求出来的，其基本思想是：从叶子结点di(0<=i<n)出发，向上回溯至根结点，依次求出每个字符的编码。
       示例：对于字符集D={A，B，C，D}，其频率(单位：千次)分布为F={12，6，2，18}，下图给出D的哈夫曼编码图。
                                    
       哈夫曼编码的回溯步骤如下：

       (1)选出哈夫曼树的某一个叶子结点。

       (2)利用其双亲指针parent找到其双亲结点。

       (3)利用找到的双亲结点的指针域中的lchild和rchild，判断该结点是双亲的左孩子还是右孩子。若该结点是其双亲结点的左孩子，则生成代码0；若该结点是其双亲结点的右孩子，则生成代码1。

       (4)由于生成的编码与要求的编码反序，将所生成的编码反序。

       (5)重复步骤(1)~(4)，直到所有结点都回溯完。

       反序方法：首先将生成的编码从后向前依次存放在一个临时的一维数组中，并设一个指针start指示编码在该一维数组中的起始位置。当某个叶子结点的编码完成时，从临时的一维数组的start处将编码复制到该字符对应的bits中即可。
       哈夫曼编码的存储结构：

    struct CodeNode
    {
       char ch;           //存储字符
       char bits[n+1];    //存放编码位串
    };
    typedef struct CodeNode CodeNoe;
    typedef CodeNoe HUffmanCode[n]; 
       哈夫曼编码的算法：
     void CharSetHuffmanEncoding(HuffmanTree T, HuffmanCode H)
     {   //根据哈夫曼树T求哈夫曼编码表H
        int c, p, i;
        char cd[n+1];
        int start;
        cd[n]='\0';
        for(i=0; i<n; i++)
        {
          //依次求叶子T[i]的编码
          H[i].ch=getchar();      //读入叶子T[i]对应的字符
          start=n;                //编码起始位置的初值
          c=i;                    //从叶子T[i]开始上溯
          while(p=T[c].parent>0)
          {
             if(T[p].lchild==c)
             {
                cd[--start]='0';
             }
             else
             {
                cd[--start]='1';
              }
             c=p;      //继续上溯
          }
          strcpy(H[i].bits, &cd[start]);      //复制编码位串
       }
    }  
      3. 哈夫曼解码
         哈夫曼解码过程:从哈夫曼树的根结点出发，依次识别电文的中的二进制编码，如果为0，则走向左孩子，否则走向右孩子，走到叶结点时，就可以得到相应的解码字符。

        算法如下：
    void CharSetHuffmanDecoding(HuffmanTree T, char* cd, int n)
      {
           int p=2*n-2;      //从根结点开始
           int i=0;
           //当要解码的字符串没有结束时
           while(cd[i]!='/0')
           {
                //当还没有到达哈夫曼树的叶子并且要解码的字符串没有结束时
               while((T[p].lchild!=0 && T[p].rchild != 0) && cd[i] != '\0')
                {
                     if(cd[i] == '0')
                     {
                        //如果是0，则叶子在左子树
                        p=T[p].lchild;
                     }
                     else
                     {
                        //如果是1，则叶子在左子树
                        p=T[p].rchild;
                     }
                     i++;
          }
          //如果到达哈夫曼树的叶子时
           if(T[p].lchild == 0 && T[p].rchild == 0)
           {
               printf("%c", T[p].ch);
               p = 2*n-1;
            }
           else      //如果编号为p的结点不是叶子，那么编码有错
            {
                 printf("\n解码出错! \n");
                return;
             }
       }
        printf("\n");
    }
    4. 哈夫曼树的创建和哈夫曼编码程序：
    在VS2010中新建Win32 控制台应用程序的项目：HuffmanTree，创建结果如下图：


       
// HuffmanTree.cpp : 定义控制台应用程序的入口点。

 #include "stdafx.h"
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>

 typedef struct HuffmanTree
 {
   int weight;
   int parent, lchild, rchild;
 } HuffmanTree;

 typedef struct CodeNode
 {
   int ch;
   char bits[4+1];
 }CodeNode;

 void SelectMin(HuffmanTree tree[], int len, int * pos1, int* pos2)
 {
   int min=255;
   int i, j;
   *pos1=0;
   *pos2=0;
   for(i=0; i<len; i++)
   {
     if(tree[i].parent==-1)
       if(min>tree[i].weight)
       {
         min=tree[i].weight;
         *pos1=i;
       }
   }
   min=255;

   for(j=0; j<len; j++)
   {
     if(j==*pos1)
       continue;
     if(tree[j].parent==-1)
       if(min>tree[j].weight)
       {
         min=tree[j].weight;
         *pos2=j;
       }
   }
 }

 void CreateHuffmanTree(HuffmanTree tree[], int n)
 {
   int m=2*n;
   int i;
   for(i=n; i<m-1; i++)
   {
     int pos1, pos2;
     HuffmanTree node;
     SelectMin(tree, i, &pos1, &pos2);
     printf("pos1=%d,pos2=%d\n", pos1, pos2);
     node.weight=tree[pos1].weight+tree[pos2].weight;
     tree[pos1].parent=i;
     tree[pos2].parent=i;
     node.lchild=pos1;
     node.rchild=pos2;
     node.parent=-1;
     tree[i]=node;
   }
 }

 void HuffmanEncoding(HuffmanTree tree[])
 {
   int c, p, i;
   int start;
   char cd[4+1];
   cd[4]='\0';

   for(i=0; i<4; i++)
   {
     printf("\n");
     printf("%d",tree[i].weight);
     printf(":");
     start=4;
     c=i;
     while((p=tree[c].parent)!=-1)
     {
       if(tree[p].lchild==c)
       {
         cd[--start]='0';
       }
       else
       {
         cd[--start]='1';
       }
       c=p;
     }
     printf(&cd[start]);
   }
 }

 int main(int argc, char* argv[])
 {
   HuffmanTree tree[4*2];
   int i, j;
   for(i=0; i<4; i++)
   {
     tree[i].lchild=-1;
     tree[i].rchild=-1;
	 tree[i].parent=-1;
   }

   printf("请输入哈夫曼树叶子结点的权值: \n");
   for(i=0; i<4; i++)     //读入叶子结点的权值
   {
     int weight;
     scanf("%d",&weight);
     tree[i].weight=weight;
   }

   CreateHuffmanTree(tree, 4);
   for(j=0; j<2*4-1; j++)
   {
      printf("tree[%d]:weight=%d \n", j, tree[j].weight);
   }

   HuffmanEncoding(tree);
   
   return 0;
 }
    Ctrl+F5执行HuffmanTree.cpp结果如下图：