Trees are common in computer science and in the business world: search trees, inheritance diagrams,
organization charts, etc. Anytime we work with trees, we inevitably end up wanting to draw pictures
of them. In this problem, you will write a method that draws textual pictures of trees. For example,
here is a sample picture of the kind that you will draw:
ALICE
|
BOB-------CONROY
| |
DENISE-EDITH FRANCINE
|
GILBERT-HARRY
Notice that every node has a label that is a sequence of one or more uppercase letters ('A'-'Z').
Sibling nodes are connected by dashes ('-'), and each parent node is connected to its children by
a single vertical bar ('|'). Nodes are limited to at most two children.
For example,
in the above picture, "BOB" has two children but "CONROY" has only one child (all quotes for clarity
only).
The layout of a picture is controlled by the following rules:
- A child node is always drawn two rows below its parent.
- Within a row, nodes are drawn from left to right in the same order that they appear in the input. (See below for the format of the input.)
- Sibling nodes are separated by one or more dashes ('-'). Adjacent non-sibling nodes in the same row are separated
by one or more spaces (' ').
- The vertical bar ('|') connecting a parent to its children is drawn directly below the middle character of the parent's label and
directly above the character midway between the first character of the first child's label and the last character of the last
child's label. When the middle of the parent's label and/or the children's labels falls between characters, the vertical bar
is aligned with the character immediately to the left of the true center.
- Sibling nodes are drawn as close together as possible without violating Rules 1-4. Placing siblings lower in
the tree close together takes precedence over siblings higher in the tree (see Example 1).
A tree will be specified by a String in the following format:
<tree> = <label> "[" <treelist> "]"
<treelist> = "" | <tree> | <tree> <tree>
<label> = one or more uppercase letters
Note that spaces in the grammar are for clarity only, and do not appear in the input.
In words, a tree is written as the label of its root followed by its subtrees in square brackets.
For example, a one-node tree with the label "FRED" would be written "FRED[]" while a three-node tree with labels "ROOT", "LEFTCHILD", and "RIGHTCHILD" would be written "ROOT[LEFTCHILD[]RIGHTCHILD[]]".
The tree drawn above would be written
"ALICE[BOB[DENISE[]EDITH[]]CONROY[FRANCINE[GILBERT[]HARRY[]]]]"
In practice, the written form of a tree may be too long to fit comfortably in a single String.
The actual input will be a String[] tree. However, you should think of all the elements of
tree as being concatenated together. For example, the written form of the tree drawn above might be
input as the String[]
{ "ALICE[BOB[DENISE[]EDITH[]]CONR",
"OY[FRANCINE[GILBERT[]HARRY[]]]]" }
Given the String[] tree, you are to generate and return a rectangular String[] containing
the picture of the tree.
Pad each row on the front and/or back with spaces as needed to make the return value rectangular, but be careful to
maintain the alignment of your picture. Your picture should not contain any rows or columns that are entirely spaces.
|