Динамические структуры данных. Алексеев А.Ю - 63 стр.

                             3.6. Упражнения

    При выполнении упражнений следует использовать варианты реализации
бинарного дерева (см.3.5), указанные преподавателем.
    Для представления деревьев во входных данных рекомендуется использо-
вать скобочную запись, кроме случаев, специально оговоренных в условии за-
дачи. В выходных данных рекомендуется представлять дерево (лес) в гори-
зонтальном виде (т.е. с поворотом на 90°), а бинарные деревья - в виде
уступчатого списка.
    В заданиях 1 - 3 предлагается реализовать как рекурсивные, так и не ре-
курсивные процедуры (функции); в последнем случае следует использовать
стек и операции над ним (см. разд.2).
    1. Задано бинарное дерево b типа BT с типом элементов Elem. Для введен-
ной пользователем величины E (var E: Elem):
    а) определить, входит ли элемент Е в дерево b;
    б) определить число вхождений элемента Е в дерево b;
    в) найти в дереве b длину пути (число ветвей) от корня до ближайшего уз-
ла с элементом Е (если Е не входит в b, за ответ принять -1).
    2. Для заданного бинарного дерева b типа BT с произвольным типом эле-
ментов:
    а) определить максимальную глубину дерева b, т.е. число ветвей в самом
длинном из путей от корня дерева до листьев;
    б) вычислить длину внутреннего пути дерева b, т.е. сумму по всем узлам
длин путей от корня до узла;
    в) напечатать элементы из всех листьев дерева b;
    г) подсчитать число узлов на заданном уровне n дерева b (корень считать
узлом 1-го уровня);
    д) определить, есть ли в дереве b хотя бы два одинаковых элемента.
    3. Заданы два бинарных дерева b1 и b2 типа BT с произвольным типом
элементов. Проверить:
    а) подобны ли они (два бинарных дерева подобны, если они оба пусты, ли-
бо они оба непусты и их левые поддеревья подобны и правые поддеревья по-
добны);
    б) равны ли они (два бинарных дерева равны, если они подобны и их соот-
ветствующие элементы равны);
    в) зеркально подобны ли они (два бинарных дерева зеркально подобны,
если они оба пусты, либо они оба непусты и для каждого из них левое подде-
рево одного подобно правому поддереву другого);
    г) симметричны ли они (два бинарных дерева симметричны, если они
зеркально подобны и их соответствующие элементы равны).
    4. Задано бинарное дерево b типа ВТ с произвольным типом элементов.
Используя очередь и операции над ней (см.п.2), напечатать все элементы де-

                                    63