AOP_Tom1 (1021736), страница 94
Текст из файла (страница 94)
9. [М20] Сколько раз выпал!»яются шаги Т1 — Тб при обходе бинарного дерева с и узлами согласно алгоритму Т в зависимости от и? ь 10. [20[ Какое максимальное количество элементов может находиться в стеке во время выполнения алгоритма Т при работе с деревом с и узлами? (Ответ на этот вопрос очень важен при распределении памяти, когда стек располагается в последовательных ячейках памяти.) 11.
[НМ41[ Найдите среднее значение для наибольшего размера стека при выполнении алгоритма Т в зависимости от числа узлов и при условии, что все бинарные деревья с п узлами рассматриваются как равновероятные. 12. [22[ Напишите алгоритм, аналогичный алгоритму Т, который совершает обход бинарного дерева в прямом порядке, и докажите его корректность. ь 13. [24) Напишите алгоритм, аншюгичный алгоритму Т, который совершает обход бинарного дерева в обратном порядке,и докажите его корректность. 14.
[22[ Покажите, что если бинарное дерево с и узламн имеет вид (2), то общее количество Л-связей в таком представлении можно выразить с помощью простой функции от и. Эта функция не зависит от формы дерева 15. [15[ В прошитом представлении дерева (10) каждый узел, за исключением заголовка списка, имеет в точности одну связь, которая указывает на нее сверху вниз, а именно— связь от родителя этого узла. Некоторые узлы также имеют связи, которые указывают на них снизу вверх. Например, узел С имеет два указателя, направленных на него снизу вверх, а узел Š— только один.'- Существует ли простая зависимость между количеством связей, указывающих на данный узел, и другими основными свойствами узла? (Это нужно для того, чтобы при изменении структуры дерева знать количество связей, указывающих на узел.) ь 16.
[22[ Схемы, представленные на рис 24, позволяют предложить следующие интуитивно понятные правила расположения узла МОВЕ(Цг) в бинарном дереве по отношению к узлу МОВЕ(Ц). Если узел МОВЕ(Ц) имеет непустое правое поддерево, рассмотрим Ц = гр, Цг = Р в верхних схемах; узел МОВЕ(Цг) является крайним слева узлом этого правого поддерева. Если узел МОВЕ (Ц) имеет пустое правое поддерево, рассмотрим Ц = Р в нижних схемах. Наконец, чтобы определить положение узла МОВЕ(цг), следует перемещаться вверх по дереву до первой возможности перейти вправо Предложите подобное "интуитивное" правило для поиска места расположения узла МОВЕ(Ц*) в бинарном дереве по отношению к узлу МОВЕ(Ц).
ь 17. [22] Предложите алгоритм, аналогичный алгоритму Я, для определения Ря в прошитом бинарном дереве. Предполагается, что дерево имеет заголовок списка,как в (8)-(10). 18. [24[ Во многих алгоритмах работы с деревьями каждый узел может посещаться не один раз, а деаждь за счет комбинации прямого и симметричного порядка, который называется двойным порядком(доиб(е огдег). Обход бинарного дерева в двойном порядке определяется так если бинарное дерево пусто,ничегоделать не надо.
В противном случае необходимо а) посетить корень (первый раз); Ь) пройти левое поддерево в двойном порядке; с) посетить корень (во второй раз); Й) пройти правое поддерево в двойном порядке. Например, после обхода дерева (1) в двойном порядке получим последовательность АгВ~РгРгВгАгС~ЕгЕгСгСгСгЕгН~НгГгд~ дг, где Аг означает, что А посещается впервые.
Если Р указывает на узел дерева и д = 1 или 2, положим (Р,д) = (Ц,е), если следующим шагом в двойном порядке после посещения узла МОВЕ(Р) в д-й рвз является посещение узла НННЕ(Я) в е-й раз; или, если (Р, Н) является последним шагом в двойном порядке, запишем (Р,Н) = (НЕАН, 2), где ННАР— это адрес заголовка списка. Предположим также, что (НЕАР, 1) является первым шагом в двойном порядке.
а Предложите алгоритм, аналогичный алгоритму Я, для обхода бинарного дерева в двойном порядке, а также предложите алгоритм, аналогичный алгоритму Б, для вычисления (Р, ы) . Рассмотрите связь между этими алгоритмами и алгоритмами из упр. 12 и 17. о ь 19. [Я?] Предложите алгоритм, аналогичный алгоритму Б, для вычисления Р! (а) в правопрошитом бинарном дереве: (Ъ) в полностью прошитом бинарном дереве. Постарайтесь написать такой алгоритм, среднее время выполнения которого для произвольного узла дерева Р было бы малб, насколько возможно. 20, [йу] Измените программу Т так, чтобы стек использовался в ней в виде связанного списка, а не ввиде последовательно расположенных ячеек памяти.
ь 21. [53] Создайте алгоритм обхода непрошитого бинарного дерева в симметричном порядке без использования вспомогательного сшека. При этом допускается произвольное изменение содержимого полей ШНК и НЮ1НК в узлах дерева во время его обхода при условии, что данное бинарное дерево имеет обычное представление (2) как до, так и после выполнения алгоритма обхода. Причем в узлах дерева нельзя использовать никакие другие биты. 22.
[25] Создайте программу для компьютера Н1К для реализации алгоритма из упр. 21 и сравните время ее выполнения со временем выполнения программ Я и Т. 23. [23] Предложите алгоритм, аналогичный алгоритму 1, для вставки узла справа и слева в праеопрошигиам бинарном дереве. Предположим, что узлы содержат поля ЬЬ1НК, НЬ1НК и АТАС. 24. [М20] Будет ли справедлива теорема А, если узлы деревьев Т и Т' располагаются не в прямом, а в симметричном порядке? 23. [Мйэ'] Пусть Т вЂ” множество бинарных деревьев, 5 — множество полей !п1о, которые содержатся в узлах этих деревьев, причем Я является линейно упорядоченным на основе отношения» (см.
упр. 2,2.3-14). Определим отношение Т» Т' для любых деревьев Ти Т' из множества Т тогда и только тогда, когда Ц Т пусто;либо Н) Т и Т' не пусты и !п(о(гоо!(Т))» !п(о(гоог(Т')); либо 'ш) Т и Т' не пусты, !п(о(гоо!(Т)) = !п(о(гоос(Т')), 1ей(Т)» 1ей(Т') и !ей(Т) не эквивалентно !еЕ!(Т'); либо !ч) Т и Т' не пусты, !пЕо(гоо!(Т)) = !пЕо(гоо!(Т')), !ей(Т) эквивалентно 1ей(Т') и г!НЬ!(Т)» г!НЬЕ(Т'). Здесь 1ей(Т) и г!КЬ!(Т) обозначают соответственно левое и правое полдеревья дерева Т, а гоо!(Т) — корень дерева Т. Докажите, что (а) из Т» Т' и Т' » Т" следует Т» Т"; (Ь) Т эквивалентно Т' тогда и только тогда, когда Т» Т' н Т' » Т; (с) для любого Т, Т' из множества Т имеет место либо Т» Т', либо Т' » Т.
[Таким образом, если эквивалентные деревья множества Т рассматриваются как равные, то отношение» порождает линейное упорядочение множества Т. Это упорядочение имеет много приложений (например, для упрощения алгебраических выражений). Если Я содержит только один элемент, т. е. поля 1п(о всех элементов одинаковы, имеет место особый случай, когда эквивалентность равно. сильна подобию.] 26, [мвз] Рассмотрим упорядочение т» т', определенное в предыдущем упражнении.
Докажите теорему, аналогичную теореме Ао которая дает необходимое и достато шое условие,что Т » Т', а также использует понятие двойного порядка обхода, которое определено в упр. 13. ь 27. [22[ Предложите алгоритм длн проверки отношения двух деревьев Т и Т' (либо Т ч Т', либо Т м Т', либо Т эквивалентно Т') на основании отношения, определенного в упр. 25, предполагая, что оба.бинарных дерева являются правопрошитымн. Предположим, что каждый узел имеет поля ШИК, Ю1ИК, ЕТАС, 1МРО, а вспомогательный стек не используется. 28. [00) Копия бинарного дерева, полученного с помощью алгоритма С, будет эквивалентна исходному дереву или подобна ему? 29. [М25[ Предложите наиболее строгое доказательство справедливости алгоритма С.
ь 30. [22] Предложите алгоритм прошивки непрошитого дерева, который, например, преобразует (2) в (10). Замечание. По возможности используйте обозначения типа Рь и Рз вместо повторения шагов алгоритмов обхода наподобие алгоритма Т. 31. [22[ Предложите алгоритм, который "стирает" правопрошнтое бинарное дерево.
Он должен возвратить асе узлы дерева, за исключением заголовка списка, в список свободных ячеек АЧА11, причем заголовок списка отвечает пустому бинарному дереву. Предположим, что узел имеет поля ШМК, 351ИК, КТАС, а вспомогательный стек не используется. 32. [21) Предположим, что каждый узел бинарного дерева имеет четыре поля связи: ШИК и Ы,1МК, которые указывают на левое и правое поддеревья или Л, как и а непрошитом дереве, а также 300 и РКЕО, которые указывают на предшественника и последователя узла в симметричном порядке. (Значит, 30С(Р) = Рв и РЕЕР(Р) = зР. Такое дерево содержит больше информации, чем прошитое дерево.) Создайте алгоритм, подобный алгоритму 1, для вставки в такое дерево. ь 33.
[ЯО[ Существует более одного способа прошивки дерева! Рассмотрим следующее представление, используя три поля БОТАС, Ь11ИК, Ы.1ИК в каждом узле, ЕТАС(Р): определяется так же, как и в прошитом бинарном дереве; 1Л.1ИК(Р): всегда равно Рь; КЫИК(Р): определяется так же,как и в непрошитом бинарном дереве. Обсудите алгоритмы вставки для такого представления н предложите для данного представления алгоритм копирования (т.
е. алгоритм С) с подробным описанием. 34. [22[ Пусть Р указывает на узел в некотором бинарном дереве, а НЕАΠ— на заголовок списка в пустом бинарном дереве. Предложите алгоритм, который (1) удаляет узел МОСЕ(Р) и все его поддеревья из любого дерева, а также (И) присоединяет узел МОСЕ(Р) н его поддерево к ИОВЕ(НЕАО). Предположим, что все рассматриваемые бинарные деревья прошиты справа с полями 111МК, КТАС, Ж.1ИК в каждом узле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
