Обектно-ориентирано програмиране 2004/05 - упражнения и практикум

Задача 1. Дадено е двоично дърво. Да се намери огледалния му образ (фиг. 1).

Фиг.1

Задача 2. Дадено е двочино дърво. Ниво i в дървото наричаме множеството от върховете му, които се намират на разстояние i от корена. Да се дефинира функция, която намира произволно ниво в дадено дърво (фиг. 2).

Фиг.2

Задача 3. Дадени са две двоични дървета A и B . Дървото А наричаме по-малко от B , ако е празно или ако има същия като B корен, а поддърветата му са по-малки от съответните поддървета на B . Да се дефинира функция, която проверява дали едно дърво е по-малко от друго (Фиг. 3).

Фиг.3

Задача 4. Като се използва и без да се използва задача 3, да се дефинира функция, която проверява дали две дървета съвпадат.

Задача 5. Дадено е двоично дърво от естествени числа. Да се дефинира функция, която намира максималния сбор от числа, който може да се получи по даден път от корена на дървото до негово листо (за празното дърво приемаме, че този сбор е 0) . За Фиг. 4 този сбор е 30.

Фиг. 4

Задача 6. Дадено е двоично дърво. Да се намери множество от върхове на дървото, които лежат на някой най-дълъг път между корена на дървото и негово листо (един път наричаме по-дълъг от друг, ако съдържа повече върхове). Например за дървото от Фиг. 4 такова множество е {10,11,2,7} както и {10,11,2,5}.

Задача 7. От конзолата се въвежда правилен израз от вида:

<израз> ::= <число> | ( sp <израз> sp < операция > sp < израз> sp)

< операция > ::= + | - | * | /

където sp обозначава интервал. Да се дефинира функция, която намира еднозначно представяне на такъв израз с двоично дърво и друга функция, която по такова дърво намира стойноста на дадения израз. Например за израза “( 20 + ( 17 * ( 7 / 5 ) ) ) “ такова дърво е например дървото на Фиг. 5

Фиг.5