JZTXT

31. 哈夫曼树

发布时间 2023-06-15 17:18:31作者: 夏冰翎

一、什么是哈夫曼树

  哈夫曼树（Huffman Tree）也称为 赫夫曼树 或 最优二叉树 。它是 带权路径长度 最小的二叉树。假设二叉树有 n 个叶子结点，每个叶子结点带有权值 \(W_{K}\)，从根节点到每个叶子结点的长度为 \(l_{K}\)，则每个叶子结点的带权路径之和就是：\(WPL=\sum\limits_{k = 1}^{n} w_{k}l_{k}\)。

  假设有五个叶子结点，它们的权值为 {1,2,3,4,5}，用此权值序列可以构造出形状不同的二叉树，它们的 WPL 值也不相同。

img

哈夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近；

二、哈夫曼树的特点

  1. 每个初始节点最终都称为叶节点，且权值越小的节点到根节点的路径长度越大；
  2. 没有度为 1 的结点；
  3. n 个叶子结点的哈夫曼树共有 2n-1 个结点；
  4. 哈夫曼树的任意非叶子结点的左右子树交换后仍是哈夫曼树；
  5. 对同一组权值 \({W_{1},w_{2},……,w_{n}}\)，存在不同构的两颗哈夫曼树；

三、哈夫曼树的构造

  给定 n 个权值分别为 \(w_{1},w_{2},...,w_{n}\) 的节点，构造哈夫曼树的算法描述如下：

  1. 将这 n 个节点分别作为 n 棵仅含一个节点的二叉树，构成森林 F。
  2. 构造一个新节点，从 F 中选取两颗根节点权值最小的树作为新节点的左、右子树，并且将新节点的权值置为左、右子树根节点的权值之和。
  3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
  4. 重复 步骤2 和 步骤3，直至 F 中只剩下一棵树为止。 img

3.1、最小堆的相关操作

  我们可以使用最小堆来帮忙创建哈夫曼树，有关最小堆的操作如下：

3.1.1、最小堆的表示

#define MinData     -9999
#define MinSize     100

typedef struct HeapStruct *MinHeap;
typedef struct HeapStruct *Heap;
typedef struct TreeNode *HuffmanTree;
typedef HuffmanTree Position;
typedef struct TreeNode ElementType;

struct HeapStruct
{
    ElementType *elements;      // 存储堆元素的数组
    int size;                   // 堆的当前元素个数
    int capacity;               // 堆的最大容量
};

struct TreeNode
{
    int weight;
    Position left;
    Position right;
};

3.1.2、最小堆的创建

/**
 * @brief 最小堆的创建
 * 
 * @param maxSize 堆的最大容量
 * @return MinHeap 返回指向最小堆的指针
 */
MinHeap CreateMinHeap(int maxSize)
{
    MinHeap H = malloc(sizeof(struct HeapStruct));
    if(H == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }

    H->elements = calloc((maxSize+1),sizeof(ElementType));
    if(H->elements == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }
  
    H->size = 0;
    H->capacity = maxSize;
    // 定义哨兵为小于堆中所有可能元素的值，便于以后更快操作
    H->elements[0].weight = MinData;
    H->elements[0].left = NULL;
    H->elements[0].right = NULL;

    return H;
}

3.1.3、最小堆的插入

/**
 * @brief 最小堆的插入
 * 
 * @param H 待操作的最小堆
 * @param item 待插入的元素
 */
void Insert(MinHeap H,ElementType *item)
{
    int i;

    if(H->size == H->capacity)
    {
        printf("最小堆已满\n");
        return;
    }

    i = ++H->size;                                              // i指向插入后堆中的最后一个元素的位置
    for(; H->elements[i/2].weight > item->weight; i /= 2)       // 向下过滤结点
    {
        H->elements[i] = H->elements[i/2];
    }
  
    H->elements[i] = *item;                                     // 将item插入
}

3.1.4、最小堆的删除

/**
 * @brief 最小堆的删除
 * 
 * @param H 待操作的最小堆
 * @return ElementType 返回要删除的元素（根节点）
 */
