Background背景

Trees are fundamental in many branches of computer science. 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.各種樹（數據結構）是許多計算機分支學科的基礎。當下最快的并行計算機——比如思維機CM-5——就是建立在一種稱之為“胖樹”（fat trees）的架構上的。而四叉樹和八叉樹又是許多計算機圖形學算法的基礎。

This PRoblem involves building and traversing binary trees.本問題是關于建立和遍例二叉樹的。

The Problem問題

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.給定一個二叉樹序列，你要寫一個程序將每棵樹按層序訪問并打印出來。在這個問題中，二叉樹的每個節都值都為正整數，且每棵樹的節點數都小于256。

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.在層序遍例一個樹時，指定行中所有的結點應按照從左至右的順序打印，并且在第k行打印完之后才能打印第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.在本問題中，二叉樹是由一系列的二元組(n, s)給出的，其中n是節點的值，s是由根到該節點的路徑字符串。路徑字符串由一系列的“L”和“R”組成，L代表左子樹，R代表右子樹。在上圖所示二叉樹中，值為13的節點由(13, RL)表示，值為2的節點由(2, LLR)表示。根節點由(5,)表示，其中空的路徑字符串表示的路徑就是由根到根。當一個二叉樹中，所有從根到節點（已給出的）的路徑上的所有的節點都已給出且只給出一次，那么這個二叉樹就認為是完整的定義。

The 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.

輸入是一組按照上文所述給出的二叉樹定義。序列中的每棵樹都包含數個二元組(n, s)，分別以空格隔開。每棵樹的最后是()。所有的左右括號中間都不存在空格。

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.所有節點的值都為正整數。輸入的每棵樹都包括至少一個節點，且不會超過256個節點。輸入由EOF表示結束。

The 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.對于輸入的每行完整定義的二叉樹，都要按層序遍例并打印。如果一棵樹沒有完整的定義，即一些節點沒有給出其值，或是一個節點重復給出，則應該打印出字符串“not complete”。

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

步驟:

1.輸入

2.建樹

3.層序遍歷

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.Vector;public class Main {	public static Scanner scan = new Scanner(System.in);	public static Node root;// 二叉樹根節點	public static Boolean fail = false;//看建樹是否成功	public static void main(String[] args) {				while(scan.hasNext()){			root = new Node();			read_input();			Vector<Integer> v = new Vector<>();			if(!fail&&bfs(root,v)){				String str = "";				for(int i:v){					str += i+" ";				}				System.out.println(str.trim());			}else{				System.out.println("not complete");			}					}	}	//層序遍歷	public static boolean bfs(Node root, Vector<Integer> v) {		Queue<Node> q = new LinkedList<Node>();		q.add(root);		while (!q.isEmpty()) {			Node u = q.poll();			if (!u.is_have)				return false;			v.add(u.v);			if (u.left != null)				q.add(u.left);			if (u.right != null)				q.add(u.right);		}		return true;	}		//輸入數據	public static boolean read_input() {		fail = false;		while (true) {			String str = scan.next();			if ("()".equals(str))				break;			int index = str.indexOf(',');			int v = Integer.valueOf(str.substring(1, index));			String dis = str.substring(index + 1, str.length() - 1);			addNode(v, dis);//建樹		}		return true;	}	//建樹	public static void addNode(int v, String dis) {		int n = dis.length();		Node u = root;		for (int i = 0; i < n; i++) {			if (dis.charAt(i) == 'L') {				if (u.left == null) {					u.left = new Node();				}				u = u.left;			} else {				if (u.right == null) {					u.right = new Node();				}				u = u.right;			}		}		if (u.is_have == false) {			u.v = v;			u.is_have = true;		} else {			fail = true;		}	}	//樹節點	static class Node {		int v;		boolean is_have;//是否已經被賦值		Node left, right;		public Node() {			is_have = false;			left = null;			right = null;		}	}}