Вказівки
Змініть батьківський вузол дерева на вибраний вузол.
Дерево - це особливий тип графа, у якому всі вузли зʼєднані, але немає циклів.
Це означає, що для будь-якої пари вузлів існує рівно один шлях від одного вузла до іншого.
Ця вправа присвячена переорієнтації дерева, щоб побачити речі з іншої точки зору.
Наприклад, родинні дерева зазвичай подають з погляду предка:
+------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.
Ця вправа полягає в тому, що ми беремо дерево на вході та переорієнтовуємо його з погляду одного з вузлів.
Примітки щодо реалізації
Обʼєкт дерева має два атрибути:
-
String label
-
List<Tree> children
Тестова програма створює дерева повторним застосуванням функції-будівника
Tree.of. Наприклад, інструкція
Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));
створює таке дерево:
"a"
|
-------
| |
"b" "c"
|
"d"
Можемо припустити, що в тестових деревах не буде однакових значень.
Методи FromPov і PathTo - найцікавіша частина вправи.
Метод FromPov приймає рядковий аргумент from, який задає вузол у дереві
через його значення. Він має повернути дерево зі значенням from у корені.
Можемо змінити початкове дерево й повернути його або створити нове дерево й
повернути його. Якщо ми повертаємо нове дерево, можемо вільно використати чи
знищити початкове дерево. Звісно, краще залишити його без змін.
Метод PathTo приймає два рядкові аргументи from і to, які задають два
вузли в дереві через їхні значення. Він має повернути найкоротший шлях у дереві
від першого вузла до другого.
Повідомлення винятків
Іноді потрібно кинути виняток.
Коли ми робимо це, завжди варто додати змістовне повідомлення про помилку, щоб указати, у чому джерело помилки.
Це робить код читабельнішим і суттєво допомагає з налагодженням.
У цій конкретній вправі потрібно використати ключове слово throw,
щоб «кинути» кілька UnsupportedOperationException, якщо класу Tree() передано дерево, яке неможливо переорієнтувати, або якщо між start node та end node не вдається знайти шлях.
Тести пройдуть, лише якщо ми і викинemo exception за допомогою throw, і додамо до нього повідомлення.
Щоб кинути UnsupportedOperationException з повідомленням, запишіть повідомлення як аргумент типу exception:
// when a tree cannot be oriented to a new node POV
throw new UnsupportedOperationException("Tree could not be reoriented");
// when a path cannot be found between a start and end node on the tree.
throw new UnsupportedOperationException("No path found");
