用c语言构造哈夫曼树

构造哈夫曼树的基本思路是：先将所有的叶子节点按照权值从小到大排序，然后选取权值最小的两个节点作为左右子节点，将它们的权值相加作为父节点的权值，再将父节点插入到原来的序列中，重复以上步骤，直到只剩下一个节点，这个节点就是哈夫曼树的根节点。

以下是用C语言实现构造哈夫曼树的基本步骤：
1. 定义一个结构体来表示哈夫曼树的节点，包括权值、左右子节点和父节点等信息。
2. 定义一个数组来存储所有的叶子节点，并按照权值从小到大排序。
3. 通过循环选取权值最小的两个节点作为左右子节点，创建一个新的父节点，并将父节点插入到数组中。
4. 重复以上步骤，直到只剩下一个节点，这个节点就是哈夫曼树的根节点。

以下是一个简单的C语言代码实现：

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

// 定义哈夫曼树节点结构体
typedef struct TreeNode {
    int weight; // 权值
    struct TreeNode *left; // 左子节点
    struct TreeNode *right; // 右子节点
    struct TreeNode *parent; // 父节点
} TreeNode;

// 定义叶子节点数组
TreeNode *leaves[100];

// 比较函数，用于排序
int cmp(const void *a, const void *b) {
    return ((TreeNode *)a)->weight - ((TreeNode *)b)->weight;
}

// 构造哈夫曼树
TreeNode *buildHuffmanTree(int n) {
    // 将叶子节点按照权值从小到大排序
    qsort(leaves, n, sizeof(TreeNode *), cmp);

    // 选取权值最小的两个节点作为左右子节点，创建一个新的父节点，并将父节点插入到数组中
    for (int i = 0; i < n - 1; i++) {
        TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
        newNode->weight = leaves[i]->weight + leaves[i+1]->weight;
        newNode->left = leaves[i];
        newNode->right = leaves[i+1];
        newNode->parent = NULL;
        leaves[i+1] = newNode;

        // 将新节点插入到正确的位置
        int j = i + 1;
        while (j < n - 1 && leaves[j]->weight > newNode->weight) {
            leaves[j] = leaves[j+1];
            j++;
        }
        leaves[j] = newNode;

        // 设置子节点的父节点
        newNode->left->parent = newNode;
        newNode->right->parent = newNode;
    }

    // 返回根节点
    return leaves[n-1];
}

int main() {
    // 初始化叶子节点数组
    int n = 5;
    for (int i = 0; i < n; i++) {
        leaves[i] = (TreeNode *)malloc(sizeof(TreeNode));
        scanf("%d", &leaves[i]->weight);
        leaves[i]->left = NULL;
        leaves[i]->right = NULL;
        leaves[i]->parent = NULL;
    }

    // 构造哈夫曼树
    TreeNode *root = buildHuffmanTree(n);

    // 输出根节点的权值
    printf("%d\n", root->weight);

    return 0;
}