以二叉链表作为二叉树的存储结构。编写递归算法,计算二叉树中叶子结点的数目。请将下面的代码补充完整。
时间: 2024-02-23 17:57:48 浏览: 89
好的,以下是递归算法计算二叉树中叶子结点数目的C语言程序,以二叉链表作为二叉树的存储结构:
```
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点定义
typedef struct TreeNode {
int data;
struct TreeNode *lchild, *rchild;
} TreeNode;
// 创建二叉树
TreeNode* create_tree() {
int data;
scanf("%d", &data);
if (data == -1) { // 输入-1表示该节点为空
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->lchild = create_tree();
node->rchild = create_tree();
return node;
}
// 计算二叉树中叶子结点数目的递归算法
int count_leaf(TreeNode *root) {
if (root == NULL) { // 如果节点为空,则返回0
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) { // 如果节点为叶子结点,则返回1
return 1;
}
return count_leaf(root->lchild) + count_leaf(root->rchild); // 递归计算左子树和右子树的叶子结点数目之和
}
int main() {
printf("请输入二叉树的节点数据(-1表示该节点为空):\n");
TreeNode *root = create_tree();
printf("二叉树中叶子结点数目为:%d\n", count_leaf(root));
return 0;
}
```
在递归算法`count_leaf()`中,如果节点为空,则返回0;如果节点为叶子结点,则返回1;否则递归计算左子树和右子树的叶子结点数目之和。在`main()`函数中,首先调用`create_tree()`函数创建二叉树,然后调用`count_leaf()`函数计算二叉树中叶子结点数目。
阅读全文