ElementType * DeleteMin(MinHeap H)
{
    int parent,child;
    ElementType *minItem = malloc(sizeof(ElementType));
    ElementType temp;

    if(H->size == 0)
    {
        printf("最小堆已经空了\n");
        return NULL;
    }

    // 取出根结点最小值
    minItem->weight = H->elements[1].weight;
    minItem->left = H->elements[1].left;
    minItem->right = H->elements[1].right;

    temp = H->elements[H->size--];                                          // 用最小堆中最后一个元素从根节点开始向上过滤下层结点
  
    for(parent = 1; parent*2 <= H->size; parent = child)                    // parent*2 <= H->size判别该节点是否有左孩子
    {
        child = parent * 2;                                                 // child指向左孩子
        if((child != H->size) &&                                            // child==H->size意味着左儿子是最后一个元素
            (H->elements[child].weight > H->elements[child+1].weight))      // 如果左孩子比右孩子大
        {
            child++;                                                        // child指向指向右孩子
        }
        if(temp.weight <= H->elements[child].weight)                        // temp元素比左右儿子都小
        {
            break;
        }
        else                                                                // 移动temp元素到下一层
        {
            H->elements[parent] = H->elements[child];                       // 把左右儿子中小的那个拷贝到parent上
        }
    }
    H->elements[parent] = temp;
  
    return minItem;
}

3.1.5、最小堆的建立

/**
 * @brief 将一个堆转换为小顶堆
 *
 * @param Heap 待操作的堆
 */
MinHeap BuildMinHeap(Heap H)
{
    int i = 0, j = 0;
    int temp = 0;

    for(i = H->size/2; i >= 1; i--)
    {
        AdjustHeap(H,i,H->size);
    }

    return H;
}

/**
 * @brief 将以i对应的非叶子节点的树调整为小顶堆
 * 
 * @param array 待调整的数组
 * @param i 表示非叶子节点在数组中的索引
 * @param n 待调整的数据的元素的个数
 */
void AdjustHeap(Heap H,int i,int n)
{
    ElementType temp = H->elements[i];
    int k = 0;
    // k=i*2，k是i节点的左子节点
    for(k = i*2; k <= n; k = k*2)
    {
        if(k+1 <= n && H->elements[k].weight > H->elements[k+1].weight)     // 左子节点的值大于右子节点的值
        {
            k++;                                                            // k指向右子节点
        }
        if(H->elements[k].weight < temp.weight)                             // 如果子节点小于父节点
        {
            H->elements[i] = H->elements[k];                                // 把较大的值赋值给当前节点
            i = k;                                                          // i指向k，继续循环比较
        }
        else
        {
            break;
        }
    }
    // 当for循环结束后，已经将以i为父节点的树的最小值，放在了最顶上，即局部小顶堆
    H->elements[i] = temp;                                                  //将temp放在调整后的位置
}

3.2、构建哈夫曼树

/**
 * @brief 哈夫曼树的构造
 * 
 * @param H 根据结点创建最小堆
 * @return HuffmanTree 返回执行树根的指针
 */
HuffmanTree CreateHuffmanTree(int array[],int length)
{
    // 假设H->size个权值已经存在H->elements[]里
    int i;
    HuffmanTree T;

    MinHeap H = CreateMinHeap(MinSize);
    for(i = 0; i < length; i++)
    {
        H->elements[i+1].weight = array[i];
        H->elements[i+1].left = NULL;
        H->elements[i+1].right = NULL;
        H->size++;
    }

    H = BuildMinHeap(H);                                    // 将H->elements[]按权值调整为最小堆

    while(H->size > 1)                                      // 做H->size-1次合并
    {
        T = malloc(sizeof(ElementType));                    // 建立新节点
        if(T == NULL)
        {
            printf("分配内存失败！\n");
            return NULL;
        }

        T->left = DeleteMin(H);
        T->right = DeleteMin(H);
        T->weight = T->left->weight + T->right->weight;     // 计算新权值

        Insert(H,T);                                        // 将新T插入最小堆
    }

    T = DeleteMin(H);

    return T;
}

整体复杂度为 O(NlogN)