b) имеются узлы с несчетным уровнем,

c) каждый узел имеет по крайней мере степень 2 и существует несчетное множество уровней

12. [М23] При каких условиях частично упорядоченное множество соответствует неупорядоченному дереву или лесу (Частично упорядоченные множества определены в разделе 2 2 3 )

13. [10] Предположим, что номер узла -Y в десятичной системе обозначений Дьюи равен

01 02 йк Какими тогда будут номера узлов на пути от JV к корню (см упр 3) в этой системе обозначений

14. [М22] Пусть S - это любое непустое множество элементов 1 oi ак, где к > О и 0.1, ,ак - положительные целые числа Покажите, что S соответствует дереву в том случае, когда оно конечно и удовлетворяет следующему условию если а т принадлежит этому множеству, то ему также принадлежит а (т - 1), если m > 1, или а, если т = 1 (Это условие, очевидно, выполняется для дерева в десятичной системе обозначений Дьюи, следовательно, его можно рассматривать как еще один способ определения древовидной структуры)

► 15. [20] Придумайте систему обозначений для узлов бинарного дерева, аналогичную десятичной системе обозначений Дьюи для узлов деревьев

16. [20] Нарисуйте схемы, аналогичные изображенным на рис 21 которые соответствуют следующим арифметическим выражениям (а) 2(а - Ь/с), (Ъ) а + Ь + 5с

17. [01] Если представленную на рис 19 структуру рассматривать как лес F, то какому узлу будет соответствовать узел-родитель множества поддеревьев {F[l 2,2])

18. [08] Каким элементам в Списке (3) соответствуют обозначения L[o 1,1] и L[3 1]

19. [15] Создайте схему Списка, аналогичную схеме (7), для Списка L = (а, {L)) Каки.м элементам этою Списка соответствуют обозначения L[2] и L[2 1,1]

► 20. [М21] Пусть О-2-(?среео обозначает дерево в котором каждый узел не имеет ни одного потомка или имеет двух детей (Формально 0-2-дерево состоит из одного узла - корня, плюс О или 2 непересекающихся 0-2-деревьев ) Покажите, что каждое 0-2-дерево имеет нечетное чисто узлов, и установите взаимно однозначное соответствие между бинарными деревьями с п узлами и (упорядоченными) О-2-деревьями с 2п-- 1 узлами

21. [М22] Если де1)ево имеет п1 узлов степени 1, п2 узлов степени 2, и узлов степени т, го сколько в нем содержикя концевых узлов

► 22. [21] Используемые в Европе стандартные форматы страниц АО, А1, А2, , An, представляют собой прямоугольники с соотношением сторон \/2 к 1 и площадью 2~" квадратных метров Следовательно, при разрезании пополам страницы формата An получим две страницы формата А(п -(- 1) Используя данный принцип, создайте графическое представление бинарных деревьев и проиллюстрируйте эту идею на примере структуры

2 3 1-(1) из следующего раздела

2.3.1. Обход бинарных деревьев

Прежде чем продолжить изучение деревьев, необходимо тщательно рассмотреть свойства бинарных деревьев, поскольку деревья общего типа обычно представляются внутри компьютера в виде некоторого эквивалентного бинарного дерева

Бинарное дерево определено выше как конечное множество узлов, которое может либо быть пустым, либо состоять из корня вместе с двумя другими бинарными

деревьями. Это определение наводит на мысль о естественном способе представления бинарных деревьев внутри компьютера: каждый узел имеет связи LLINK и RLINK, а также переменную сязи Т, которая является указателем дерева. Если дерево пусто, то Т = Л; в противном случае Т является адресом корневого узла этого дерева, а LLINK (Т), RLINK (Т)-указателями на левое и правое поддеревья этого корня соответственно. Данные правила рекурсивно определяют представление в памяти любого бинарного дерева. Например, дерево

может быть представлено таким образом:

1£11

Это простое и естественное представление дерева в памяти компьютера и объясняет особую важность бинарных древовидных структур Как показано в разделе 2.3.2, деревья общего типа очень удобно представлять в виде бинарных деревьев. Более того, многие деревья в приложениях сами по себе являются бинарными, поэтому они представляют особый интерес.

Существует достаточно много алгоритмов работы с древовидными структурами, в которых наиболее часто встречается понятие обхода {traversing) дерева или "прохода" по дереву. При таком методе исследования дерева каждый узел посещается в точности один раз, а полный обход дерева задает линейное упорядочение узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел, т. е. узел, который располагается перед данным узлом в таком упорядочении или после него.

Для обхода бинарного дерева можно применить один из трех принципиально разных способов: в прямом порядке {preorder), в центрированном порядке {inorder) или в обратном порядке {postorder). Эти три метода определяются рекурсивно. Если бинарное дерево пусто, то для его "обхода" ничего делать не потребуется.

в противном случае обход выполняется в три этапа.

Прямой порядок обхода Центрированный порядок обхода Попасть в корень Пройти левое поддерево

Пройти левое поддерево Попасть в корень

Пройти правое поддерево Пройти правое поддерево

Обратный порядок обхода Пройти левое поддерево Пройти правое поддерево Попасть в корень

Если применить эти определения к бинарному дереву (1) и (2), то при прямом порядке обхода узлов получим последовательность

ABDCEGFHJ. (3)

(Сначала следует корень А, затем - левое поддерево в прямом порядке,

и, наконец, правое поддерево в прямом порядке.) При центрированном порядке обхода корень посещается после обхода узлов одного из деревьев точно так, как если бы узлы дерева "проектировались" на горизонтальную прямую с образованием последовательности

DBAEGCHFJ. (4)

Аналогично обратный порядок обхода позволяет получить последовательность

DBGEHJFCA. (5)

Как будет показано ниже, эти три способа упорядочения узлов бинарного дерева в виде линейной последовательности чрезвычайно важны, поскольку они тесно связаны с большинством компьютерных методов обработки деревьев. Названия прямой, центрированный и обратный происходят, конечно, от расположения корня по отношению к поддеревьям. Во многих приложениях бинарных деревьев понятия левого и правого поддеревьев совершенно симметричны, и в таких случаях термин симметричный порядок используется в качестве синонима понятия центрированный порядок. Центрированный порядок, при котором корень располагается посередине, образует симметрию относительно левой и правой сторон: при отражении бинарного дерева относительно вертикальной оси получается простое обращение симметричного порядка.

Для применения в ко.мпьютерных вычислениях предложенные выше рекурсивные Определения трех основных способов обхода придется сформулировать несколько иначе. Наиболее общие методы такой переформулировки рассматриваются в главе 8. Обычно для этого используется вспомогательный стек, например так, как в показанном ниже алгоритме.