题目2:求二又树 T中度为0、度为1和度内2的结点数。要求在同一选归函数中完成计算求解过程,结果可以在主函数中输出。为此可以在主函数中定义一个整型数组,用于计数,而递归函数利用整形数组作为形参,利用数组传地址的特点将三个值带回(主函数)。
时间: 2024-11-09 21:22:06 浏览: 19
题目2涉及到的是二叉树的遍历问题,特别是深度优先搜索(DFS)的一种特殊情况。在这个场景下,我们需要编写一个递归函数来计算二叉树中度为0(叶子节点)、度为1(只有一个孩子的节点)和度为2(有两个孩子的节点)的节点总数。这个任务可以采用前序遍历的方式,因为前序遍历时,我们会先访问根节点,然后遍历左子树,最后遍历右子树。
在主函数中,我们可以定义一个整型数组`count`,长度为3,分别存储三种类型的节点数。递归函数会接收这个数组的引用作为参数:
```c++
int dfs(TreeNode* node, int* count) {
if (node == nullptr) return 0; // 如果当前节点为空,返回0
// 更新计数
if (node->left == nullptr && node->right == nullptr) count[0]++; // 度为0的节点(叶子)
else if (node->left != nullptr && node->right == nullptr) count[1]++; // 度为1的节点
else if (node->left != nullptr && node->right != nullptr) count[2]++; // 度为2的节点
// 递归处理左右子树
count = dfs(node->left, count);
count = dfs(node->right, count);
return 0; // 回调给主函数,这里通常不需要返回值,但为了保持一致,我们仍设为0
}
void mainFunction(TreeNode* root) {
int count[3] = {0, 0, 0}; // 初始化计数器
dfs(root, count);
cout << "度为0的节点数: " << count[0] << endl;
cout << "度为1的节点数: " << count[1] << endl;
cout << "度为2的节点数: " << count[2] << endl;
}
```
阅读全文