21xrx.com
2025-04-06 14:10:40 Sunday
文章检索 我的文章 写文章
C++算法：统计二叉树叶子结点个数
2023-06-22 06:22:26 深夜i     36     0
C++ 算法 二叉树 叶子结点 统计

在C++编程的过程中，统计二叉树叶子结点个数是一个常见的算法题目。二叉树是一种常用的数据结构，由于其高效的查找和插入操作，很多算法都会使用它来实现。

在统计二叉树叶子结点个数的过程中，我们需要先明确什么是叶子结点。 叶子结点就是没有子结点的结点。因此，在统计叶子结点的个数的时候，只需要遍历整个二叉树，当当前结点的左右子树都为空时，即为一个叶子结点。

具体的实现过程如下：

1.定义一个计数器count，用来统计叶子结点的个数。初始值为0。

2.对于每一个结点node：

（1）如果node为空，则直接返回。

（2）如果node左右子树都为空，则count加1。

（3）如果node左右子树不为空，则递归遍历左右子树。

3. 最后返回count，即可得到二叉树叶子结点的个数。

具体的代码实现如下：

#include<iostream>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int countLeafNodes(TreeNode* root) {
  int count = 0;
  if (root == NULL) 返回叶子结点个数为0
  
  if (root->left == NULL && root->right == NULL)
    return 1;//当前节点无左右子树
  count = countLeafNodes(root->left) + countLeafNodes(root->right);//递归统计叶子结点的个数
  return count;
}
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 res = countLeafNodes(root);
  cout << "LeafNodeNum = " << res << endl;
  return 0;
}

在上面的代码中，我们使用了递归的思想来遍历整个二叉树。对于每一个结点，我们判断其左右子树是否为空，如果都为空，则说明当前结点为叶子结点，计数器加1；如果左右子树不为空，则继续递归遍历其左右子树。

最后输出叶子结点的个数，即可得到二叉树的叶子结点数。以上就是统计二叉树叶子结点个数的实现过程。

  
  

评论区