WY0708 发表于 2023-11-13 18:38:40

数据结构，树的操作

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

isdkz 发表于 2023-11-13 18:38:48

你可以通过遍历树的方式来实现。以下是一个使用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小 发表于 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);
    }

    // 判断当前节点的子节点数量是否为2
    if (root->numChildren == 2) {
      count++;
    }

    return count;
}


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


int main() {
    // 构建树结构并初始化

    // 调用计算函数
    int result = countDegreeTwoNodes(root);
    printf("度为二的节点个数为: %d\n", result);

    return 0;
}


通过以上代码，我们可以实现统计树中度为二的节点个数的功能。希望对你有所帮助。如果还有其他问题，请随时提问。
页: [1]
查看完整版本: 数据结构，树的操作