[数据结构与算法]DS二叉树--叶子数量

题目描述
计算一颗二叉树包含的叶子结点数量。

提示：叶子是指它的左右孩子为空。

建树方法采用“先序遍历+空树用0表示”的方法，即给定一颗二叉树的先序遍历的结果为AB0C00D00，其中空节点用字符‘0’表示。则该树的逻辑结构如下图。

输入

第一行输入一个整数t，表示有t个测试数据

第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出

逐行输出每个二叉树的包含的叶子数量

样例输入

3
AB0C00D00
AB00C00
ABC00D00E00

样例输出

2
2
3

?

#include <iostream>
#include <string>
using namespace std;
class BitNode{
public:
	char data;
	BitNode*lchild,*rchild;
}; 
class Bitree{
public:
	BitNode*root;
	int pos;
	int flag;
	string str1;
	Bitree(string str){
		str1=str;
		flag=0;
		pos=0;
		root=createTree();
	}
	BitNode*createTree(){
		char ch=str1[pos];
		pos++;
		if(ch=='0'){
			return NULL;
		}
		else{
			BitNode*b=new BitNode();
			b->data=ch;
			b->lchild=createTree();
			b->rchild=createTree();
			return b;
		}
	}
	void getLeaf(BitNode *b){
		if(b!=NULL){
			if(b->lchild==NULL&&b->rchild==NULL){
				flag++;
			}
			getLeaf(b->lchild);
			getLeaf(b->rchild);
		}
	}
};
int main(){
	int t;
	cin>>t;
	while(t--){
		string str;
		cin>>str;
		Bitree b(str);
		b.getLeaf(b.root);
		cout<<b.flag<<endl;
	}
}