Preorder Perusal

Pythonで書きたい欲求を抑え、Rubyで書く。
Rubyの構造体をとりあえず使ってみたが、別に使う必要はなかったかもしれない。

Tree=Struct.new("Tree",:left,:right)

def run
  t={}
  STDIN.gets.to_i.times do 
    l,r = STDIN.gets.rstrip.split(" ")
    if !t.has_key?(l)
      t[l]=Tree.new(r) #left
    else
      t[l].right=r
    end
  end  
  tr(t,t.keys[0])
end

def tr(t,k)
  puts k
  tree=t[k]

  if tree.nil?
    return
  end

  unless tree.left.nil?
    tr(t,tree.left)
    unless tree.right.nil?
      tr(t,tree.right)
    end
  end
end

STDIN.gets.to_i.times { run }

---

Given a binary tree, we want to perform a preorder traversal. A preorder traversal is defined as follows. Suppose the tree looks like this, where (left) and (right) are subtrees:

      Root
      /     \
 (left)   (right)

1. Print the root
2. Print the elements in (left), if any, using preorder traversal
3. Print the elements in (right), if any, using preorder traversal

The first line of the input will be an integer N (1 <= N <= 1000), indicating the number of test cases.

Each test case consists of one line containing an integer K (1 <= K <= 100), followed by K lines containing two space-separated strings A and B, representing that B is a child node of A. When A has two children, the left one will always be given first. Each test case is defined such that the tree has only one root.

For each test case, print out the node names in preorder, one per line. No blank line between test cases.

Sample Input/Output

1
6
A C
A F
C B
C D
F E
F G

A
C
B
D
F
E
G