Дерево - 2
(Время: 1 сек. Память: 16 Мб Сложность: 51%)
Катя решила разместить на стене комнаты свое родословное дерево из фотографий. В корне дерева она повесила свою фотографию. Фотографии мамы и папы – это левое и правое поддеревья. И так далее… Катя повесила на стену фотографии всех родственников, которых она знала, полюбовалась на свою работу, и ушла гулять.
Пока Кати не было, её брат Антон решил вставить фотографии в рамочки. Для этого он решил снять фотографии. Сначала он слева-направо снял все фотографии, которые являются листьями дерева (лист - это вершина, у которой нет поддеревьев.) Снятые портреты Антон сложил в стопку и перенес к себе в комнату. Затем вернулся в комнату Кати и повторил процедуру. В конце концов на стене остался только портрет Кати. Антон перенес и этот портрет к себе.
И вот тут Антон понял, что восстановить дерево по оставшимся у него стопкам портретов он не может! Помогите Антону восстановить дерево! Вам должны помочь буквенные обозначения, которыми Катя пометила все узлы дерева. Каждый узел удовлетворяет следующим условиям:
- буквы всех узлов левого поддерева в алфавитном порядке идут перед буквенным обозначением текущего узла,
- буквы всех узлов правого поддерева в алфавитном порядке идут после буквенного обозначения текущего узла.
На рисунке показан пример дерева, а также последовательность действий Антона.
Удаление узлов с данными:
BDHPY
CM
GQ
K
Входные данные
Входной файл INPUT.TXT содержит нескольких строк, где каждая строка содержит буквенные обозначения удаленных узлов. Последняя строка теста содержит знак «*». Гарантируется, что в дереве есть хотя бы один узел. Число узлов дерева не превосходит число символов английского алфавита. Каждая буква в тесте встречается только один раз.
Выходные данные
В выходной файл OUTPUT.TXT выведите структуру дерева в следующем формате: сначала корень дерева, потом данные левого поддерева, потом данные правого поддерева.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | BDHPY
CM
GQ
K
* | KGCBDHQMPY |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|