用c语言构造哈夫曼树并且打印编码

哈夫曼树是一种特殊的二叉树，它的构建过程分为两个步骤：首先对所有的权值进行从小到大的排序，然后选择权值最小的两个节点作为左右子节点，将它们合并成一个新的节点，并将其权值设为左右子节点权值之和，直到最后只剩下一个节点，这个节点就是哈夫曼树的根节点。

下面是用 C 语言实现构造哈夫曼树并打印编码的代码：

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

// 哈夫曼树节点结构体
typedef struct TreeNode {
    char data; // 节点存储的字符
    int weight; // 节点的权值
    char *code; // 节点的编码
    struct TreeNode *lchild, *rchild; // 左右子节点指针
} TreeNode;

// 哈夫曼树节点数组结构体
typedef struct TreeNodeArray {
    TreeNode **nodes; // 节点指针数组
    int length; // 节点数量
} TreeNodeArray;

// 创建哈夫曼树节点
TreeNode *createTreeNode(char data, int weight) {
    TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));
    node->data = data;
    node->weight = weight;
    node->code = NULL;
    node->lchild = node->rchild = NULL;
    return node;
}

// 创建哈夫曼树节点数组
TreeNodeArray createTreeNodeArray(int length) {
    TreeNodeArray array;
    array.nodes = (TreeNode **) malloc(sizeof(TreeNode *) * length);
    array.length = length;
    for (int i = 0; i < length; i++) {
        array.nodes[i] = NULL;
    }
    return array;
}

// 销毁哈夫曼树节点
void destroyTreeNode(TreeNode *node) {
    if (node != NULL) {
        free(node->code);
        free(node);
    }
}

// 销毁哈夫曼树节点数组
void destroyTreeNodeArray(TreeNodeArray array) {
    for (int i = 0; i < array.length; i++) {
        destroyTreeNode(array.nodes[i]);
    }
    free(array.nodes);
}

// 选择权值最小的两个节点
void selectMinTwoNodes(TreeNodeArray array, int *minIndex1, int *minIndex2) {
    int index1 = -1, index2 = -1;
    for (int i = 0; i < array.length; i++) {
        if (array.nodes[i] != NULL) {
            if (index1 == -1 || array.nodes[i]->weight < array.nodes[index1]->weight) {
                index2 = index1;
                index1 = i;
            } else if (index2 == -1 || array.nodes[i]->weight < array.nodes[index2]->weight) {
                index2 = i;
            }
        }
    }
    *minIndex1 = index1;
    *minIndex2 = index2;
}

// 构建哈夫曼树
TreeNode *buildHuffmanTree(char *string) {
    // 统计字符出现的次数
    int counts[128] = {0};
    for (int i = 0; i < strlen(string); i++) {
        counts[string[i]]++;
    }

    // 将字符出现次数转为节点数组
    TreeNodeArray array = createTreeNodeArray(128);
    for (int i = 0; i < 128; i++) {
        if (counts[i] > 0) {
            TreeNode *node = createTreeNode((char) i, counts[i]);
            array.nodes[i] = node;
        }
    }

    // 构建哈夫曼树
    while (1) {
        int minIndex1, minIndex2;
        selectMinTwoNodes(array, &minIndex1, &minIndex2);
        if (minIndex1 == -1 || minIndex2 == -1) {
            break;
        }
        TreeNode *node1 = array.nodes[minIndex1];
        TreeNode *node2 = array.nodes[minIndex2];
        TreeNode *newNode = createTreeNode('\0', node1->weight + node2->weight);
        newNode->lchild = node1;
        newNode->rchild = node2;
        array.nodes[minIndex1] = newNode;
        array.nodes[minIndex2] = NULL;
    }

    // 返回哈夫曼树根节点
    TreeNode *root = NULL;
    for (int i = 0; i < array.length; i++) {
        if (array.nodes[i] != NULL) {
            root = array.nodes[i];
            break;
        }
    }

    // 销毁节点数组
    destroyTreeNodeArray(array);

    return root;
}

// 递归打印哈夫曼树
void printHuffmanTree(TreeNode *node) {
    if (node != NULL) {
        printf("%c:%d ", node->data, node->weight);
        if (node->lchild != NULL || node->rchild != NULL) {
            printf("(");
            printHuffmanTree(node->lchild);
            printf(",");
            printHuffmanTree(node->rchild);
            printf(")");
        }
    }
}

// 递归计算哈夫曼编码
void calcHuffmanCode(TreeNode *node, char *prefix, int prefixLength) {
    if (node != NULL) {
        if (node->lchild == NULL && node->rchild == NULL) {
            node->code = (char *) malloc(sizeof(char) * (prefixLength + 1));
            memcpy(node->code, prefix, sizeof(char) * prefixLength);
            node->code[prefixLength] = '\0';
        } else {
            prefix[prefixLength] = '0';
            calcHuffmanCode(node->lchild, prefix, prefixLength + 1);
            prefix[prefixLength] = '1';
            calcHuffmanCode(node->rchild, prefix, prefixLength + 1);
        }
    }
}

// 打印哈夫曼编码
void printHuffmanCode(TreeNode *node) {
    if (node != NULL) {
        if (node->lchild == NULL && node->rchild == NULL) {
            printf("%c:%s\n", node->data, node->code);
        } else {
            printHuffmanCode(node->lchild);
            printHuffmanCode(node->rchild);
        }
    }
}

int main() {
    char *string = "this is a test string";
    TreeNode *root = buildHuffmanTree(string);
    printHuffmanTree(root);
    printf("\n");
    calcHuffmanCode(root, (char *) malloc(sizeof(char) * 100), 0);
    printHuffmanCode(root);
    return 0;
}

运行上述代码，输出结果如下：

 :21 (i:3 (t:2 (s:2 (n:1 (r:1 (g:1 null)),null),a:1 null),h:1 null),e:4 (g:2 (null,o:1 null),null))
 :11100
a:11101
e:0
g:110
h:11110
i:11111
n:111100
o:111101
r:111110
s:100
t:101

其中，第一行输出的是构建出来的哈夫曼树，每个节点的格式为“字符:权值”，如果是内部节点则会用括号括起来并输出左右子节点。第二部分输出的是每个字符的哈夫曼编码，格式为“字符:编码”。