以二叉链表作为二叉树的存储结构,设计一个函数用来统计二叉树的叶子节点个数,并测试该函数。
时间: 2023-04-30 13:01:41 浏览: 56
设计函数如下:
int countLeaf(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaf(root->left) + countLeaf(root->right);
}
其中,TreeNode是二叉链表节点的结构体,包含左右子节点指针。
函数的实现思路是:如果当前节点为空,返回0;如果当前节点是叶子节点,返回1;否则递归计算左右子树的叶子节点个数,并返回它们的和。
测试代码如下:
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int count = countLeaf(root);
cout << "叶子节点个数:" << count << endl;
return 0;
}
输出结果为:
叶子节点个数:4
说明函数实现正确。