c语言数据结构类型定义哈夫曼树

在 C 语言中，可以通过结构体和指针来定义和操作哈夫曼树。

首先，定义一个结构体来表示节点的信息，如下所示：

struct HuffmanNode {
    int weight; // 权重值
    int parent; // 父节点位置
    int left;   // 左子节点位置
    int right;  // 右子节点位置
};

然后，定义一个指向节点的指针数组来存储所有节点：

#define MAX_NODE_NUM 100 // 最大节点数
HuffmanNode huffTree[MAX_NODE_NUM];

在构建哈夫曼树的过程中，需要不断地取出队列中权重值最小的两个节点，合并成一个新的父节点，并将父节点加入队列。对于每个节点，需要记录其位置以及权重值，因此可以定义一个结构体来表示节点在队列中的信息，如下所示：

struct QueueNode {
    int pos;     // 节点位置
    int weight;  // 权重值
};

然后，定义一个数组来存储所有节点的位置：

int queue[MAX_NODE_NUM];

在构建哈夫曼树的过程中，可以先将所有叶子节点加入队列中：

int n = 0; // 节点数
for (int i = 0; i < num; i++) {
    huffTree[i].weight = weights[i];
    huffTree[i].parent = -1; // 初始时父节点为-1，表示该节点还没有父节点
    huffTree[i].left = -1;   // 初始时左子节点为-1，表示该节点是叶子节点
    huffTree[i].right = -1;  // 初始时右子节点为-1，表示该节点是叶子节点
    queue[n++] = i;
}

接下来，不断取出队列中权重值最小的两个节点，合并成一个新的父节点，并将父节点加入队列，直到队列中只剩下一个节点：

while (n > 1) {
    int min1 = 0, min2 = 1;
    if (huffTree[queue[min1]].weight > huffTree[queue[min2]].weight) {
        swap(min1, min2);
    }
    for (int i = 2; i < n; i++) {
        if (huffTree[queue[i]].weight < huffTree[queue[min1]].weight) {
            min2 = min1;
            min1 = i;
        } else if (huffTree[queue[i]].weight < huffTree[queue[min2]].weight) {
            min2 = i;
        }
    }
    int pos1 = queue[min1];
    int pos2 = queue[min2];
    int parent = n; // 新的父节点的位置为n
    n++; // 更新节点数
    huffTree[pos1].parent = parent;
    huffTree[pos2].parent = parent;
    huffTree[parent].weight = huffTree[pos1].weight + huffTree[pos2].weight;
    huffTree[parent].left = pos1;
    huffTree[parent].right = pos2;
    queue[min1] = parent;
    queue[min2] = queue[n-1];
}

最后，可以通过遍历树来获取每个字符的编码。具体来说，可以从叶子节点开始，沿着父节点不断向上遍历，记录经过的路径（0表示向左，1表示向右），直到根节点。得到的路径即为该字符的哈夫曼编码。