Description
计算一颗二叉树包含的叶子结点数量。
提示：叶子是指它的左右孩子为空。
建树方法采用“先序遍历+空树用0表示”的方法，即给定一颗二叉树的先序遍历的结果为AB0C00D00，其中空节点用字符‘0’表示。则该树的逻辑结构如下图。
Input
第一行输入一个整数t，表示有t个测试数据
第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行
Output
逐行输出每个二叉树的包含的叶子数量
Sample Input
3
AB0C00D00
AB00C00
ABC00D00E00
Sample Output
2
2
3
#include<iostream>
#include<string>
using namespace std;
struct BiNode
{
char data;
BiNode *lchild, *rchild;
};
class BiTree
{
public:
BiTree( );
~BiTree(void);
BiNode* Getroot();
void PreOrder(BiNode *root);
void leaf(BiNode *root,int &n);
private:
BiNode *root;
BiNode *Creat( );
void Release(BiNode *root);
};
BiTree::BiTree( )
{
root = Creat( );
}
BiTree::~BiTree(void)
{
Release(root);
}
BiNode* BiTree::Getroot( )
{
return root;
}
void BiTree::PreOrder(BiNode *root)
{
if(root==NULL) return;
else{
cout<<root->data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
void BiTree::leaf(BiNode *root,int &n)
{
if(root)
{
if(root->lchild==NULL&&root->rchild==NULL)
n++;
leaf(root->lchild,n);
leaf(root->rchild,n);
}
}
BiNode* BiTree::Creat( )
{
BiNode *root;
char ch;
cin>>ch;
if (ch=='0') root = NULL;
else{
root = new BiNode;
root->data=ch;
root->lchild = Creat( );
root->rchild = Creat( );
}
return root;
}
void BiTree::Release(BiNode *root)
{
if (root!= NULL){
Release(root->lchild);
Release(root->rchild);
delete root;
}
}
int main()
{
int i,m;
cin>>m;
for(i=0;i<m;i++)
{
BiTree bt;
BiNode *root = bt.Getroot( );
int n=0;
bt.leaf(root,n);
cout<<n;
cout<<endl;
}
return 0;
} |
|
转播
