SDUT 잎사귀 문제

1824 단어

데이터 구조 실험의 두 갈래 나무 7: 잎 문제


Time Limit: 1000MS Memory limit: 65536K


제목 설명


abd,eg,,,,cf,,, (그 중에서 빈 결점을 나타냄) 와 같은 선순으로 입력된 문자 서열을 알고 있습니다.이 두 갈래 나무를 세우고 위에서 아래로 왼쪽에서 오른쪽으로 순서대로 이 두 갈래 나무의 모든 잎사귀 결점을 출력하십시오.

입력


 
입력 데이터가 여러 줄로 되어 있으며, 각 줄은 길이가
오십
문자열

출력


 
위에서 아래로 왼쪽에서 오른쪽으로 두 갈래 나무의 잎사귀 결점을 출력합니다.

예제 입력

abd,,eg,,,cf,,,
xnl,,i,,u,,

예제 출력

dfg
uli

힌트


 

출처


 xam

예제 프로그램


 
#include<bits/stdc++.h>
using namespace std;
struct Tree
{
    char c;
    Tree *L,*R;
};
Tree* Creat()
{
    Tree *p=new Tree;
    p->L=NULL;
    p->R=NULL;
    return p;
}
int num;
char s[10000],ss[10000];
Tree * Build(Tree* root,int r)
{
    if(num>r)
        return 0;
    if(s[num]==',')
        return 0;
    root=Creat();
    root->c=s[num];
    num++;
    root->L=Build(root->L,r);
    num++;
    root->R=Build(root->R,r);
    //if(!root->L&&root->R)  // 
    //ans++;
    return root;
}
int BFS(Tree *root)
{
    queue<Tree*>Q;
    Q.push(root);
    while(!Q.empty())
    {
        Tree* p=Q.front();
        Q.pop();
        if(!p)
            return 0;
        //printf("%d",p->c);// 
        if(p->L)
            Q.push(p->L);
        if(p->R)
            Q.push(p->R);
        if(!p->L&&!p->R)
            printf("%c",p->c);
    }
}
int main()
{
    while(~scanf("%s",s))
    {
        num=0;
        int len=strlen(s);
        Tree* root=Creat();
        root=Build(root,len-1);
        BFS(root);
        printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기