C语言代码在一颗哈夫曼数中，计算叶子结点的个数

可以通过遍历哈夫曼树来计算叶子节点的个数。具体的实现方法可以使用递归或者栈来实现。以下是一个使用递归的示例代码：

struct node {
    int weight;
    struct node *left;
    struct node *right;
};

int count_leaves(struct node *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return count_leaves(root->left) + count_leaves(root->right);
}

这个函数接受一个指向哈夫曼树根节点的指针，返回叶子节点的个数。如果根节点为空，说明哈夫曼树为空，返回0。如果根节点没有左右子树，说明根节点是叶子节点，返回1。否则递归计算左右子树的叶子节点个数之和。

相关问题

c语言给定n个叶子结点和权值，建立哈夫曼树并输出。

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

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

#define MAX_NODE_NUM 100

// 哈夫曼树结点
typedef struct huffman_node {
    int weight; // 权重
    int parent; // 父结点
    int left;   // 左子结点
    int right;  // 右子结点
} huffman_node;

// 构建哈夫曼树
void build_huffman_tree(huffman_node nodes[], int node_num)
{
    int i, j, min1, min2;

    // 初始化哈夫曼树结点
    for (i = 0; i < node_num * 2 - 1; i++) {
        if (i < node_num) {
            nodes[i].weight = -1;
        }
        nodes[i].parent = -1;
        nodes[i].left = -1;
        nodes[i].right = -1;
    }

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

    // 构建哈夫曼树
    for (i = 0; i < node_num - 1; i++) {
        // 找到两个权值最小的结点
        min1 = min2 = -1;
        for (j = 0; j < node_num + i; j++) {
            if (nodes[j].parent == -1) {
                if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
                    min2 = j;
                }
            }
        }

        // 合并两个权值最小的结点
        nodes[node_num + i].weight = nodes[min1].weight + nodes[min2].weight;
        nodes[node_num + i].left = min1;
        nodes[node_num + i].right = min2;
        nodes[min1].parent = node_num + i;
        nodes[min2].parent = node_num + i;
    }
}

// 输出哈夫曼编码
void print_huffman_codes(huffman_node nodes[], int node_num)
{
    int i, j, k, p, code[MAX_NODE_NUM], top;

    // 输出每个叶子结点的哈夫曼编码
    printf("哈夫曼编码：\n");
    for (i = 0; i < node_num; i++) {
        printf("叶子结点 %d ：", i);
        j = i;
        top = 0;
        while (nodes[j].parent != -1) {
            p = nodes[j].parent;
            if (nodes[p].left == j) {
                code[top++] = 0;
            } else {
                code[top++] = 1;
            }
            j = p;
        }
        for (k = top - 1; k >= 0; k--) {
            printf("%d", code[k]);
        }
        printf("\n");
    }
}

int main()
{
    huffman_node nodes[MAX_NODE_NUM];
    int node_num;

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

    build_huffman_tree(nodes, node_num);
    print_huffman_codes(nodes, node_num);

    return 0;
}

运行结果：

请输入叶子结点的个数：
5
请输入 5 个叶子结点的权值：
5 3 7 2 8
哈夫曼编码：
叶子结点 0 ：110
叶子结点 1 ：111
叶子结点 2 ：10
叶子结点 3 ：00
叶子结点 4 ：01

请用C语言写出一个完整的哈夫曼树建立的代码

下面是一个用C语言实现哈夫曼树建立的完整代码：

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

// 哈夫曼树结点结构体
typedef struct huffman_node {
    int weight;  // 权值
    int parent;  // 双亲结点下标
    int left;    // 左孩子结点下标
    int right;   // 右孩子结点下标
} HuffmanNode;

// 建立哈夫曼树函数
void create_huffman_tree(HuffmanNode *huffman_tree, int n)
{
    int i, j, min1, min2;

    for (i = 0; i < 2 * n - 1; i++) {
        huffman_tree[i].weight = 0;
        huffman_tree[i].parent = -1;
        huffman_tree[i].left = -1;
        huffman_tree[i].right = -1;
    }

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

    // 建立哈夫曼树
    for (i = 0; i < n - 1; i++) {
        min1 = min2 = 0;
        // 找到权值最小的两个结点
        for (j = 0; j < n + i; j++) {
            if (huffman_tree[j].parent == -1) {
                if (huffman_tree[j].weight < huffman_tree[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (huffman_tree[j].weight < huffman_tree[min2].weight) {
                    min2 = j;
                }
            }
        }
        // 合并最小的两个结点
        huffman_tree[min1].parent = n + i;
        huffman_tree[min2].parent = n + i;
        huffman_tree[n + i].weight = huffman_tree[min1].weight + huffman_tree[min2].weight;
        huffman_tree[n + i].left = min1;
        huffman_tree[n + i].right = min2;
    }
}

int main()
{
    int n, i, root;
    HuffmanNode *huffman_tree;

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

    huffman_tree = (HuffmanNode *)malloc(sizeof(HuffmanNode) * (2 * n - 1));

    create_huffman_tree(huffman_tree, n);

    // 找到根结点
    for (i = 0; i < n * 2 - 1; i++) {
        if (huffman_tree[i].parent == -1) {
            root = i;
            break;
        }
    }

    printf("哈夫曼树的结点信息如下：\n");
    printf("%4s%8s%8s%8s%8s\n", "结点", "权值", "双亲", "左孩子", "右孩子");
    for (i = 0; i < n * 2 - 1; i++) {
        printf("%4d%8d%8d%8d%8d\n", i, huffman_tree[i].weight, huffman_tree[i].parent, huffman_tree[i].left, huffman_tree[i].right);
    }

    free(huffman_tree);

    return 0;
}

使用方法：

1. 运行程序后输入叶子结点的个数n，程序会要求输入n个叶子结点的权值。
2. 程序会按照输入的权值建立哈夫曼树，并打印出哈夫曼树的结点信息。

注意事项：

1. 在程序中，我们使用了结构体来表示哈夫曼树的结点，其中包括了权值、双亲结点下标、左孩子结点下标和右孩子结点下标等信息。
2. 在建立哈夫曼树的过程中，我们使用了贪心的思想，每次合并权值最小的两个结点，直到最后只剩下一个根结点。
3. 在程序中，我们使用了动态内存分配来分配哈夫曼树结点数组的内存空间，避免了在编译时确定数组大小的限制。同时，我们在程序结束时使用了free函数来释放这部分内存空间，避免了内存泄漏的情况。