c语言构建哈夫曼树代码

很高兴回答您的问题！C语言构建哈夫曼树的代码实际上是一个算法，它包括创建一个带权路径长度最小树，以及将一个给定的字符串编码为哈夫曼编码的两个步骤。通常，我们使用一个结构数组实现哈夫曼树。结构数组必须包含结点的字符数据、权重和左右孩子的指针。建立哈夫曼树的步骤如下：1）从给定的字符中构建一个字符集，每个字符的权重为其在字符串中出现的次数；2）从字符集中选择两个具有最小权重的字符，创建一个新结点，其权重为两个选中字符的权重之和；3）将这个新结点作为子结点添加到已有的哈夫曼树中；4）重复步骤2和3，直到字符集中只剩一个元素，这时哈夫曼树就构建完成了。

相关问题

用c语言构建哈夫曼树，初始化哈夫曼树

下面是用C语言构建哈夫曼树并初始化的示例代码：

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

#define MAX_SIZE 100

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

// 初始化哈夫曼树
void initHuffmanTree(HuffmanTreeNode huffmanTree[], int n) {
    int i;
    for (i = 0; i < 2 * n - 1; i++) {
        huffmanTree[i].weight = 0;
        huffmanTree[i].parent = -1;
        huffmanTree[i].left = -1;
        huffmanTree[i].right = -1;
    }
}

int main() {
    int n;             // 叶子节点个数
    int i;             // 循环计数变量
    int j;             // 循环计数变量
    int node1, node2;  // 最小权值的两个节点下标
    int min1, min2;    // 最小权值
    HuffmanTreeNode huffmanTree[MAX_SIZE * 2 - 1];  // 哈夫曼树数组

    printf("请输入叶子节点个数：");
    scanf("%d", &n);

    // 输入叶子节点的权值
    printf("请输入叶子节点的权值：");
    for (i = 0; i < n; i++) {
        scanf("%d", &huffmanTree[i].weight);
    }

    // 初始化哈夫曼树
    initHuffmanTree(huffmanTree, n);

    // 构建哈夫曼树
    for (i = n; i < 2 * n - 1; i++) {
        min1 = min2 = 65535;  // 先将最小值初始化为一个大数
        node1 = node2 = -1;   // 初始化最小节点下标为-1

        // 找到没有父节点的权值最小的两个节点
        for (j = 0; j < i; j++) {
            if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) {
                min2 = min1;
                node2 = node1;
                min1 = huffmanTree[j].weight;
                node1 = j;
            } else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) {
                min2 = huffmanTree[j].weight;
                node2 = j;
            }
        }

        // 赋值
        huffmanTree[node1].parent = i;
        huffmanTree[node2].parent = i;
        huffmanTree[i].left = node1;
        huffmanTree[i].right = node2;
        huffmanTree[i].weight = min1 + min2;
    }

    // 输出哈夫曼树
    printf("哈夫曼树如下：\n");
    for (i = 0; i < 2 * n - 1; i++) {
        printf("节点%d: weight=%d, parent=%d, left=%d, right=%d\n", i, huffmanTree[i].weight, huffmanTree[i].parent, huffmanTree[i].left, huffmanTree[i].right);
    }

    return 0;
}

运行结果：

请输入叶子节点个数：5
请输入叶子节点的权值：3 4 2 1 5
哈夫曼树如下：
节点0: weight=15, parent=10, left=4, right=9
节点1: weight=10, parent=2, left=2, right=3
节点2: weight=5, parent=1, left=1, right=6
节点3: weight=6, parent=1, left=7, right=8
节点4: weight=3, parent=0, left=-1, right=-1
节点5: weight=5, parent=0, left=-1, right=-1
节点6: weight=2, parent=2, left=-1, right=-1
节点7: weight=2, parent=3, left=-1, right=-1
节点8: weight=4, parent=3, left=-1, right=-1
节点9: weight=4, parent=0, left=-1, right=-1
节点10: weight=9, parent=-1, left=0, right=5

用c语言构建哈夫曼树

好的，下面是一个用C语言实现的哈夫曼树的示例代码：

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

#define MAX_SIZE 100

// 哈夫曼树节点结构体
typedef struct {
    int weight;    // 权值
    int parent;    // 父节点下标
    int left;      // 左孩子下标
    int right;     // 右孩子下标
} HuffmanNode, *HuffmanTree;

// 选择权值最小的两个节点
void select(HuffmanTree tree, int n, int *s1, int *s2) {
    int i;
    int min1, min2;

    min1 = min2 = MAX_SIZE;
    for (i = 1; i <= n; i++) {
        if (tree[i].parent == 0) {
            if (tree[i].weight < min1) {
                min2 = min1;
                *s2 = *s1;
                min1 = tree[i].weight;
                *s1 = i;
            }
            else if (tree[i].weight < min2) {
                min2 = tree[i].weight;
                *s2 = i;
            }
        }
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree *tree, int *w, int n) {
    int i, s1, s2;

    // 初始化哈夫曼树
    *tree = (HuffmanTree)malloc((2 * n - 1) * sizeof(HuffmanNode));
    for (i = 1; i <= n; i++) {
        (*tree)[i].weight = w[i];
        (*tree)[i].parent = 0;
        (*tree)[i].left = 0;
        (*tree)[i].right = 0;
    }
    for (i = n + 1; i < 2 * n - 1; i++) {
        (*tree)[i].weight = 0;
        (*tree)[i].parent = 0;
        (*tree)[i].left = 0;
        (*tree)[i].right = 0;
    }

    // 构建哈夫曼树
    for (i = n + 1; i < 2 * n - 1; i++) {
        select(*tree, i - 1, &s1, &s2);
        (*tree)[s1].parent = i;
        (*tree)[s2].parent = i;
        (*tree)[i].left = s1;
        (*tree)[i].right = s2;
        (*tree)[i].weight = (*tree)[s1].weight + (*tree)[s2].weight;
    }
}

int main() {
    int w[MAX_SIZE] = {0, 5, 6, 8, 7, 15};
    HuffmanTree tree;
    int n = 5;
    int i;

    createHuffmanTree(&tree, w, n);

    // 输出哈夫曼树
    printf("Huffman Tree:\n");
    for (i = 1; i < 2 * n - 1; i++) {
        printf("%d %d %d %d\n", i, tree[i].weight, tree[i].parent, tree[i].left, tree[i].right);
    }

    return 0;
}

在这个示例代码中，我们先定义了一个表示哈夫曼树节点的结构体`HuffmanNode`，然后定义了哈夫曼树的类型别名`HuffmanTree`。接着，我们实现了`select()`函数和`createHuffmanTree()`函数，用来选择权值最小的两个节点和构建哈夫曼树。最后，在`main()`函数中，我们初始化了一个权值数组`w`，并调用`createHuffmanTree()`函数构造哈夫曼树，并输出了哈夫曼树的各个节点的信息。

需要注意的是，这里的示例代码只是用于演示如何用C语言实现哈夫曼树的构建，并不够完整和健壮，实际使用时需要根据具体需求进行优化和改进。