数据结构实验之二叉树七：叶子问题

数据结构实验之二叉树七：叶子问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem De ion

已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立该二叉树并按从上到下从左到右的顺序输出该二叉树的所有叶子结点。

Input

 输入数据有多行，每一行是一个长度小于50个字符的字符串。

Output

 按从上到下从左到右的顺序输出二叉树的叶子结点。

Sample Input

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

Sample Output

dfg
uli

题目链接：

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2711/pid/3346

#include <bits/stdc++.h>

using namespace std;

int top;
char str[51];

typedef struct treenode{
    char s;
    struct treenode *leftnode;
    struct treenode *rightnode;
}node;

node *create()
{
    top++;
    node *root;
    if(str[top]==\',\')
    return NULL;
    else
    {
        root=new node;
        root->s=str[top];
        root->leftnode=create();
        root->rightnode=create();
    }
    return root;
}

void leave(node *root)
{
    int in=0,out=0;
    node *dl[66];
    dl[in++]=root;
    while(in>out)
    {
        if(dl[out])
        {
            if(!dl[out]->leftnode&&!dl[out]->rightnode)
            cout << dl[out]->s;
            dl[in++]=dl[out]->leftnode;
            dl[in++]=dl[out]->rightnode;
        }
        out++;
    }
    cout << endl;
}

int main()
{
    while(cin >> str)
    {
        top=-1;
        node *root=create();
        leave(root);
    }
    return 0;
}