C语言求完全二叉树的权值

如果给定一棵完全二叉树，我们可以按照完全二叉树的定义，将所有节点从上到下、从左到右依次编号。假设根节点的编号为1，则第i个节点的编号为i。

对于一棵完全二叉树，我们可以使用数组来存储它。假设我们定义了一个数组tree，其中tree[i]表示第i个节点的权值。则根节点的权值为tree[1]，它的左子节点的权值为tree[2]，右子节点的权值为tree[3]，它的左子节点的左子节点的权值为tree[4]，右子节点的左子节点的权值为tree[5]，以此类推。

那么，对于一棵完全二叉树，它的所有节点的权值之和可以通过如下代码计算：

int sum = 0;
for (int i = 1; i <= n; i++) {
    sum += tree[i];
}

其中，n表示完全二叉树的节点个数。注意，这里的节点个数不是树的深度，而是树的总节点数。对于一棵深度为d的完全二叉树，它的节点个数为2^d-1。

相关问题

克鲁斯卡尔算法C语言制作最小二叉树代码

克鲁斯卡尔算法是用于计算最小生成树的算法，与二叉树无关。如果您要制作最小生成树，可以使用克鲁斯卡尔算法。如果您要制作最小二叉树，可以使用其他算法，如霍夫曼编码算法等。

以下是使用C语言实现克鲁斯卡尔算法求解最小生成树的代码：

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

#define MAX_EDGE_NUM 100
#define MAX_VERTEX_NUM 100

// 定义边的结构体
typedef struct {
    int u; // 边的起点
    int v; // 边的终点
    int w; // 边的权值
} Edge;

// 定义并查集
int father[MAX_VERTEX_NUM];

// 初始化并查集
void init(int n) {
    int i;
    for (i = 0; i < n; i++) {
        father[i] = i;
    }
}

// 查找祖先节点
int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

// 合并两个集合
void merge(int x, int y) {
    int x_root = find(x);
    int y_root = find(y);
    if (x_root != y_root) {
        father[x_root] = y_root;
    }
}

// 比较函数，用于排序
int cmp(const void *a, const void *b) {
    Edge *e1 = (Edge *)a;
    Edge *e2 = (Edge *)b;
    return e1->w - e2->w;
}

int main() {
    int n, m; // n表示顶点数，m表示边数
    Edge edges[MAX_EDGE_NUM]; // 存储边的数组
    int i, j, k;
    int sum = 0; // 最小生成树的权值之和

    // 读入顶点数和边数
    scanf("%d %d", &n, &m);

    // 读入每条边的信息
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    // 初始化并查集
    init(n);

    // 将边按权值从小到大排序
    qsort(edges, m, sizeof(Edge), cmp);

    // 逐条加入边
    for (i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        // 判断边的两个端点是否在同一个集合中
        if (find(u) != find(v)) {
            // 加入这条边
            merge(u, v);
            sum += w;
        }
    }

    printf("最小生成树的权值之和为：%d\n", sum);

    return 0;
}

在这段代码中，我们使用了一个`Edge`结构体来存储每条边的信息，包括起点、终点和权值。我们还定义了一个`MAX_EDGE_NUM`和`MAX_VERTEX_NUM`常量来限制最大边数和顶点数，以防止数组越界的问题。读入顶点数和边数后，我们使用一个循环读入每条边的信息。在循环结束后，我们初始化并查集、将边按权值从小到大排序，并逐条加入边，直到生成树的边数等于顶点数减1为止。最后输出最小生成树的权值之和。

C语言编写二叉树的WPL计算

可以使用哈夫曼编码来计算二叉树的WPL（带权路径长度）。首先，计算每个叶子节点的权值和深度，然后将每个叶子节点看作一个符号，并将它们进行哈夫曼编码，得到相应的编码。最后，将每个符号的权值乘以其对应的编码长度，再将它们相加即可得到二叉树的WPL。

具体的实现可以使用C语言中的结构体来表示二叉树节点，使用递归实现深度遍历，并使用动态数组（例如链表）来保存每个叶子节点的权值和哈夫曼编码。