rees are fundamental in many branches of computer science (Pun definitely intended). Current state-

of-the art parallel computers such as Thinking Machines’ CM-5 are based on

fat trees

. Quad- and

octal-trees are fundamental to many algorithms in computer graphics.

This problem involves building and traversing binary trees.

Given a sequence of binary trees, you are to write a pro-

gram 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 on the right

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.

Input

The input is a sequence of binary trees specified as described above. Each tree in a sequence consists

of several pairs ‘

(

n

,

s

)

’ as described above separated by whitespace. The last entry in each tree is ‘

()

’.

No whitespace appears between left and right parentheses.

All nodes contain a positive integer. Every tree in the input will consist of at least one node and

no more than 256 nodes. Input is terminated by end-of-file.

Output

For each completely specified binary tree in the input file, the level order traversal of that tree should

be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a

node is given a value more than once, then the string ‘

not complete

’ should be printed.

Sample Input

(11,LL) (7,LLL) (8,R)

(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

(3,L) (4,R) ()

Sample Output

5 4 8 11 13 4 7 2 1

not complete

 

分析：建树，搜索。

AC代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
using namespace std;

struct Node{
    bool have_value;
    int v;
    Node *left,*right;
    Node():have_value(false),left(),right(){}
};
Node *root;
bool failed;

Node* newnode() {return new Node();}

void addnode(int v,char *s){
    int n = strlen(s);
    Node* u = root;
    for(int i = 0;i < n;i++)
    if(s[i] == 'L'){
        if(u->left == NULL) u->left = newnode();
        u = u->left;
    }
    else if(s[i] == 'R'){
        if(u->right == NULL) u->right = newnode();
        u = u->right;
    }
    if(u->have_value) failed = true;
    u->v = v;
    u->have_value = true;
}

char s[257];
bool read_input(){
    failed = false;

    root = newnode();
    for(;;){
        if(scanf("%s",s) != 1) return false;
        if(!strcmp(s,"()")) break;
        int v;
        sscanf(&s[1],"%d",&v);
        addnode(v,strchr(s,',')+1);
    }
    return true;
}

bool bfs(vector<int>& ans){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front();q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        if(u->left != NULL) q.push(u->left);
        if(u->right != NULL) q.push(u->right);
    }
    return true;
}
int main()
{
    while(1)
	{
		root = newnode();
		if (!read_input())break;
		vector<int>ans;
		if (!failed&&bfs(ans))
		{
			int len = ans.size();
			for (int i = 0; i < len; i++)
				printf("%d%c", ans[i], i == len - 1 ? '\n' : ' ');
		}
		else puts("not complete");
	}
    return 0;
}