21xrx.com
2024-11-22 07:00:57 Friday
登录
文章检索 我的文章 写文章
C++代码:求二叉树叶子节点的个数
2023-07-07 20:28:15 深夜i     --     --
C++代码 二叉树 叶子节点 个数 计算

在算法与数据结构中,二叉树是一种非常常见的数据结构,常用于表示具有层次结构的数据。二叉树由节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。比如,在以下树中,节点2、4、5、7、8、9、11、12都是叶子节点。


    1

    / \

   2  3

   / \

  4  5

    / \

   6  7

     / \

    8  9

      / \

     10  11

       / \

      12  13

如果要求二叉树中叶子节点的个数,可以使用编程语言C++实现,具体实现代码如下:


#include <iostream>

// 定义二叉树节点

struct TreeNode {

  int val;

  TreeNode* left;

  TreeNode* right;

  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

// 求二叉树叶子节点数目的函数

int countLeafNodes(TreeNode* root) {

  if (!root)

    return 0;

  

  if (!root->left && !root->right)

    return 1;

  

  return countLeafNodes(root->left) + countLeafNodes(root->right);

}

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->left->right->left = new TreeNode(6);

  root->left->right->right = new TreeNode(7);

  root->left->right->right->left = new TreeNode(8);

  root->left->right->right->right = new TreeNode(9);

  root->left->right->right->right->left = new TreeNode(10);

  root->left->right->right->right->right = new TreeNode(11);

  root->left->right->right->right->right->left = new TreeNode(12);

  root->left->right->right->right->right->right = new TreeNode(13);

  

  // 输出叶子节点数目

  std::cout << "叶子节点数目为:" << countLeafNodes(root) << std::endl;

  return 0;

}

需要说明的是,在上述代码中,我们首先定义了一个树节点(使用了C++的类),其中val存放节点数值,left和right指向该节点的左右子节点。然后,我们定义了countLeafNodes函数,该函数递归地遍历整个二叉树,累计叶子节点的数量。递归函数的终止条件是当当前节点为叶子节点时,返回1。如果当前节点有子节点,则将左右子节点的叶子节点数目相加即可。

最后,我们使用main函数创建了以上树形结构,输出该结构中叶子节点的数目。运行该程序,输出结果为:叶子节点数目为:8。

  
  
下一篇: Node.js删除文件

评论区

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