Trees 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 /** 题目：Trees on the level UVA - 122 链接：https://vjudge.net/problem/UVA-122 题意：lrj算法竞赛入门经典P150. eg6-7 分析： 建造一颗二叉树。链表或者数组方式。 本题不可以数组方式，因为节点个数达到256个，当为一条链的时候，2^256超大。 采用树结构。 收获：复习二叉树的建立，使用。 sscanf和strchr的使用。 sscanf(&s[1],"%d",&value);表示把一个字符串当做输入，输入到后面"%d",&value中读取。 strchr(s,',')表示返回s串中第一次出现','的指针。 */ #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> P; const int maxn = 1e5+100; const int mod = 1e9+7; int sign; /// 1 表示同一节点重复出现过。 struct node { int value; int exist;/// 1 表示存在。 node *left, *right; node():exist(0),left(NULL),right(NULL){} }; char s[100005]; char out[]="not complete"; node* root = new node(); void dfs(int value,char *s) { node* u = root; for(int i = 0; s[i]!='\0'; i++){ if(s[i]=='L'){ if(u->left==NULL) u->left = new node(); u = u->left; }else { if(s[i]=='R'){ if(u->right==NULL) u->right = new node(); u = u->right; }else { if(u->exist==1) sign = 1; u->value = value; u->exist = 1; } } } } vector<int> ans; void bfs() { node* u = root; queue<node*> qu; ans.clear(); qu.push(u); while(!qu.empty()){ u = qu.front(); qu.pop(); if(u->exist==0){ sign = 1; break; } ans.push_back(u->value); if(u->left!=NULL){ qu.push(u->left); } if(u->right!=NULL){ qu.push(u->right); } } if(sign){ cout<<out<<endl; return ; } int len = ans.size(); printf("%d",ans[0]); for(int i = 1; i < len; i++){ printf(" %d",ans[i]); } cout<<endl; } int main() { while(scanf("%s",s)!=EOF) { int value; if(strcmp(s,"()")==0) continue; root = new node(); sign = 0; sscanf(&s[1],"%d",&value); dfs(value,strchr(s,',')+1); //@Test //sscanf(&s[1],"%d",&value); //cout<<"value = "<<value<<endl; while(scanf("%s",s)!=EOF){ if(strcmp(s,"()")==0){ bfs(); break; } sscanf(&s[1],"%d",&value); dfs(value,strchr(s,',')+1); } } return 0; }