AOP_Tom1 (1021736), страница 157
Текст из файла (страница 157)
2. Первые два дерева в ответе к упр. 1 идентичны, как ориентированные деревья, поэтому получим 9 различных возможностей. Общий случай рассматривается в разделе 2.3.4.4, в котором доказана справедливость формулы и" 3. Часть !. Покажем, что существует ио крайней мере одна такая последовательность. Пусть дерево содержит и узлов. Решение в случае, когда и = 1, очевидно, так как Х является корнем. Если и > 1, согласно определению предполагается, что существует корень Х» и поддеревья Т», Тг,...,Тпб либо Х = Хм либо Х является членом какого-то единственного поддерева Т,.
В последнем случае по индукции существует путь Хг,, Х, где Лг является корнем поддерева Т„и, так как Хг — родитель Хг, получим путь Хг, Хг,..., Х. Часть 2. Покажем, что существует не более одной такой последовательности. Докажем по индукции, что, если Х не является корнем дерева, Х имеет единственного родителя (так что узел Х» определяет узел Х» и который определяет узел Х» г, и т. д.). Если дерево имеет один узел, доказательство очевидно; иначе Х находится в единственном поддереве Т,. Либо Л' является корнем Т, и по определению узел Х имеет единственного родителя, либо Х не является корнем Т, и в этом случае узел Х по индукции имеет единственного родителя Т,, причем никакой другой узел за пределами поддерева Т, не может быть родителем узла Х.
4. Верно (к сожалению). 5. 4. 8. Пусть родитель1~~(Х) = Х и пусть родитель'"»О(Х) = родитель(родителей~(Х)), так что родительй1(Х) является родителем узла Х. а родительр~(Х) — прародителем узла Х. Когда А > 2, родитель[»~(Х) является пра» прародителем Л. Искомое условие родства заключается в том, что родительр"»О(Х) = родительй"'"Р О(1'), но родитель~~~(Х) родитель~ +'~(1'). Если п > О, это условие несимметрично по отношению к Х и 1', хотя оно считается симметричным в повседневных ситуациях. 7. Используйте несимметричное условие из упр. б и учтите тот факт, что родитель 1(Х) ~ родитель~ ~(1'), если г или )г (или оба сразу) равны — 1.
Чтобы показать, что это отношение Р! всегда истинно для единственного значения ги и единственного значения и, рассмотрим десятичную систему обозначений Дьюи для Х и У, а именно — 1.а|..ар.бг..б„и 1.аг .. ар.сг ..с„где р > О, 7 > О, г > О и Ьг ф с| (егли уг ф О). В таком виде можно переписать обозначения для любой пары узлов, а потому, очевидно, следует принять, что т = »» — 1 и т + п = г — 1 8. Нп одно бинарное дерево не является деревом Это совершенно разные понятия не»мотря на то что схема непустого бинарного дерева очень положа на дерево 9. Кор»»ел» является узел А, поскозьку лорень обычно располагается сверху 10. Любой конечный набор вложенных множегтв можно сопоставить с лесом, определенным выше' Пусзь А»,А — множества данного набора, которые не содержатся ни в каких других мноя естваз Для фиксированного 1 совокупность всех множеств, которые содер,катся в А», является вло кенной, следовательно, можно допустить, что зта совокупность соответствует дереву, не упорядоченно»»у с множеством А» в качестве корня 11.
Пусть во вложенном наборе С отношение Х = У выпозняется, если существует такое Я Е С что Х О 1' С Я Очевидно, что это отношение рефлексивно и симметрично, а также фактически является отношением эквивалентности, поскольку И' ш Х и Х = г подразумевает, чго существуют такие Я» и Я» в наборе С с И' С г», Х С г» Г» г, и 1 С гэ Так как Ъ »» Ез ~ О, то либо У» С х,,либо Я С Я», следовательно, В'»» У' С а» О Яг Е С Теперь, если С ивляезся вложенным набором, определим соответствующий набору С ориентированный зес согласно правилу "Х является предком 1, а У вЂ” потомком Л тогда и тозько тогда, когда Х Э 1 ' Каждый класс эквивалентности набора С соответствует ориентированному дереву, которое яв зяется ориентированным лесом с отношением Х эз У для всех Х, 1 (Такил» образом, мы обобщили определения леса и дерева, которые ранее были даны только дзя конечных наборов ) На основе атил рассчждений можно определить уровень множества Х каь кардинальное число множества предков (Х) Аналогично степень множества Х является кардинальным числом классов эквивалентности во вложенном наборе потомков (Х) Назовеч Х родителем 1', а У' --.
сыном (дочерью) Х, если Х является предком 1, но не сэ ществует таких Я, что Х Э Я З К (Х может иметь потомков, которые не явзяются его детьми, или иметь предков, которые не являются его Родителями ) Для упорядочения деревьев и леса некоторым специальным образом зададим порядок среди упомянутых выше классов эквивалентности, например, расширив отношение С до понятия линейного порядка, как в упр 2 2 3-14 Пример (а) П»гть 5„» = (х ! х = д»д»дз в десятичной системе обозначений, где а = е»глез в десятичной системс обозна.»ений и д, = е», егли» пюд 2 Зл О) НабоР л С = (Яь» ) у > О. О < а < 1) является вложенным и соответствует дереву с бесконечныл» количеством уровней н несчетной степенью каждого узла Примеры (Ь) и (г) В таком слзчае удобно рассматривать это множество на плоскости, вместо того чтобы использовать действительные числа, к тому же мея ду плоскостью и множествоч дейгтвизельных чисел счществует взаимно однозначное соответствие Пусть Я „= ((о,у) ~ т/2" < у < (т+1)/2") и пусть Т = ((х,у) ) х < с») Легко видеть, что набор С = (5 ( О < а < 1, и > О, О < гп < 2") Л» (Т ! О < а < 1) является вложенным Детьми множества Я ат являются 5»э»»„~»» и Я»» ~»д„т»М а множество Т имеет ребенка 5 оо плюс поддерево (оэ„,„( /1 < о) О (Тэ ! /1 < о) Таким образом, каждый узел обладает степенью 2 и имеет несчетное множество предков вида Т Это построение предложено Р Г Байглоу (Е В»яе!оъ) Замечание Данное построение можно усовершенствовать, если подходящим образом упорядочить множество действительных чисел и определить Ть = ((х, у) ) х м о), получая в результате вложенный набор, в котором ка кдый узел имеет несчетный уровень, степень 2 и двоих детей 12.
Для того чтобы обеспечить соответствие зеса частично упорядоченному множеству, наложим на него дополнительное ограничение (аналогично "вложенным множествам") если х ~ у и х < х, то либо у < х, лабо х -< у Иначе говоря элементы, которые больше данного элемента, являются линейно упорядоченными. Для получения дерева также следует предположить существование такого наибольшего элемента г, что я .( г для всех ж Доказательство трго факта, что в результате получится определенное выше неупорядоченное дерево, если число узлов конечно, проводится так же, как и для вложенных множеств в упр. 10.
13. ам апай,, аьаз .аы 14. Поскольку множество Я не является пустым, оно годержит элемент 1 аь .аы где Л принимает минимально возможное значение. Если Л > О, выберел~ в множесгве 5 минимально возможное значение аь и сразу же получим, что !с должно быть равно О. Иначе говоря, Я должно содержать элемент 1. Пусть этот элемент является корнем. Все остальные элементы !с > О, а потому оставшиеся элементы множества 5 можно разбить на множества 5~ = (1.у аэ...аь), 1 < у < т, лля некоторого пг > О. если тп зе 0 и множество Я не пусто, то по тем же соображениям получим, что 1.1 принадлежит множеству 5, для каждого 5~.
Поэтому каждое множество Я~ не пусто. Тогда легко видеть, что множества ~, = (1 аг ' .аь ) 14лам .аь принадлежит Яз) удовлетворяют тому же условию, что и множество Я. По индукции каждое множество 5~ образует дерево. 15. Пусть 1 — корень, а ссО и а.! — корни левого и правого поддеревьев дерева а соответственно, если такие корни существуют. Например, на рис.
18, (а) Король Кристиан 1Х встречается дважды, а именно — в позициях 1.0,0.0.0 и 1.1.0 0.1.0. Для краткости опустим десятичные точки в этих обозначениях и получим 10000 и 110010. Замечание. Это обозначение предложено Ф. Гальтоном (Егапс!э Са!гоп); см. Хасига! 1пЛегйапсе (Масш!!!ап, 1889), 249. Для родословных лучше использовать мнемонические обозначения Г (1асйег — отец) и М (шосЬег — мать) вместо 0 и 1 и отбросить начальную единицу. Тогда родственное отношение Кристиана 1Х по отношению к Чарльзу можно выразить обозначением МРг'МР, т.
е Кристиан 1Х является отцом матери отца отпа матери Чарльза. Система обозначений на основе 0 и 1 интересна еще и тем, что она позволяет установить важное соотношение между узлами бинарного дерева и положительными целыми числами в двоичной системе (а именно — между адресами в памяти компьютера). 16. (а) (Ъ) 17. Узел-родитель (г'(Ц) = 4, узел-родитель (г'(1, 2)) = С; следовательно, узел-родитель (Л'(1, 2, 2!) = Е.
18. Ь(5, 1, Ц = (2). ЦЗ, Ц не имеет смысла, так как 1,(З] является пустым Списком. ьЩ 1(2) = (1); Ц2,1,Ц = а. (') 20. (Интуитивно соответствие между 0-2-деревьями и бинарными деревьями можно получить, удалив все концевые узлы в 0-2-дереве См. построение в разделе 2.3 4ой) Пусть 0-2-дерево с одним узлом соответствует пустому бинарному дереву, а 0-2-дерево с более чем одним узлом, состоящее из корня г и О-2-деревьев Т~ и Тм соответствует бинарному дереву с корнем г, левым поддеревом Т', и правым поддеревом Та где Т~ и Тз соответствуют Т, 'и Тз. 21. 1+О я~+1 пэ+ +(ш — 1).п~. Доказаглельсшео. Количество узлов в дереве равно по + п~ + пз + ..
+ и, и оно также равно 1 + (количество детей в дереве) = 1 + 0. по + 1 и~+2.пг+ +щ и 22. Основная идея заключается в использовании рекурсивного построения, т. е. в представлении непустого бинарного дерева в виде корня, а также левого и правого поддеревьев, которые уменьшены наполовину и повернуты.
Таким образом, имея достаточно мощную лупу, можно на странице бумаги изобразить бинарное дерево большого размера. Это можно реализовать несколькими способами. Например, один из них заключается в представлении корня с помощью линии, проведенной от центра страницы в альбомной ориентации к ее верхнему краю. Причем представление левого поддерева получится в левой половине страницы после поворота на 90' по часовой стрелке, а правого поддерева— в правой половине страницы после поворота на 90' против часовой стрелки. Затем каждый узел будет представлен линией половинной длины (по сравнению с длиной предыдущего отрезка), проведенной снизу вверх, (Коли применить этот метод для полного бинарного дерева (сошр)есе Ыпагу ггее) с 2 — 1 узлами на )г уровнях, получатся так называемые ь Н-деревья (Н-(геев), которые представляют наиболее эффективную компоновку таких бинарных деревьев на СВИС-микросхеме (Чьз1 сЫр) (см.
Н. Р. Вгепс апб Н. Т. Кпп8, ГпГ. Ргос. Ге(гэга 11 (1980), 46 — 48.) В А ПК П РАЗДЕЛ 2.3.1 1. 1ИРО(Т) = А, 1ИРО(851ИК(Т)) = С и т. дб в результате получим Н. 2. В прямом порядке обхода: 1245367; в симметричном порядке обхода: 4251637; в обратном порядке обхода: 4526731. 3. Да, справедливо. Обратите внимание, например в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
