タイトル1523:ツリーを上から下へ印刷

タイトル説明:ツリーの各ノードを上から下に印刷し、同層ノードを左から右に印刷します.入力:入力には複数のテストサンプルが含まれ、入力はEOFで終了します.各テストケースについて、入力する最初の行の整数n(1<=n<=1000、:nは入力するツリー要素の個数(ノード1から番号付け)を表します.次の行には、i番目のツリーノードの要素の値を表すn個の数字があります.次はn行で、各行に1文字Ciがあります.Ci=’d’は,i番目のノードに2人の子があり,次いで左の子番号と右の子番号であることを示す.Ci=’l’は、i番目のノードに左の子があり、左の子の番号が続くことを示す.Ci=’r’は、i番目のノードに右の子があり、右の子の番号が続くことを示す.Ci=’z’はi番目のノードに子供がいないことを示す.出力:各テストケースに対応して、ツリーノードの値を上下に左から右に印刷します.サンプル入力:7 8 6 5 7 10 9 11 d 2 5 d 3 4 z z z d 6 7 zサンプル出力:8 6 10 5 7 11

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class Main {

       public static void main(String[] args) throws IOException {

              PrintWriter cout = new PrintWriter(System.out)  ;


              while(Cin.hashNext()){
                     new Task().solve(Cin.Int() , cout) ;
              }
              cout.flush() ;
       }


}


class  Task{

       Node[] node ;
       int[]  id ;

       void solve(int n , PrintWriter cout) throws IOException{
            node = new Node[n+1] ;
            id = new int[n+1] ;
            for(int i = 1 ; i <= n ; i++){
                id[i] = Cin.nextInt()  ;
                node[i] = new Node() ;
            }

            int u , v ;

            for(int i = 1 ; i <= n ; i++){
                  String s = Cin.nextString() ;
                  if(s.equals("d")){
                            u = Cin.nextInt() ;
                            v = Cin.nextInt() ; 
                            node[i].left = u ;
                            node[i].right = v ;
                            node[u].father = node[v].father = i ;
                  }
                  else if(s.equals("l")){
                            u = Cin.nextInt() ;
                            node[i].left = u ;
                            node[u].father  = i ;
                  }
                  else if(s.equals("r")){       
                            v = Cin.nextInt() ;
                            node[i].right = v ;
                            node[v].father = i ;
                  }
            }

            int root = -1 ;
            for(int i = 1 ; i <= n ; i++){
                 if(node[i].father == -1) root = i ;
            }

            List<Integer> answer = new ArrayList<Integer>() ;
            Queue<Integer> que = new  LinkedList<Integer>() ;
            que.add(root) ;
            while(! que.isEmpty()){
                  u = que.poll() ;
                  answer.add(u) ;
                  if(node[u].left != -1) que.add(node[u].left) ;
                  if(node[u].right != -1) que.add(node[u].right) ;
            }
            cout.print(id[answer.get(0)]) ;
            for(int i = 1 ; i < answer.size() ; i++) cout.print(" " + id[answer.get(i)] ) ;
            cout.println() ;

       }

}


class  Node{
       int father ;
       int left , right ;
       Node(){
           father = -1 ;
           left = right = -1 ;
       }
}


class  Cin{
       static StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in)) ; 

       static boolean hashNext() throws IOException{
              return  cin.nextToken() != cin.TT_EOF ;
       }

       static int nextInt() throws IOException{
              cin.nextToken() ;
              return (int)cin.nval ;
       }

       static int Int() throws IOException{
              return (int)cin.nval ;
       }

       static String nextString() throws IOException{
              cin.nextToken() ;
              return (String)cin.sval ;
       }
}