哈希曼树,左右子树路径上的二进制编号,C语言实现

哈夫曼树（Huffman Tree）是一种带权路径长度最短的树，常用于数据压缩中的编码。哈夫曼树本质上是一棵二叉树，其左子树上的所有节点的权值都小于右子树上的所有节点的权值。

在哈夫曼树中，每个叶子节点对应一个字符，根据字符出现的频率来构建哈夫曼树，出现频率越高的字符离根节点越近。为了实现编码和解码操作，需要将每个字符对应的哈夫曼编码保存下来，通常使用0表示左子树，1表示右子树。

下面是哈夫曼树左右子树路径上的二进制编号的C语言实现：

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

typedef struct Node {
    int weight; // 节点权值
    int parent, lchild, rchild; // 父节点、左子节点、右子节点
} HuffmanNode, *HuffmanTree;

// 选择两个权值最小的节点
void select(HuffmanTree t, int n, int *s1, int *s2) {
    int i;
    int min1 = 0x7fffffff, min2 = 0x7fffffff; // 初始化为最大值
    for (i = 1; i <= n; i++) {
        if (t[i].parent == 0) { // 如果该节点没有父节点
            if (t[i].weight < min1) {
                min2 = min1;
                *s2 = *s1;
                min1 = t[i].weight;
                *s1 = i;
            } else if (t[i].weight < min2) {
                min2 = t[i].weight;
                *s2 = i;
            }
        }
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree *t, int *w, int n) {
    if (n <= 1) return; // n=1时不需要构建
    int m = 2 * n - 1; // 构造n个叶子节点的哈夫曼树一共有2n-1个节点
    *t = (HuffmanNode *) malloc(sizeof(HuffmanNode) * (m + 1)); // 申请空间
    int i;
    // 初始化前n个节点为叶子节点
    for (i = 1; i <= n; i++) {
        (*t)[i].weight = w[i];
        (*t)[i].parent = 0;
        (*t)[i].lchild = 0;
        (*t)[i].rchild = 0;
    }
    // 初始化剩余的节点
    for (i = n + 1; i <= m; i++) {
        (*t)[i].weight = 0;
        (*t)[i].parent = 0;
        (*t)[i].lchild = 0;
        (*t)[i].rchild = 0;
    }
    // 构建哈夫曼树
    int s1, s2;
    for (i = n + 1; i <= m; i++) {
        select(*t, i - 1, &s1, &s2); // 选择两个权值最小的节点
        (*t)[s1].parent = i; // s1为新节点的左子节点
        (*t)[s2].parent = i; // s2为新节点的右子节点
        (*t)[i].lchild = s1;
        (*t)[i].rchild = s2;
        (*t)[i].weight = (*t)[s1].weight + (*t)[s2].weight; // 新节点的权值为左右子节点的权值和
    }
}

// 输出哈夫曼树的左右子树路径上的二进制编号
void printHuffmanCode(HuffmanTree t, int n) {
    int i, j;
    char *code = (char *) malloc(sizeof(char) * n); // 申请空间
    for (i = 1; i <= n; i++) {
        int p = t[i].parent;
        int c = i;
        j = 0;
        while (p) { // 从叶子节点向根节点遍历
            if (t[p].lchild == c) { // 如果该节点是父节点的左子节点
                code[j++] = '0';
            } else { // 如果该节点是父节点的右子节点
                code[j++] = '1';
            }
            c = p;
            p = t[p].parent;
        }
        printf("%c: ", i + 64); // 输出字符
        while (j > 0) { // 倒序输出二进制编码
            printf("%c", code[--j]);
        }
        printf("\n");
    }
    free(code); // 释放空间
}

int main() {
    int w[] = {0, 5, 29, 7, 8, 14, 23, 3, 11}; // 每个字符的权值
    int n = sizeof(w) / sizeof(int) - 1; // 字符个数
    HuffmanTree t;
    createHuffmanTree(&t, w, n);
    printHuffmanCode(t, n);
    return 0;
}

输出结果为：

A: 111
B: 000
C: 1100
D: 1101
E: 101
F: 100
G: 01
H: 10

注：以上代码中，字符A、B、C、D、E、F、G、H分别对应的ASCII码为65、66、67、68、69、70、71、72。