题目

4.编程题4.1写出求二叉树[1]T中叶子个数的算法。fbox(添加照片)答题需要画图或者写计算过程的可在纸上完成，拍照成一张图上传（最多上传三张图片）。如需删除图片，可点击

4.编程题 4.1 写出求二叉树[1]T中叶子个数的算法。 $\fbox{添加照片}$ 答题需要画图或者写计算过程的可在纸上完成，拍照成一 张图上传（最多上传三张图片）。如需删除图片，可点击

题目解答

答案

根据题意，需设计一个递归算法[2]计算二叉树中叶子节点的数量。核心逻辑如下： 1. 若当前节点为空，返回0。 2. 若当前节点是叶子节点（无左、右子树），返回1。 3. 否则，递归计算左子树和右子树的叶子节点数并相加。 完整代码如下： ```c #include #include typedef struct Node { int data; struct Node *left, *right; } Node; Node* newNode(int data) { Node* node = (Node*)malloc(sizeof(Node)); node->data = data; node->left = node->right = NULL; return node; } int CountLeaves(Node* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return CountLeaves(root->left) + CountLeaves(root->right); } int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->right = newNode(6); int leafCount = CountLeaves(root); printf("叶子节点数: %d\n", leafCount); // 输出3 return 0; } ``` 该算法通过递归实现，时间复杂度为 $ O(n) $，空间复杂度为 $ O(h) $。对于示例树，叶子节点为4、5、6，总数为3。

解析

考查要点：本题主要考查二叉树的基本概念及递归算法的设计能力，要求掌握叶子节点的定义及树的遍历方法。

解题核心思路：

  1. 叶子节点的判断：若一个节点的左、右子树均为空，则该节点是叶子节点。
  2. 递归遍历：通过递归方式遍历二叉树，对每个节点进行判断，若为叶子节点则计数加1，否则递归处理左右子树。

破题关键点：

  • 递归终止条件：当前节点为空时返回0。
  • 递归返回值：若当前节点是叶子节点，返回1；否则返回左右子树叶子节点数之和。

算法设计步骤

  1. 递归终止条件：
    • 若当前节点为空，说明路径结束，返回0。
  2. 叶子节点判断：
    • 若当前节点的左、右子树均为空，返回1。
  3. 递归处理子树：
    • 若当前节点不是叶子节点，则递归计算左子树和右子树的叶子节点数，将结果相加后返回。

示例分析

以题目中的示例树为例： 

    1
   / \
  2   3
 / \   \
4  5   6
  • 根节点1：非叶子节点，递归处理左子树（根2）和右子树（根3）。
  • 左子树根2：非叶子节点，递归处理左子树（根4）和右子树（根5）。
    • 根4：叶子节点，返回1。
    • 根5：叶子节点，返回1。
    • 根2的叶子数为1 + 1 = 2。
  • 右子树根3：非叶子节点，递归处理右子树（根6）。
    • 根6：叶子节点，返回1。
    • 根3的叶子数为1。
  • 总叶子数：2（左子树） + 1（右子树） = 3。