用c语言实现哈夫曼树

以下是用C语言实现哈夫曼树的基本步骤：

1. 定义哈夫曼树的结点结构体，包括权值、左右孩子指针和父亲指针等成员变量。

2. 定义哈夫曼树的构建函数，该函数接收一个权值数组作为参数，返回构建好的哈夫曼树的根节点指针。

3. 在构建函数中，首先根据权值数组创建n个叶子结点，然后将这些叶子结点按照权值从小到大排序。

4. 接着，循环n-1次，每次取出权值最小的两个结点作为新结点的左右孩子，新结点的权值为左右孩子权值之和。

5. 将新结点插入到已排序的叶子结点数组中，并重新排序。

6. 最后，返回根节点指针即可。

以下是C语言实现哈夫曼树的代码示例：

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

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

// 构建哈夫曼树的函数
TreeNode* buildHuffmanTree(int *weights, int n) {
    // 创建n个叶子结点
    TreeNode **nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);
    for (int i = 0; i < n; i++) {
        nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));
        nodes[i]->weight = weights[i];
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
        nodes[i]->parent = NULL;
    }

    // 按照权值从小到大排序
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nodes[i]->weight > nodes[j]->weight) {
                TreeNode *temp = nodes[i];
                nodes[i] = nodes[j];
                nodes[j] = temp;
            }
        }
    }

    // 构建哈夫曼树
    for (int i = 0; i < n - 1; i++) {
        // 取出权值最小的两个结点作为新结点的左右孩子
        TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));        newNode->weight = nodes[i]->weight + nodes[i+1]->weight;
        newNode->left = nodes[i];
        newNode->right = nodes[i+1];
        newNode->parent = NULL;

        // 将新结点插入到已排序的叶子结点数组中
        nodes[i+1] = newNode;
        for (int j = i + 2; j < n; j++) {
            if (nodes[j-1]->weight > nodes[j]->weight) {
                TreeNode *temp = nodes[j-1];
                nodes[j-1] = nodes[j];
                nodes[j] = temp;
            } else {
                break;
            }
        }
    }

    // 返回根节点指针
    return nodes[n-1];
}

// 测试代码
int main() {
    int weights[] = {5, 2, 4, 7, 1, 3, 6};
    int n = sizeof(weights) / sizeof(weights[0]);

    TreeNode *root = buildHuffmanTree(weights, n);

    return 0;
}