Экзамен

Осень прошла, зима наступает, и листва покинула множество деревьев главного городского парка. В этот период многие впадают в депрессию, включая студента Василия, так как ему предстоит сдать экзамен в конце года, а экзамен этот по теме «структуры данных», к которым в частности относятся и деревья. Пожалуйста, помогите ему подготовиться к экзамену, написав простую программу.

N-арное дерево – это дерево, степень каждого узла которого не превосходит N. Бинарные (двоичные) деревья – это частный случай n-арного дерева при n=2.

Существует красивый способ представить любое n-арное дерево с помощью бинарного. Речь идет о так называемом (FC-NS)-представлении (First Child – Next Sibling). Каждый узел такого дерева слева ссылается на потомка (или на NIL), а справа ссылка осуществляется на брата (узел с общим предком). Пусть Par(N) – функция, возвращающая предка для N, либо NIL в том случае, когда N – корень. Таким образом, узлы N и S – братья, если Par(N)=Par(S).

Будем обозначать узлы дерева ASCII-символами '0'-'9', 'a'-'z', 'A'-'Z'. Пусть Val(N) – функция, возвращающая ASCII-код символа, обозначающего узел. Определим также функцию FC(N), возвращающую первого потомка для N (либо NIL при отсутствии такового). Аналогично определим функцию NS(N), которая будет возвращать следующего брата за узлом N.

FC(N) – это потомок Сi с наименьшим значением Val(Ci) для всех потомков,

NS(N) – такой брат Si, с наименьшим Val(Si) для всех Val(Si)>Val(N).

Ниже рассмотрим пример 3-арного дерева и его бинарного (FC-NS)-представления, полученное в результате вышеупомянутых рассуждений:

                      1                                           1
                     /|\                                          |
                    / | \                                         2-3-4
                   /  |  \                                        |   |
                  2   3   4                                       5-6 7
                 / \       |                                          |
                5   6      7                                          8-9
                          / \								
                         8   9								

                3-арное дерево	                      Бинарное (FC-NS)-представление

Ваша задача по заданному дереву построить бинарное (FC-NS)-представление и вывести его в виде псевдографической схемы по правилам, описанным ниже.

Входные данные

Первая строка входного файла INPUT.TXT содержит P – количество узлов заданного множества деревьев (их может быть более одного). Далее следуют P строк, содержащие пары ASCII-символов ('0'-'9', 'a'-'z', 'A'-'Z'), разделенные пробелом. Первый из них – узел потомка, второй – узел предка. Родительский узел корневого узла обозначен символом '-'. Никакие узлы не повторяются дважды. Различные узлы обозначаются различными символами.

Выходные данные

В выходной файл OUTPUT.TXT выведите заданное множество деревьев в бинарном (FC-NS)-представлении. Первая строка должна содержать корневые узлы деревьев, следующие в порядке возрастания ASCII-кодов по одному из нижеизложенных правил построения:

1. Корневой узел первого дерева должен располагаться в первой строке, в самой левой позиции.
2. FC(N) (если не NIL) должен печататься под узлом N, разделяясь вертикальной линией '|'.
3. NS(N) (если не NIL) должен печататься справа от узла N, разделяясь одним или несколькими символами '-'.
4. Узлы одного уровня (с равным расстоянием от корня) всегда должны располагаться в одной строке.
5. Никакие два символа не должны соприкасаться, они должны отделяться либо горизонтальной, либо вертикальной линией.
6. Никакие два символа не должны пересекаться (печататься один на другом), все должны быть видимыми.
7. Количество символов при выводе должно быть минимальным (не должно быть лишних пробелов и лишних пропусков с использованием линий).

Просим учесть, что утверждение 7 не следует из примеров, приведенных ниже.

Примеры

1
|
2-3-4
|   |
5-6 7
    |
    8-9

Примечание

Первый пример содержит дерево, описанное в тексте задания.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]