在一棵以二叉链表表示的二叉树上,试基于C语言给出统计树中具有度为1的结点数目的算法。写出完整代码
时间: 2024-11-09 22:26:19 浏览: 24
在二叉链表表示的二叉树中,每个节点都有一个左指针和一个右指针。度为1的节点是指那些只有一个子节点的节点。我们可以遍历整棵树并计数度为1的节点。这里提供一个简单的C语言函数来实现这个功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 功能:计算二叉树中度为1的节点数目
int countDegreeOneNodes(TreeNode* root) {
if (root == NULL) {
return 0; // 如果为空节点,则返回0
}
int degreeOneCount = 0;
// 对左子树递归计数
if (root->left != NULL && root->left->right == NULL) { // 如果左子节点存在并且右子节点为空
degreeOneCount++;
}
// 对右子树递归计数
if (root->right != NULL && root->right->left == NULL) { // 如果右子节点存在并且左子节点为空
degreeOneCount++;
}
// 继续对左右子节点递归计数
degreeOneCount += countDegreeOneNodes(root->left);
degreeOneCount += countDegreeOneNodes(root->right);
return degreeOneCount;
}
int main() {
// 这里需要实例化一个二叉树,然后传入根节点到上述函数中计算度为1的节点数
// 由于这里是示例,你需要实际提供一个已构建好的二叉树结构
TreeNode* exampleTreeRoot = ...; // 实际的二叉树根节点
int degreeOneCount = countDegreeOneNodes(exampleTreeRoot);
printf("The number of nodes with degree 1 is: %d\n", degreeOneCount);
return 0;
}
```
阅读全文