1.问题描述：
输入一棵二叉树，求出其叶子结点个数
2.要求：
（1）设计二叉树的存储结构
（2）设计求叶子结点个数的递归算法
（3）用户输入的一串先序遍历字符串为二叉树节点
（4）输出二叉树的叶子节点个数
示例：
输入先序遍历的二叉树节点：abc##de#g##f###
二叉树叶子结点个数为：3
树的原型：
这一题有两种思路：
1.左右子树递归查找（dfs）
2.广度优先遍历查找（bfs）文章来源：https://www.toymoban.com/news/detail-765090.html
下面代码展示来两种不同方法：文章来源地址https://www.toymoban.com/news/detail-765090.html
#include<iostream>
#include<queue>
using namespace std;
string str;//先序遍历字符串
int i = 0;//下标
typedef char DataType;//树中数据类型
typedef struct TreeNode {
DataType val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(DataType data) :val(data), left(NULL), right(NULL) {};
}TNode;
TNode* Create_Tree() {
char ch = str[i++];
if (ch == '#') return NULL;//说明节点为空 返回上一级函数
TNode* root = new TNode(ch);//创建根节点
root->left = Create_Tree();//创建左子树
root->right = Create_Tree();//创建右子树
return root;
}
//递归左右子树查找叶子结点
int Tree_LeafSize1(TNode* root) {
if (!root) return 0;//如果节点为空 叶子结点0 返回上一级函数
if (!root->left && !root->right) return 1;//满足叶子结点条件 叶子结点为1 返回上一级函数
return Tree_LeafSize1(root->left) + Tree_LeafSize1(root->right);//递归遍历左右子树
}
//广度优先遍历查找叶子结点
int Tree_LeafSize2(TNode* root) {
int res = 0;
queue<TNode*> Q;
Q.push(root);
while (!Q.empty()) {
TNode* t = Q.front();
Q.pop();
if (t->left) Q.push(t->left);
if (t->right) Q.push(t->right);
if (!t->left && !t->right) res++;//叶子结点
}
return res;
}
int main() {
cin >> str;//输入先序遍历字符串
TreeNode* root = Create_Tree();//构建二叉树
cout<<"Tree_LeafSize1:" << Tree_LeafSize1(root)<<endl;//3
cout<<"Tree_LeafSize2:" << Tree_LeafSize2(root);//3
return 0;
}abc##de#g##f###
Tree_LeafSize1:3
Tree_LeafSize2:3到了这里，关于二叉树叶子结点个数统计（两种思路）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
