21xrx.com
2024-09-20 00:56:52 Friday
登录
文章检索 我的文章 写文章
C++算法:统计二叉树叶子结点个数
2023-06-22 06:22:26 深夜i     --     --
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;如果左右子树不为空,则继续递归遍历其左右子树。

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

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复