题目如下：Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes.
In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k+1.
For example, a level order traversal of the tree
is: 5, 4, 8, 11, 13, 4, 7, 2, 1.
In this problem a binary tree is specified by a sequence of pairs (n,s) where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of L's and R's where L indicates a left branch and R indicates a right branch. In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once.
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node
{
int lch,rch,val;
bool b;
}a[],n1,n2;
int n,ans[];
int rd()
{
int i,j,k,p,x,y,z,rt;
char s[],c1,c2;
memset(a,,sizeof(a));
n=;
if (scanf("%s",s)==-) return ;
rt=;
while ()
{
if (s[]==')') break;
x=;
for (i=;s[i]!=',';i++)
x=x*+s[i]-'';
p=;
for (i=i+;i<=strlen(s)-;i++)
if (s[i]=='L')
{
if (!a[p].lch) a[p].lch=++n;
p=a[p].lch;
}
else
{
if (!a[p].rch) a[p].rch=++n;
p=a[p].rch;
}
if (a[p].b) rt=-;
a[p].val=x;
a[p].b=;
scanf("%s",s);
}
return rt;
}
queue<int> q;
int main()
{
int i,j,k,l,m,p,x,y,z;
bool b;
while ()
{
x=rd();
if (!x) break;
if (x==-)
{
printf("not complete\n");
continue;
}
while (!q.empty()) q.pop();
q.push();
memset(ans,,sizeof(ans));
k=b=;
while (!q.empty())
{
n1=a[q.front()];
q.pop();
if (!n1.b)
{
b=;
break;
}
ans[++k]=n1.val;
if (n1.lch) q.push(n1.lch);
if (n1.rch) q.push(n1.rch);
}
if (b)
printf("not complete\n");
else
{
printf("%d",ans[]);
for (i=;i<=k;i++)
printf(" %d",ans[i]);
printf("\n");
}
}
}
如果直接用数组下标表示位置，那么当所有节点连成一条线的时候下标将变得很大。所以需要在每个节点记录他的左右儿子位置，这样可以节省空出来的空间。
每个节点用一个bool记录是否被赋过值，如果没被赋过值或是被赋第二次值，那就not complete了。
但是注意的细节就是由于多组数据，即使读入时已经知道not complete也要读完。