PRoblem Description

已知二叉樹的一個(gè)按先序遍歷輸入的字符序列，如abc,,de,g,,f,,, (其中,表示空結(jié)點(diǎn))。請建立二叉樹并求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)。

Input

連續(xù)輸入多組數(shù)據(jù)，每組數(shù)據(jù)輸入一個(gè)長度小于50個(gè)字符的字符串。

Output

輸出二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)。

Example Input

abc,,de,g,,f,,,
Example Output
3
#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct node{    char data;    struct node *lc,*rc;}bitree;int i=-1;int ans;bitree * pre_create(char str[]){    bitree *t;    if(str[++i]!=',')    {        t=(bitree *)malloc(sizeof(bitree));        t->data=str[i];        t->lc=pre_create(str);        t->rc=pre_create(str);    }    else    {        t=NULL;    }    return t;}void pre_show(bitree * t){    if(t)    {        if(t->lc==NULL&&t->rc==NULL)        {            ans++;        }        pre_show(t->lc);        pre_show(t->rc);    }}int main(){    char str[101];    bitree * tree;    while(scanf("%s",str)!=EOF)    {        i=-1;        ans=0;        tree=pre_create(str);        pre_show(tree);        printf("%d/n",ans);    }    return 0;}