Структури от данни и алгоритми - Домашно 4 | (2015г.)
Пращането на дървета за Коледа се превръща в истински проблем за пощенските служители – всеки иска да прати своето дърво на приятел. След обстоен анализ на пратите служителите забелязали че голяма част от дърветата които се пращат имат еднаква структура и се различават само по стойностите на елементите във възлите си, което веднага ги навело на мисълта че ще могат значително да намалят работата си ако могат да разберат кога две дървета имат еднаква структура (или както се изразявали математиците за да звучат по-важно – кога са изоморфни). Тъй като служителите си имат друга работа, а и не разбират много от тия неща, решили като да бъдат добри хора (за да заслужат подаръци все пак) да прехвърлят камъка във вашата градина като ви накарат да напишете програма, която по зададени две дървета решава дали те са изоморфни. Две дървета са изоморфни ако всеки съответен възел в двете дървета започвайки от корена има еднакъв брой наследници, или по- просто казано ако графичното представяне на дърветата като граф е едно и също, като не се интересувате от самите стойности във възлите и подредбата в братството. Така например изоморфни са дърветата:
5 7
/ \ / \
9 1 15 3
/ | \ / | \
4 12 42 7 10 8
Дърветата ще са представени като символни низове по следния начин:
(<стойност в корена> {<наследници>})
Съответното представяне на първото дърво е:
(5 {(9 {}) (1 {(4 {}) (12 {}) (42 {})})})
Напишете програма, която прочита от командния ред два символни низа – описващи две дървета и извежда на екрана YES или NO в зависимост дали съответните дървета са изоморфни или не.