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

WY0708

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

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-13 18:40:33

你可以使用递归来实现。首先，定义一个函数来遍历树的每个节点并计算度为二的节点个数。在函数中，对于每个节点，你需要检查它的子节点个数（也就是它的度），如果度为二，则计数器加一。然后递归地对每个子节点调用这个函数。最后返回计数器的值即可。

以下是一个简单的C语言实现示例：

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

struct TreeNode {
    int data;
    struct TreeNode* children[10]; // 假设每个节点最多有10个子节点
    int numChildren;
};

int countDegreeTwoNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    int count = 0;
    if (root->numChildren == 2) {
        count = 1;
    }
    
    for (int i = 0; i < root->numChildren; i++) {
        count += countDegreeTwoNodes(root->children[ i]);
    }
    
    return count;
}

int main() {
    // 在这里构建你的树，并调用 countDegreeTwoNodes 函数
    return 0;
}

在这个示例中，我们假设每个节点最多有10个子节点，并定义了一个结构体  TreeNode  来表示树的节点。 countDegreeTwoNodes  函数用于计算度为二的节点个数。

跳转到最佳答案楼层

isdkz

你可以使用递归来实现。首先，定义一个函数来遍历树的每个节点并计算度为二的节点个数。在函数中，对于每个节点，你需要检查它的子节点个数（也就是它的度），如果度为二，则计数器加一。然后递归地对每个子节点调用这个函数。最后返回计数器的值即可。

以下是一个简单的C语言实现示例：

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

struct TreeNode {
    int data;
    struct TreeNode* children[10]; // 假设每个节点最多有10个子节点
    int numChildren;
};

int countDegreeTwoNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    int count = 0;
    if (root->numChildren == 2) {
        count = 1;
    }
    
    for (int i = 0; i < root->numChildren; i++) {
        count += countDegreeTwoNodes(root->children[ i]);
    }
    
    return count;
}

int main() {
    // 在这里构建你的树，并调用 countDegreeTwoNodes 函数
    return 0;
}

在这个示例中，我们假设每个节点最多有10个子节点，并定义了一个结构体  TreeNode  来表示树的节点。 countDegreeTwoNodes  函数用于计算度为二的节点个数。