Д. Кнут - Искусство программирования том 1 (1119450), страница 92
Текст из файла (страница 92)
Если узел МОВЕ(Ц) имеет непустое правое поддерево, рассмотрим Ц = эР, Цэ = Р в верхних схемах; узел МОВЕ(Цэ) является крайним слева узлом этого правого поддерева. Если узел МОВЕ(Ц) имеет пустое правое поддерево, рассмотрим Ц = Р в нижних схемах. Наконец, чтобы определить положение узла МОВЕ(Цэ), следует перемещаться вверх по дереву до первой возможности перейти вправо Предложите подобное "интуитивное" правило для поиска места расположения узла МОВЕ(Ц*) в бинарном дереве по отношению к узлу МОВЕ(Ц). ь 17. [22] Предложите алгоритм, аналогичный алгоритму Б, для определения Р* в прошитом бинарном дереве. Предпатагается, что дерево имеет заголовок списка, как в (8)-(10).
18. [Ед] Во многих алгоритмах работы с деревьями каждый узел может посещаться не один раз, а деааюдм за счет комбинации прямого и симметричного порядка, который называется двойным порядком(даиИе агдег). Обход бинарного дерева в двойном порядке определяется так: если бинарное дерево пусто., ничего делать не надо.
В противном случае необходимо а) посетить корень (первый раз); Ъ) пройти левое поддерево в двойном порядке; с) посетить корень (во второй раз); с() пройти правое поддерево в двойном порядке. Например,после обхода дерева (1) в двойном порядке получим последовательность А~ В~ Р1РэВэАгС! Е1ЕэС1СэСгР) Нь НэГг 3~ .Уз, где А~ означает, что А посещается впервые. Если Р указывает на узел дерева и д = 1 или 2, положим (Р,д) = (Ц,е), если следующим шагом в двойном порядке после посещения узла МОВЕ(Р) в И-й рэз является посещение узла мООК(О) и е-й раз; или, если (Р,Н) является последним шагом в двойном порндке, запишем (Р,Н) = (НЕАО, 2).
где НЕАΠ— это адрес заголовка списка. Предположим также, что (НЕАН, 1) являдтся первым шагом в двойном порядке. Предложите алгоритм, аналогичный алгоритму Я, для обхода бинарного дерева в двойном порядке, а также предложите алгоритм, аналогичный алгоритму Б, для вычисления (Р, 4) . Рассмотрите связь между этими алгоритмами и алгоритмами из упр. 12 и 17. Ь ь 19.
[27) Предложите алгоритм, аналогичный алгоритму Я, для вычисления Рг (а) в правопрошитом бинарном дереве; (Ь) в полностью прошитом бинарном дереве. Постарайтесь написать такой алгоритм, среднее время выполнения которого для произвольного узла дерева Р было бы мало, насколько возможно.
20. [ЯЯ] Измените программу Т так, чтобы стек использовался в ней в виде связанного списка, а не в виде последовательно расположенных ячеек памяти. ь 21. [УУ] Создайте алгоритм обхода непрошитого бинарного дерева в симметричном порядке без использоеанил еспомогатпельноге стеке. При этом допускается произвольное изменение содержимого полей ЬЕЕМК и Н.1МК в узлах дерева во время его обхода при условии, что данное бинарное дерево имеет обычное представление (2) как да, так и после выполнения алгоритма обхода. Причем в узлах дерева нельзя использовать никакие другие биты. 22.
[20] Создайте программу для компьютера М1Х для реализации алгоритма из упр. 21 и сравните время ее выполнения со временем выполнения программ Я и Т. 23. [ЯЯ] Предложите алгоритм, аналогичный алгоритму 1, для вставки узла справа и слева в праеепрешитохг бинарном дереве.
Предположим, что узлы содержат поля 1.1.1МК, НПМК и НТАО. 24. [МЕО] Будет ли справедлива теорема А, если узлы деревьев Т и Т' располагаются не в прямом, а в симметричном порядке? 25. [М24] Пусть Т вЂ” множество бинарных деревьев, з — множество полей !п1о, которые содержатся в узлах этих деревьев, причем 5 является линейно упорядоченным на основе отношения» (см. упр. 2.2.3-14). Определим отношение Т» Т' для любых деревьев Ти Т' из множества Т тогда и только тогда, когда 1) Т пусто; либо 11) Т и Т' не пусты и !п(о(гоо!(Т))»!пЕо(гоо!(Т')); либо ш) Т и Т' не пусты, 1п(о(гоо!(Т)) = !пЕа(гоос(Т')), 1ей(Т)» !ей(Т') и 1ей(Т) не эквивалентно !ей(Т'); либо гк) Т и Т' не пусты, 1п(о(гоо!(Т)) = !пЕо(гоос(Т')), !е(1(Т) эквивалентно !ей(Т') и ИНЬ (Т) г!ЯЬ!(Т ), Здесь !ей(Т) и г1КЬЕ(Т) обозначают соответственно левое и правое поддеревья дерева Т, а гоос(Т) — корень дерева Т, Докажите, что (а) нз Т» Т и Т» Тл следует Т» Тл; (Ь) Т эквивалентно Т' тогда и только тогда, когда Т» Т' н Т' » Т; (с) для любого Т, Т' из множества 7 имеет место либо Т» Т, либо Т'» Т, [Таким образом, если эквивалентные деревья множества Т рассматриваются как равные, то отношение» порождает линейное упорядочение множества Т.
Это упорядочение имеет много приложений (например, для упрощения алгебраических выражений). Если Я содержит только один элемент, т. е. паля 1п(о всех элементов одинаковы, имеет место особый случай, когда эквивалентность равно- сильна подобию.] 26. [М24] Рассмотрим упорядочение Т » Т', определенное в предыдущем упражнении. Докажите теорему, аналогичную теореме А, которая дает необходимое и достаточное усло- вие, что Т» Т', а также использует понятие двойного порядка обхода, которое определено в упр. 18. ь 27. [22] Предложите алгоритм для проверки отношения двух деревьев Т и Т' (либо Т -с Т', либо Т ы Т', либо Т эквивалентно Т') на основании отношения, определенного в упр, 25, предполагая, что оба.бинарных дерева являются правопрошитыми.
Предположим, что каждый узел имеет поля 1.ЫМК, Ы,1МК, КТАС, 1МГО, а вспомогательный стек не используется. 28. [00] Копия бинарного дерева, полученного с помощью алгоритма С, будет эквиваленгпна исходному дереву или подобна ему? 29. [М25] Предложите наиболее строгое доказательство справедливости алгоритма С. ь 30. [22) Предложите алгоритм прошивки непрошитого дерева, который, например, преобразует (2) в (10). Замечаное.
По возможности используйте обозначения типа Рв и Рг вместо повторения шагов алгоритмов обхода наподобие алгоритма Т. 31. [22) Предложите алгоритм, который "стирает" правопрошитое бинарное дерево. Он должен возвратить все узлы дерева, за исключением заголовка списка, в список свободных ячеек АУА1Е, причем заголовок списка отвечает пустому бинарному дереву. Предположим, что узел имеет поля ВЫМЕ, Ы.1МК, КТАС, а вспомогательный стек не используется. 32. [21] Предположим, что каждый узел бинарного дерева имеет четыре поля связи: ВЫМЕ и КЫМК, которые указывают на левое и правое поддеревья или Л, как и в иепрошитом дереве, а такясе 300 и РЕЕВ, которые указывают на предшественника и последователя узла в симметричном порядке.
(Значит, ЕОС(Р) = Рг и РЕЕВ(Р) = гР. Такое дерево содержит больше информации, чем прошитое дерево.) Создайте алгоритм, подобный алгоритму 1, для вставки в такое дерево. е 33. [20) Существует более одного способа прошивки дерева! Рассмотрим следующее представление, используя три поля ).ТАС, ГЫМК, Ы.1МК в каждом узле: ЕТАС(Р): определяется так же, как и в прошитом бинарном дереве: ЕЫМК(Р): всегда равно Р*; Ы.1МК(Р): определяется так же,как и в непрошитом бинарном дереве. Обсудите алгоритмы вставки для такого представления и предложите для данного представления алгоритм копирования (т, е,алгоритм С) с подробным описанием. 34.
[22) Пусть Р указывает на узел в некотором бинарном дереве, а НЕА — на заголовок списка в пустом бинарном дереве. Предложите алгоритм, который (!) удаляет узел МОВЕ(Р) и все его поддеревья из любого дерева, а также (й) присоединяет узел МОВЕ(Р) и его поддерево к МОВЕ(НЕАО) . Предположим, что все рассматриваемые бинарные деревья прошиты справа с полями ЕЫМК, КТАС, КЫМК в каждом узле. 35. [40] Дайте определение шрайнаго дерева(гегаагу ггее) (а в более общем случае — б арного дерева для произвольного 1 > 2), аналогичное определению бинарного дерева, и исследуйте воэможность обобщения для барных деревьев результатов, полученных в этом разделе и в упраяснениях после него, 36. [М22] В упр. 1.2.1-15 показано, что лексикографический порядок расширяет полное упорядочение множества Я до полного упорядочения множеств из п элементов множества Я.
В приведенном выше упр. 25 показано, что линейное упорядочение данных в узлах дерева может быть расширено до линейного упорядочения деревьев на основе аналогичного определения, Если отношение с приводит к полному упорядочению множества 5, то является ли расширенное отношение из упр. 25 полным упорядочением набора Т? ь 37.
[24] (Задача Д. Фергюсона.) Если два слова в памяти компьютера обязательно должны содержать два поля связи и поле 1МРО с данными, то в таком случае для представления дерева типа (2) с и узлами потребуется 2п слов. Создайте схему представления бинарных деревьев, для которой в памяти компьютера потребовалось бы выделить меньшее количество слов, предполагая, что одна связь и одно пале 1МГ0 с данными могут уместиться в одном слове.
2.3.2. Представление деревьев в виде бинарных деревьев Перейдем от бинарных деревьев к деревьям общего вида. Напомним следующие основные различия между деревьями и бинарными деревьями. 1) Дерево всегда имеет корень, т. е. оно никогда не бывает пустым; каждый узел может иметь О, 1, 2, 3, ... детей. 2) Бинарное дерево может быть пустым, а кахсдый его узел может иметь О, 1 или 2 детей; мы будем различать левых и правых детей. Напомним также, что лес является упорядоченным набором некоторого количества деревьев (и даже равного нулю).
Поддеревья любого узла дерева образуют лес. Существует естественный способ представления любого леса в виде бинарного дерева. Рассмотрим следующий лес, состоящий из двух деревьев: Соответствующее бинарное дерево получим за счет связывания детей каждой семьи и удаления всех вертикальных связей, за исключением связи с родителем первого ребенка. Затем, наклонив зту схему под углом 43' и слегка откорректировав расположение узлов, получим такое бинарное дерево: И наоборот, после выполнения этих действий в обратном порядке становится очевидно,что любое бинарное дерево соответствует единственному лесу деревьев. Приведение схемы (1) к схеме (3) имеет чрезвычайно большое значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
