设计C函数,计算二叉树中度为2的结点的个数。
时间: 2024-09-07 15:04:01 浏览: 51
求度为2的结点个数-二叉树
设计一个C函数来计算二叉树中度为2的节点的数量,你可以采用递归的方式遍历整个二叉树。首先,我们需要定义一个结构体表示二叉树的节点,每个节点包含一个值、左子节点和右子节点。假设我们已经有一个名为`TreeNode`的结构:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int countDegreeTwoNodes(TreeNode* root) {
// 如果根节点为空,返回0
if (root == NULL) {
return 0;
}
// 如果当前节点是叶子节点(度为0),那么其右兄弟可能是度为2的节点
if (root->left == NULL && root->right == NULL) {
if (root->right->left != NULL || root->right->right != NULL) {
return 1 + countDegreeTwoNodes(root->right); // 右兄弟的情况
} else {
return countDegreeTwoNodes(root->left); // 左兄弟的情况
}
}
// 如果当前节点有左右孩子,则需要检查左右孩子的度是否为2
int degreeOne = 0; // 计算度为1的节点数量,用于后续判断
if (root->left != NULL) {
degreeOne += (root->left->left != NULL || root->left->right != NULL);
}
if (root->right != NULL) {
degreeOne += (root->right->left != NULL || root->right->right != NULL);
}
// 度为2的节点就是当前节点和它的右孩子都不为NULL,且左孩子非空或右孩子非空
int degreeTwo = (degreeOne > 1 && (root->right != NULL || root->right->left != NULL));
return degreeTwo + countDegreeTwoNodes(root->left) + countDegreeTwoNodes(root->right);
}
```
这个`countDegreeTwoNodes`函数会递归地遍历树,并在每次访问节点时检查其度。如果找到一个度为2的节点,它将返回1;如果没有,继续递归直到整棵树都被检查。
阅读全文