C语言给定包含n个结点的树，求有多少条边。

对于一棵包含 $n$ 个结点的树，我们知道它有 $n-1$ 条边。这个结论可以通过树的性质来证明。

一棵树可以看作是一个无向连通图，且其中任意两个结点之间仅有一条简单路径。那么，我们可以尝试使用归纳法来证明结论。

当 $n=1$ 时，树只有一个结点，没有边，结论显然成立。

假设当 $n=k$ 时，包含 $k$ 个结点的树有 $k-1$ 条边。

当 $n=k+1$ 时，我们可以选择其中一个结点作为根结点，然后将树分成若干颗子树。设其中一颗子树有 $m$ 个结点，则另一颗子树有 $k+1-m$ 个结点。根据归纳假设，这两颗子树分别有 $m-1$ 和 $(k+1-m)-1=k-m$ 条边。

而我们只需要在根结点处连一条边，就可以将这两颗子树连接起来，因此整棵树有 $(m-1)+(k-m)+1=k$ 条边。

因此，结论得证。对于一个包含 $n$ 个结点的树，它有 $n-1$ 条边。

在C语言中，可以直接使用 $n-1$ 来表示这个数量。

相关问题

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

这里是用C语言实现的哈夫曼树建立和输出：

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

// 定义哈夫曼树结点结构体
typedef struct huffmanNode {
    int weight;
    int parent, left, right;
} HuffmanNode;

// 建立哈夫曼树函数
void createHuffmanTree(HuffmanNode *huffmanTree, int n) {
    int i, j, min1, min2;
    // 初始化哈夫曼树
    for (i = 0; i < 2 * n - 1; i++) {
        huffmanTree[i].weight = 0;
        huffmanTree[i].parent = -1;
        huffmanTree[i].left = -1;
        huffmanTree[i].right = -1;
    }
    // 输入权值
    for (i = 0; i < n; i++) {
        printf("请输入第%d个叶子结点的权值：", i + 1);
        scanf("%d", &huffmanTree[i].weight);
    }
    // 构建哈夫曼树
    for (i = 0; i < n - 1; i++) {
        min1 = min2 = 0;
        // 找到当前权值最小的两个结点
        for (j = 0; j < n + i; j++) {
            if (huffmanTree[j].parent == -1) {
                if (huffmanTree[j].weight < huffmanTree[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (huffmanTree[j].weight < huffmanTree[min2].weight) {
                    min2 = j;
                }
            }
        }
        // 合并两个权值最小的结点
        huffmanTree[min1].parent = n + i;
        huffmanTree[min2].parent = n + i;
        huffmanTree[n + i].weight = huffmanTree[min1].weight + huffmanTree[min2].weight;
        huffmanTree[n + i].left = min1;
        huffmanTree[n + i].right = min2;
    }
}

// 输出哈夫曼树函数
void printHuffmanTree(HuffmanNode *huffmanTree, int n) {
    int i;
    printf("\n哈夫曼树如下：\n");
    printf("结点\t权值\t父结点\t左孩子\t右孩子\n");
    for (i = 0; i < 2 * n - 1; i++) {
        printf("%d\t%d\t%d\t%d\t%d\n", i + 1, huffmanTree[i].weight, huffmanTree[i].parent + 1,
               huffmanTree[i].left + 1, huffmanTree[i].right + 1);
    }
}

int main() {
    int n;
    printf("请输入叶子结点数n：");
    scanf("%d", &n);
    HuffmanNode *huffmanTree = (HuffmanNode *) malloc(sizeof(HuffmanNode) * (2 * n - 1));
    createHuffmanTree(huffmanTree, n);
    printHuffmanTree(huffmanTree, n);
    free(huffmanTree);
    return 0;
}

代码中，我们先定义了哈夫曼树结点结构体 `HuffmanNode`，包括结点权值、父结点、左孩子和右孩子四个成员变量。然后，我们实现了两个函数，分别是 `createHuffmanTree` 和 `printHuffmanTree`，用于建立哈夫曼树和输出哈夫曼树。

在 `createHuffmanTree` 函数中，我们首先初始化哈夫曼树的所有结点，然后输入每个叶子结点的权值。接着，我们使用循环不断地合并两个权值最小的结点，直到最后只剩下一个根结点，即为哈夫曼树的根节点。

在 `printHuffmanTree` 函数中，我们按照结点的编号、权值、父结点、左孩子和右孩子的顺序输出哈夫曼树的结点信息。

在主函数中，我们先输入叶子结点数 `n`，然后动态申请哈夫曼树空间，调用 `createHuffmanTree` 函数建立哈夫曼树，最后调用 `printHuffmanTree` 函数输出哈夫曼树。注意，程序结束前需要释放动态申请的哈夫曼树空间。

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

以下是使用C语言实现建立哈夫曼树并输出的示例代码：

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

#define MAX_LEAF_NODES 100

// 结点结构体
typedef struct Node {
    int weight;             // 权值
    int parent, left, right;// 父结点，左子结点，右子结点的下标
} Node;

// 获取权值最小的两个结点的下标
void getTwoMinNodes(Node *nodes, int n, int *min1, int *min2) {
    int i;
    *min1 = *min2 = -1;
    for (i = 0; i < n; i++) {
        if (nodes[i].parent == -1) {
            if (*min1 == -1 || nodes[i].weight < nodes[*min1].weight) {
                *min2 = *min1;
                *min1 = i;
            } else if (*min2 == -1 || nodes[i].weight < nodes[*min2].weight) {
                *min2 = i;
            }
        }
    }
}

// 构建哈夫曼树
void buildHuffmanTree(Node *nodes, int n) {
    int i, min1, min2;
    for (i = n; i < 2 * n - 1; i++) {
        getTwoMinNodes(nodes, i, &min1, &min2);
        nodes[min1].parent = i;
        nodes[min2].parent = i;
        nodes[i].left = min1;
        nodes[i].right = min2;
        nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
    }
}

// 输出哈夫曼编码
void printHuffmanCode(Node *nodes, int n) {
    int i, j, parent, cur;
    char *code = (char *) malloc(n * sizeof(char));
    for (i = 0; i < n; i++) {
        printf("Leaf Node %d: weight=%d, code=", i, nodes[i].weight);
        parent = nodes[i].parent;
        cur = i;
        j = 0;
        while (parent != -1) {
            if (nodes[parent].left == cur) {
                code[j++] = '0';
            } else {
                code[j++] = '1';
            }
            cur = parent;
            parent = nodes[cur].parent;
        }
        while (j > 0) {
            printf("%c", code[--j]);
        }
        printf("\n");
    }
    free(code);
}

int main() {
    int n, i;
    Node nodes[MAX_LEAF_NODES * 2 - 1];
    printf("Enter the number of leaf nodes: ");
    scanf("%d", &n);
    printf("Enter the weight of each leaf node:\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &nodes[i].weight);
        nodes[i].parent = -1;
        nodes[i].left = -1;
        nodes[i].right = -1;
    }
    buildHuffmanTree(nodes, n);
    printHuffmanCode(nodes, n);
    return 0;
}

输入格式为先输入叶子结点的数量，再输入每个叶子结点的权值，例如：

Enter the number of leaf nodes: 5
Enter the weight of each leaf node:
2 3 7 8 10

输出格式为每个叶子结点的权值和哈夫曼编码，例如：

Leaf Node 0: weight=2, code=1111
Leaf Node 1: weight=3, code=1110
Leaf Node 2: weight=7, code=110
Leaf Node 3: weight=8, code=10
Leaf Node 4: weight=10, code=0