在一棵以二叉链表表示的二叉树上,试基于C语言给出统计树中具有度为1的结点数目的算法。
时间: 2024-11-09 12:25:42 浏览: 12
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
在C语言中,我们可以通过遍历这棵二叉链表表示的二叉树来计算度为1的节点数目。首先,我们需要定义一个结构体来表示二叉树节点,包含一个值、左孩子和右孩子的指针。
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int countDegreeOne(TreeNode* root) {
if (root == NULL) return 0; // 如果根节点为空,返回0
int count = 0; // 初始化计数器为0
// 遍历树
if (root->left != NULL && root->right == NULL) count++; // 左子树存在,右子树不存在,计数加一
else if (root->left == NULL && root->right != NULL) count++; // 右子树存在,左子树不存在,计数加一
// 递归检查左右子节点
count += countDegreeOne(root->left); // 计算左子树的度1节点
count += countDegreeOne(root->right); // 计算右子树的度1节点
return count;
}
```
这个函数`countDegreeOne`会返回树中度为1的节点数目。它首先检查当前节点,如果有左子但无右子或反之,就增加计数。然后递归地对左右子树进行同样的操作。
阅读全文