主要内容 #

1. 哈夫曼树的定义
2. 哈夫曼树的构造
3. 哈夫曼树的构造代码

1. 哈夫曼树的定义 #

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

简而言之，就是按照一个贪心思想和规则进行树的构造，而构造出来的这个树的权值最小！
其中WPL表示计算出的权值。至于为什么按照哈夫曼树方法构造得到的权重最小。这里不进行证明。对于哈夫曼树，他的每个非叶子节点都有两个孩子因为哈夫曼树的构造就是自底向上的构造，两两合并。
WPL计算方法:
WPL=求和(wi·li)其中wi是第i个节点的权值(value)。li是第i个节点的长(深)度。

2. 哈夫曼树的构造 #

初始时候各个数直都是一个单节点二叉树！然后进行排序。

放入优先队列(自己排序也行)每次取两个最小权值顶点，构造父节点(value=left.value+right.value)。
1. 如果队列为空，那么返回节点，并且这个节点为根节点root。

否则继续加入队列进行排序。重复上述操作，直到队列为空。

在计算带权路径长度的时候，需要重新计算树的高度(从下往上)，因为哈夫曼树是从下往上构造的，所以对于高度不太好维护，可以构造好然后计算高度。
比如图1的WPL为：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61。

3. 哈夫曼树的构造代码 #

哈夫曼树构造的参考代码：

typedef struct HNode {
  int weight;
  HNode *lchild, *rchild;
} * Htree;

Htree createHuffmanTree(int arr[], int n) {
  Htree forest[N];
  Htree root = NULL;
  for (int i = 0; i < n; i++) {  // 将所有点存入森林
    Htree temp;
    temp = (Htree)malloc(sizeof(HNode));
    temp->weight = arr[i];
    temp->lchild = temp->rchild = NULL;
    forest[i] = temp;
  }

  for (int i = 1; i < n; i++) {  // n-1 次循环建哈夫曼树
    int minn = -1, minnSub;  // minn 为最小值树根下标，minnsub 为次小值树根下标
    for (int j = 0; j < n; j++) {
      if (forest[j] != NULL && minn == -1) {
        minn = j;
        continue;
      }
      if (forest[j] != NULL) {
        minnSub = j;
        break;
      }
    }

    for (int j = minnSub; j < n; j++) {  // 根据 minn 与 minnSub 赋值
      if (forest[j] != NULL) {
        if (forest[j]->weight < forest[minn]->weight) {
          minnSub = minn;
          minn = j;
        } else if (forest[j]->weight < forest[minnSub]->weight) {
          minnSub = j;
        }
      }
    }

    // 建新树
    root = (Htree)malloc(sizeof(HNode));
    root->weight = forest[minn]->weight + forest[minnSub]->weight;
    root->lchild = forest[minn];
    root->rchild = forest[minnSub];

    forest[minn] = root;     // 指向新树的指针赋给 minn 位置
    forest[minnSub] = NULL;  // minnSub 位置为空
  }
  return root;
}