统计二叉树的叶结点个数
根据带虚结点的先序序列建立二叉树，计算其叶子结点的数目后输出。
输入格式:
测试数据有多组，处理到文件尾。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列，其中字符*表示虚结点（对应的子树为空）。
输出格式:
对于每组测试，输出所建立的二叉树的叶子结点数目。输出格式为：“leaf:num”，其中num 为二叉树的叶结点个数。
输入样例:
HDAC*BGFE**
-+axb-cd/ef
输出样例:
leaf:3
leaf:6
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
解题代码
#include<bits/stdc++.h>
using namespace std;
string str;
int len=0;
template<class T>
class Tree{
public:
Tree(){
root=NULL;
}
struct treeNode{
T data;
treeNode *L_child,*R_child;
treeNode(T d){
data=d;
}
};
treeNode *root;
treeNode* createNode()
{
treeNode *t;
if(len>=str.size()){
return NULL;
}
T data = str[len++];
if(data=='*'){
t=NULL;
}else{
t=new treeNode(data);
t->L_child=createNode();
t->R_child=createNode();
}
return t;
};
int findLeaf(treeNode *root);
};
template<class T>
int Tree<T>::findLeaf(treeNode *root)
{
int ans = 0;
if(root==NULL) return 0;
if(!root->L_child&&!root->R_child){
return 1;
}
return ans+findLeaf(root->L_child)+findLeaf(root->R_child);
}
int main()
{
while(cin>>str){
len=0;
Tree<char> *tree = new Tree<char>();
tree->root=tree->createNode();
cout<<"leaf:"<<tree->findLeaf(tree->root)<<endl;
}
}
解题思路
就是按照先序遍历的顺序创建二叉树，这里的话HDAC*BGFE**
先序遍历，那么就是H是根节点，然后遇到D，因为是先序遍历，中-左-右，所有D在的左子树且为根节点，然后A在D的左子树，那么存入后，继续递归，然后后面遇到了*号证明A的左子树和右子树都为NULL，此时A遍历存储结束，返回D，D的左子树也遍历完了，那么C就是D的右子树，遇到星号，那么C的左子树是NULL，以此类推吧，这里的代码和前面那题很像，可以参考
https://blog.csdn.net/weixin_44546342/article/details/124576839?spm=1001.2014.3001.5502
