[已解决]数据结构，树的操作

WY0708

请问大家，求一颗树中（不一定是二叉树）度为二的结点个数，怎么用C语言实现？

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-11-13 18:39:15

使用C语言计算树中度为二的结点个数

要计算一棵树中度为二的节点个数，可以使用深度优先搜索（DFS）的方式遍历整棵树。对于每个节点，我们需要统计其子节点或者子树中度为二的节点个数。

首先，我们需要定义树的数据结构，可以使用指针来表示树节点：

#include <stdio.h>#include <stdlib.h>struct TreeNode {    int val;    struct TreeNode** children; // 指向子节点的指针数组    int numChildren; // 子节点的数量};

接下来，我们可以编写一个递归函数来计算度为二的节点个数。该函数遍历当前节点的子节点，并递归地调用自身以计算子节点或子树中度为二的节点个数。对于当前节点，如果其子节点数量等于2，则将结果计数器加一。

int countDegreeTwoNodes(struct TreeNode* root) {    if (root == NULL) {        return 0;    }    int count = 0;    // 遍历当前节点的子节点    for (int i = 0; i < root->numChildren; i++) {        count += countDegreeTwoNodes(root->children[i]);    }    // 判断当前节点的子节点数量是否为2    if (root->numChildren == 2) {        count++;    }    return count;}

最后，在主函数中，我们可以构建树并调用上述函数来计算度为二的节点个数。

int main() {    // 构建树结构并初始化    // 调用计算函数    int result = countDegreeTwoNodes(root);    printf("度为二的节点个数为: %d\n", result);    return 0;}

通过以上代码，我们可以实现统计树中度为二的节点个数的功能。希望对你有所帮助。如果还有其他问题，请随时提问。

跳转到最佳答案楼层

isdkz

你可以通过遍历树的方式来实现。以下是一个使用C语言的示例代码：

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

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

int countNodesWithDegreeTwo(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int count = 0;
    if (root->left != NULL && root->right != NULL) {
        count = 1;
    }
    return count + countNodesWithDegreeTwo(root->left) + countNodesWithDegreeTwo(root->right);
}

int main() {
    // 创建树并初始化
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->data = 1;
    root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->data = 3;
    root->right->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->left->data = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = NULL;

    int result = countNodesWithDegreeTwo(root);
    printf("度为二的结点个数为: %d\n", result);

    // 释放内存
    free(root->left);
    free(root->right->left);
    free(root->right);
    free(root);

    return 0;
}

这段代码定义了一个树的结构，然后使用递归的方式遍历树，统计具有度为二的节点的个数。在这个例子中，我们假设树的节点包含整数数据。

Mike_python小

使用C语言计算树中度为二的结点个数

要计算一棵树中度为二的节点个数，可以使用深度优先搜索（DFS）的方式遍历整棵树。对于每个节点，我们需要统计其子节点或者子树中度为二的节点个数。

首先，我们需要定义树的数据结构，可以使用指针来表示树节点：

#include <stdio.h>#include <stdlib.h>struct TreeNode {    int val;    struct TreeNode** children; // 指向子节点的指针数组    int numChildren; // 子节点的数量};

接下来，我们可以编写一个递归函数来计算度为二的节点个数。该函数遍历当前节点的子节点，并递归地调用自身以计算子节点或子树中度为二的节点个数。对于当前节点，如果其子节点数量等于2，则将结果计数器加一。

int countDegreeTwoNodes(struct TreeNode* root) {    if (root == NULL) {        return 0;    }    int count = 0;    // 遍历当前节点的子节点    for (int i = 0; i < root->numChildren; i++) {        count += countDegreeTwoNodes(root->children[i]);    }    // 判断当前节点的子节点数量是否为2    if (root->numChildren == 2) {        count++;    }    return count;}

最后，在主函数中，我们可以构建树并调用上述函数来计算度为二的节点个数。

int main() {    // 构建树结构并初始化    // 调用计算函数    int result = countDegreeTwoNodes(root);    printf("度为二的节点个数为: %d\n", result);    return 0;}

通过以上代码，我们可以实现统计树中度为二的节点个数的功能。希望对你有所帮助。如果还有其他问题，请随时提问。