赫夫曼树先序遍历c语言实现

赫夫曼树（Huffman Tree），也叫最优二叉树，常用于数据压缩算法。其构建过程是基于贪心策略。以下是C语言实现的简单先序遍历（Preorder Traversal）步骤：

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

// 定义节点结构体
typedef struct Node {
    char data;
    int freq; // 频率
    struct Node* left;
    struct Node* right;
} Node;

// 插入新节点到赫夫曼树
Node* insert(Node* root, char data) {
    if (root == NULL) return (Node*)malloc(sizeof(Node));
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

// 计算左子树和右子树的高度
int height(Node* node) {
    if (node == NULL) return -1;
    return 1 + MAX(height(node->left), height(node->right));
}

// 构建赫夫曼树并返回根节点
Node* buildHuffmanTree(char** freqs, int n) {
    // ... (按照频率排序并插入)
    // 具体实现这里略去，你需要对节点按频率降序排序，然后每次取两个最小频的节点合并成新的节点，直到只剩下一个节点为止
    return root;
}

// 先序遍历（根-左-右）
void preOrderTraversal(Node* root) {
    if (root != NULL) {
        printf("%c", root->data); // 输出当前节点的数据
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

int main() {
    char data[] = {'A', 'B', 'C', 'D', 'E'};
    int freq[] = {5, 9, 4, 6, 7}; // 数据频率列表
    int n = sizeof(data) / sizeof(data[0]);

    Node* root = buildHuffmanTree(freq, n);

    // 打印先序遍历结果
    preOrderTraversal(root);

    free(root); // 释放内存
    return 0;
}