构造哈夫曼树并编码代码c++

构造哈夫曼树是一种经典的树形编码方法，主要用于数据压缩和编码领域。构造哈夫曼树的过程主要分为以下几个步骤：

1. 统计字符出现频率：首先需要统计待编码文本中每个字符出现的频率，可以通过遍历文本字符来实现。将字符频率存储于一个数组或者字典中。

2. 构建哈夫曼树：基于字符频率，可以选择合适的数据结构来存储和构建哈夫曼树。在构建过程中，首先将每个字符频率作为一个独立的叶子节点，然后再通过合并最小频率的节点来构造树。

3. 分配编码：根据构建好的哈夫曼树，给每个字符分配一个唯一的编码。从根节点开始，标记左子树为0，右子树为1，遍历哈夫曼树至叶子节点，即可得到每个字符的编码。为了方便查找和使用编码，可以使用数组或者字典来存储字符和其编码的对应关系。

4. 编写编码代码：根据步骤3中得到的字符和编码的对应关系，编写编码函数来实现文本编码。编码函数接受待编码的文本作为输入，然后将文本中的每个字符替换为其对应的编码。

下面是一个简单的C代码示例来演示哈夫曼树的构建和编码过程：

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

typedef struct Node {
    char character;
    int frequency;
    struct Node* left;
    struct Node* right;
} Node;

// 构建哈夫曼树
Node* buildHuffmanTree(char* characters, int* frequencies, int n) {
    Node** nodes = (Node**)malloc(sizeof(Node*) * n);
    
    for(int i = 0; i < n; i++) {
        nodes[i] = (Node*)malloc(sizeof(Node));
        nodes[i]->character = characters[i];
        nodes[i]->frequency = frequencies[i];
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }
    
    // 构建哈夫曼树
    while(n > 1) {
        Node* min1 = nodes[0];
        int min1Index = 0;
        
        for(int i = 1; i < n; i++) {
            if(nodes[i]->frequency < min1->frequency) {
                min1 = nodes[i];
                min1Index = i;
            }
        }
        
        Node* min2 = nodes[0 == min1Index ? 1 : 0];
        int min2Index = 0 == min1Index ? 1 : 0;
        
        for(int i = 0; i < n; i++) {
            if(i != min1Index && nodes[i]->frequency < min2->frequency) {
                min2 = nodes[i];
                min2Index = i;
            }
        }
        
        Node* parent = (Node*)malloc(sizeof(Node));
        parent->character = '\0';
        parent->frequency = min1->frequency + min2->frequency;
        parent->left = min1;
        parent->right = min2;
        
        nodes[min1Index] = parent;
        
        for(int i = min2Index; i < n - 2; i++) {
            nodes[i] = nodes[i + 1];
        }
        
        nodes[n - 2] = parent;
        
        n--;
    }
    
    return nodes[0];
}

// 分配编码
void assignCode(Node* tree, char** codes, char* code, int depth) {
    if(tree->left == NULL && tree->right == NULL) {
        codes[tree->character] = code;
        return;
    }
    
    code[depth] = '0';
    code[depth + 1] = '\0';
    assignCode(tree->left, codes, code, depth + 1);
    
    code[depth] = '1';
    code[depth + 1] = '\0';
    assignCode(tree->right, codes, code, depth + 1);
}

// 编码函数
char* encodeText(char* text, char** codes) {
    int textSize = strlen(text);
    int totalCodeLength = 0;
    char* encodedText = (char*)malloc(sizeof(char) * (textSize * 8 + 1));
    
    for(int i = 0; i < textSize; i++) {
        char* code = codes[text[i]];
        int codeLength = strlen(code);
        
        for(int j = 0; j < codeLength; j++) {
            encodedText[totalCodeLength] = code[j];
            totalCodeLength++;
        }
    }
    
    encodedText[totalCodeLength] = '\0';
    
    return encodedText;
}

int main() {
    // 示例数据
    char characters[] = {'A', 'B', 'C', 'D', 'E'};
    int frequencies[] = {2, 3, 4, 6, 8};
    int n = sizeof(characters) / sizeof(char);
    
    // 构建哈夫曼树
    Node* huffmanTree = buildHuffmanTree(characters, frequencies, n);
    
    // 分配编码
    char* codes[256];
    char* code = (char*)malloc(sizeof(char) * 256);
    assignCode(huffmanTree, codes, code, 0);
    
    // 编码文本
    char* text = "ABCDAEBD";
    char* encodedText = encodeText(text, codes);
    
    printf("原始文本：%s\n", text);
    printf("编码后的文本：%s\n", encodedText);
    
    return 0;
}

注意，这只是一个简单的示例代码，实际应用中可能还需要考虑更多的边界条件和错误处理。