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

Description

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

Input

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

Output

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

Sample

Input

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

Output

dfg
uli

Hint

 1 #include<iostream>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 struct Tnode
 6 {
 7     char d;
 8     Tnode *l,*r;
 9 };
10 char st[60];
11 int i;
12 Tnode *CreatTree()
13 {
14     Tnode *p;
15     if(st[i++]==',')
16         p= NULL;
17     else
18     {
19         p=new Tnode;
20         p->d=st[i-1];
21         p->l=CreatTree();
22         p->r=CreatTree();
23     }
24     return p;
25 }
26 void level_order(Tnode *p)  //层次遍历
27 {
28     queue<Tnode *>q;
29     if(p!=NULL)
30         q.push(p);
31     while(!q.empty())
32     {
33         p=q.front();
34         if(!p->l&&!p->r)
35             cout<<p->d;
36         q.pop();
37         if(p->l)
38             q.push(p->l);
39         if(p->r)
40             q.push(p->r);
41     }
42 }
43  
44  
45 int main()
46 {
47     while(cin>>st)
48     {
49         i=0;
50         Tnode *Tree=CreatTree();
51         level_order(Tree);
52         cout<<endl;
53     }
54     return 0;
55 }
56