书上二叉树后面就到哈夫曼树了，过一阵就要整这个的实验课了，趁着这次机会赶快自学下，不知道写的如何，希望大家多多指正吧。

哈夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

基本术语

哈夫曼树又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
哈夫曼树
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL

构造

典型的贪心算法
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

（百度图片真香）
对于有n个叶子结点的哈夫曼树，结点总数为2n+1，即可将叶子结点集中到前面1到n个位置，后面n-1个位置存储其余非叶子结点。

我们可以用一个静态三叉链表来存储。
注意注意！！函数使用时最好不要用地址传，直接引入就好，不然会出错，最好不用***
**其实如稀疏矩阵，线性表（数组表示），哈夫曼树，此类有定义实际空间的其实不必要强用地址，反而会出步不要的错。

#include<stdio.h>
#include<stdlib.h>

#define N 30 //叶子结点最大值
#define M 2*N-1 //所有结点最大值

typedef struct{
    int weight;
    int parent;
    int Lchild;
    int Rchild;
    int flag;
}HTNode,HuffmanTree[M+1]; //0号单元不用

主程序如下：

#include<stdio.h>
#include<stdlib.h>

#define N 30 //叶子结点最大值
#define M 2*N-1 //所有结点最大值

typedef struct{
    int weight;
    int parent;
    int Lchild;
    int Rchild;
    int flag;
}HTNode,HuffmanTree[M+1]; //0号单元不用


int select(HuffmanTree ht,int n);
void InitHuffmanTree(HuffmanTree ht,int n);
void crtHuffmanTree(HuffmanTree ht,int n);
void printHuffmanTree(HuffmanTree ht,int n);

void InitHuffmanTree(HuffmanTree ht,int n)//初始哈夫曼树
{
    for(int i=1;i<=n;i++)//初始化叶子节点
    {
        ht[i].Lchild=0;
        ht[i].Rchild=0;
        ht[i].weight=0;
        ht[i].parent=0;
        ht[i].flag=0;
        scanf("%d",&ht[i].weight);
    }
    int m=2*n-1;
    for(int i=n+1;i<=m;i++)//初始化非叶子节点
    {
        ht[i].Lchild=0;
        ht[i].Rchild=0;
        ht[i].weight=0;
        ht[i].parent=0;
         ht[i].flag=0;
    }

}

void crtHuffmanTree(HuffmanTree ht,int n)//构建哈夫曼树
{
   for(int i=n+1;i<=(2*n-1);i++)
   {
       int s1=select(ht,i-1);//注意这里的i-1
       int s2=select(ht,i-1);
       ht[i].weight = ht[s1].weight+ht[s2].weight;
       ht[s1].parent=i;
       ht[s2].parent=i;
       ht[i].Lchild=s1;
       ht[i].Rchild=s2;
   }
}

int select(HuffmanTree ht,int n)//选择最小权值的结点下标
{
    int i,temp,min;
    for(i=1;i<=n;i++)//设置初始下标和权值
    {
        if(ht[i].flag==0)
        {
            temp = ht[i].weight;//初始权值
            min=i;//初始下标
            break;
        }
    }
    for(i=1;i<=n;i++)
    {
        if(ht[i].flag==0&&temp>ht[i].weight)
        {
            temp=ht[i].weight;
            min = i;
        }
    }
    ht[min].flag=1;
    return min;
}

void printHuffmanTree(HuffmanTree ht,int n)//打印哈夫曼树
{   printf("结点  weigh  parent Lchild Rchild\n");
    for(int i=1;i<=n;i++)
    {//\t为补全的意思
        printf("%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].Lchild,ht[i].Rchild);
    }
    printf("\n");
}
int main()
{
    HuffmanTree ht;
    int n;//n为所需的结点数
    printf("输入所需创建的结点数为:");
    scanf("%d",&n);

     InitHuffmanTree(ht,n);//初始化
     printf("初始的哈夫曼树为\n");
     printHuffmanTree(ht,2*n-1);//打印初始的哈夫曼树

     crtHuffmanTree(ht,n);//构建哈夫曼树
     printf("构建后的哈夫曼树为\n");
     printHuffmanTree(ht,2*n-1);//打印构建的哈夫曼树

     return 0;
}

要讲的都在注释里了，就不再多写啦。