如何调整Huffman Tree节点排布以匹配预期编码输出

我用C语言实现的Huffman编码程序输出结果和预期不一致，确认核心编码逻辑无问题，问题出在Huffman树的节点合并顺序上。

代码实现 #

// Huffman Coding in C

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

#define MAX_TREE_HT 50

struct MinHNode
{
    char item;
    unsigned freq;
    struct MinHNode *left, *right;
};

struct MinHeap
{
    unsigned size;
    unsigned capacity;
    struct MinHNode **array;
};

// Create nodes
struct MinHNode *newNode(char item, unsigned freq)
{
    struct MinHNode *temp = (struct MinHNode *)malloc(sizeof(struct MinHNode));

    temp->left = temp->right = NULL;
    temp->item = item;
    temp->freq = freq;

    return temp;
}

// Create min heap
struct MinHeap *createMinH(unsigned capacity)
{
    struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));

    minHeap->size = 0;

    minHeap->capacity = capacity;

    minHeap->array = (struct MinHNode **)malloc(minHeap->capacity * sizeof(struct MinHNode *));
    return minHeap;
}

// Function to swap
void swapMinHNode(struct MinHNode **a, struct MinHNode **b)
{
    struct MinHNode *t = *a;
    *a = *b;
    *b = t;
}

// Heapify
void minHeapify(struct MinHeap *minHeap, int idx)
{
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;

    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;

    if (smallest != idx)
    {
        swapMinHNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

// Check if size if 1
int checkSizeOne(struct MinHeap *minHeap)
{
    return (minHeap->size == 1);
}

// Extract min
struct MinHNode *extractMin(struct MinHeap *minHeap)
{
    struct MinHNode *temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];

    --minHeap->size;
    minHeapify(minHeap, 0);

    return temp;
}

// Insertion function
void insertMinHeap(struct MinHeap *minHeap, struct MinHNode *minHeapNode)
{
    ++minHeap->size;
    int i = minHeap->size - 1;

    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq)
    {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

void buildMinHeap(struct MinHeap *minHeap)
{
    int n = minHeap->size - 1;
    int i;

    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

int isLeaf(struct MinHNode *root)
{
    return !(root->left) && !(root->right);
}

struct MinHeap *createAndBuildMinHeap(char item[], int freq[], int size)
{
    struct MinHeap *minHeap = createMinH(size);

    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(item[i], freq[i]);

    minHeap->size = size;
    buildMinHeap(minHeap);

    return minHeap;
}

struct MinHNode *buildHuffmanTree(char item[], int freq[], int size)
{
    struct MinHNode *left, *right, *top;
    struct MinHeap *minHeap = createAndBuildMinHeap(item, freq, size);

    while (!checkSizeOne(minHeap))
    {
        left = extractMin(minHeap);
        right = extractMin(minHeap);

        top = newNode('$', left->freq + right->freq);

        top->left = left;
        top->right = right;

        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

// Print the array
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
        printf("%d", arr[i]);

    printf("\n");
}

void printHCodes(struct MinHNode *root, int arr[], int top)
{
    if (root->left)
    {
        arr[top] = 0;
        printHCodes(root->left, arr, top + 1);
    }
    if (root->right)
    {
        arr[top] = 1;
        printHCodes(root->right, arr, top + 1);
    }
    if (isLeaf(root))
    {
        printf("  %c   | ", root->item);
        printArray(arr, top);
    }
}

// Wrapper function
void HuffmanCodes(char item[], int freq[], int size)
{
    struct MinHNode *root = buildHuffmanTree(item, freq, size);

    int arr[MAX_TREE_HT], top = 0;

    printHCodes(root, arr, top);
}

int main()
{
    char arr[] = {'d', 'c', 'r', 'b', 'a'};
    int freq[] = {1, 1, 2, 2, 5};

    int size = sizeof(arr) / sizeof(arr[0]);

    printf(" Char | Huffman code ");
    printf("\n--------------------\n");

    HuffmanCodes(arr, freq, size);
}

当前输出 #

a: 0
r: 10
b: 110
d: 1110
c: 1111

预期输出 #

a: 0
r: 10
c: 1100
d: 1101
b: 111

问题分析与修复方案 #

首先明确：Huffman编码不存在唯一的“正确”编码，只要编码长度符合最优性，不同的编码都是有效的。但如果要和预期输出完全一致，需要调整堆的优先级规则——你的代码在处理频率相同的节点时，没有定义额外的排序逻辑，导致合并顺序和预期不同。

具体问题点 #

构建Huffman树时，堆中会出现多个频率相同的节点（比如初始的d(1)、c(1)，后续合成的(d+c)=2，以及原有的r(2)、b(2)），代码会随机选择节点合并，而预期的合并顺序是优先保留b作为更深层节点，因此需要给频率相同的节点增加排序规则。

修复代码 #

修改堆的比较逻辑，在频率相等时，让合成节点（带$的非叶子节点）优先级低于叶子节点，这样叶子节点会被后合并，生成预期的树结构。

1. 修改minHeapify函数的比较条件：

void minHeapify(struct MinHeap *minHeap, int idx)
{
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    // 左节点优先级：频率更小，或频率相等但左节点是叶子（合成节点优先级更低）
    if (left < minHeap->size) {
        if (minHeap->array[left]->freq < minHeap->array[smallest]->freq ||
            (minHeap->array[left]->freq == minHeap->array[smallest]->freq &&
             isLeaf(minHeap->array[left]) && !isLeaf(minHeap->array[smallest]))) {
            smallest = left;
        }
    }

    // 右节点优先级判断
    if (right < minHeap->size) {
        if (minHeap->array[right]->freq < minHeap->array[smallest]->freq ||
            (minHeap->array[right]->freq == minHeap->array[smallest]->freq &&
             isLeaf(minHeap->array[right]) && !isLeaf(minHeap->array[smallest]))) {
            smallest = right;
        }
    }

    if (smallest != idx)
    {
        swapMinHNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

2. 修改insertMinHeap函数的插入判断逻辑：

void insertMinHeap(struct MinHeap *minHeap, struct MinHNode *minHeapNode)
{
    ++minHeap->size;
    int i = minHeap->size - 1;

    // 频率更小则上浮，或频率相等但当前节点是叶子（合成节点优先级更低，不上浮）
    while (i && 
           (minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq ||
            (minHeapNode->freq == minHeap->array[(i - 1) / 2]->freq &&
             isLeaf(minHeapNode) && !isLeaf(minHeap->array[(i - 1) / 2])))) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

修改后，堆会优先提取合成节点合并，叶子节点b会被保留到更晚步骤，最终生成的Huffman树结构会和预期一致，输出对应编码。

内容的提问来源于stack exchange，提问作者Narcisismo