Boring Homework
Professor Z. always gives his students lots of boring homework. Last week, after explaining binary search trees (BSTs), he asked his students to draw a picture of BST according to the list of numbers inserted into the tree sequentially. Maryanna spent so much time playing the game ”Starcraft II” that she can’t finish her homework in time. She needs your help.
A binary search tree, which may sometimes also be called ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key. • Both the left and right subtrees must also be binary search trees.
–from Wikipedia
To draw a picture of BST, you may follow the rules listed below:
- The picture of a 1-node BST, whose size is 1*1, is a single ’o’ (15th small Latin letter).
- If a BST has a non-empty subtree, draw a single ’|’ just above the subtree’s root, and a single ’+’ just above previous drawn ’|’. Finally, in the row of ’+’, use the least number (including 0) of ’-’s to connect ’+’ (denoting the left subtree and right subtree) and ’o’ (denoting the parent node of the subtree)
- The left subtree (if exists) must be drawn on the left side of its parent. Similarly, the right subtree (if exists) must be drawn on the right side of its parent.
- The column of the BST’s root must not contain any character from left subtree or right subtree.
- Any column containing any characters from BST’s left subtree must not contain any characters from BST’s right subtree, and vice versa. That is, for a node of the BST, the picture of its left subtree and the picture of its right subtree do not share common columns in the picture of the whole tree.
The sample output may give a clear clarification about the format of the picture.
Input
The first line contains T (T ≤ 2500), the number of test cases. T lines follow. Each line contains a positive integer N (N < 80), followed by N integers - a permutation of 1 to N. The permutation indicates the insert order for the BST.
Output
For each test case:
Output the case number counting from 1 in the first line. The next lines should be the image
described above without any trailing spaces. See the sample for more format details.
Note: Notice that no trailing whitespaces after the last visible characters of each line are allowed.
2/2 Sample Input
3
3312 6456132 534521
Sample Output
Case #1:
+-o
|
o+
|
o
Case #2: +--o+ || o-+ o+
|| +o o |
o
Case #3: +o+
|| +o o+ || oo