Вказівки
Змініть батьківський вузол дерева на вибраний вузол.
Дерево - це особливий тип графа, у якому всі вузли зʼєднані, але немає циклів.
Це означає, що для будь-якої пари вузлів існує рівно один шлях від одного вузла до іншого.
Ця вправа присвячена переорієнтації дерева, щоб побачити речі з іншої точки зору.
Наприклад, родинні дерева зазвичай подають з погляду предка:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
Але в дереві немає притаманного йому напрямку.
Ту саму інформацію можна подати з погляду будь-якого іншого вузла дерева, піднявши його до кореня й потягнувши за собою всі його звʼязки.
Отже, те саме дерево з погляду вузла 6 мало б такий вигляд:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
Це дає змогу простіше описати шляхи між двома вузлами.
Наприклад, шлях 6-9 (який у першому дереві йде вгору до кореня, а потім униз до іншого листка) можна побачити як шлях 6-2-0-3-9.
Ця вправа полягає в тому, що ми беремо дерево на вході та переорієнтовуємо його з погляду одного з вузлів.
Примітки щодо реалізації
Тестова програма створює дерева шляхом повторного застосування варіативної функції New.
Наприклад, інструкція
tree := New("a",New("b"),New("c",New("d")))
будує таке дерево:
"a"
|
-------
| |
"b" "c"
|
"d"
Можна припустити, що в тестових деревах не буде повторюваних значень.
Тестова програма використовуватиме методи Value і Children, щоб розібрати дерева.
Базове створення та розбір дерева мають працювати, перш ніж ми візьмемося за найцікавішу частину вправи, тож їх перевіряють окремо в перших трьох тестах.
Методи FromPov і PathTo - це найцікавіша частина вправи.
Метод FromPov приймає рядок тексту (англ. string) як аргумент from, який задає вузол у дереві через його значення.
Він має повернути дерево зі значенням from у корені.
Можна змінити початкове дерево й повернути його або створити нове дерево й повернути його.
Якщо ми повертаємо нове дерево, то можемо вільно використати або знищити початкове.
Звісно, краще залишити його без змін.
Метод PathTo приймає два рядки тексту як аргументи from і to, які задають два вузли в дереві через їхні значення.
Він має повернути найкоротший шлях у дереві від першого вузла до другого.
