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

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

Корень дерева — это единственный узел, не имеющий непосредственного предка.

Имеется множество типов деревьев. Важнейшим с точки зрения информатики подмножеством структуры типа дерева является подмножество бинарных деревьев поиска. У бинарного дерева каждый узел имеет не более двух дочерних узлов, при­чем левый и правый узлы различаются. Каждый узел содержит несколько полей: поля значения, хранящегося в узле, и полей, указывающих на левый и правый по­томки данного узла, а также на родительский узел. Бинарным деревом поиска его

Глава 14. Основы теории алгоритмов

делает следующее свойство: значения в узлах дерева располагаются таким образом, что в любой момент для любого узла х значения всех узлов в его левом поддереве не превышают значения узлах, а значения всех узлов в его правом поддереве не мень­ше значения узла х. На рис. 14.23 показано несколько деревьев. Числа в кружках отражают значения данных, хранящихся в узлах дерева. Дерево на рис. 14.23, а не является бинарным, так как у узла 5 есть три дочерних узла. Дерево на рис. 14.23, б является бинарным, но не является деревом поиска, так как узел 2 является правым дочерним узлом по отношению к узлу 3, нарушая свойство дерева поиска. Дерево на рис. 14.23, в представляет собой корректное бинарное дерево поиска.

Рис. 14.23. Виды деревьев

На рис. 14.24 изображено возможное представление бинарного дерева поис­ка с использованием полей указателей. На этом рисунке, как и на предыдущем, цифры представляют собой значения, хранящиеся в каждом из элементов дерева, а стрелки показывают, как при помощи указателей каждый узел дерева связан со своими правым и левым поддеревьями, а также с родительским узлом. Так, для узла со значением 2 буквой а помечен указатель, связывающий его с родительским узлом, а буквами Ъ и с — указатели, связывающие этот узел, соответственно, с его левым и правым поддеревьями.

						•
		>	г
	> а 4
	т12	t				7т
b 1		с <
т Чт		т		т		т	•т

Рис. 14.24. Бинарное дерево поиска

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

14.4. Представление и обработка данных разного типа

узлов: 1,2, 3,4,5,7. Как видите, таким образом можно получить отсортированную последовательность значений узлов.

Два других распространенных метода обхода дерева — обход в прямом порядке, при котором сначала выводится корень, а потом значение левого и правого поддере­вьев (для уже рассматривавшегося дерева это дает последовательность значений 4, 2,1,3,7,5), и обход в обратном порядке, при котором сначала выводятся значения узлов левого и правого поддеревьев, а затем — корня (для нашего дерева это дает последовательность 1, 3, 2, 5, 7,4).

Псевдокоды описанных обходов дерева очень просты. Алгоритм процедуры симметричного обхода представлен на рис. 14.25.

Входные данные:

Процедура InorderTreeWalk (x,f)\—

х — указатель на корневой узел дерева f— функция, вызываемая для обработки _ данных в текущем узле

Если ссылка на след. элемент отсутствует, выполнение процедуры прекращается

false

InorderTreeWalk (x.left, f)[-

Процедура вызывает сама себя в качестве ссылки на обрабатываемый узел принимая ссылку на корень левого поддерева (x.left)

f(x. value)

Функция f обрабатывает значение, хранящееся в текущем узле

| InorderTreeWalk(x.rightj)}------

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

f_____ Возврат из процедуры j

Рис. 14.25.Процедура симметричного обхода бинарного дерева

В этой процедуре для обхода всех узлов дерева и выполнения над ними опре­деленных операций используется рекурсия.

Рекурсия часто применяется в алгоритмах обработки разного рода сложно структурированных объектов, в частности документов в формате XML, когда ко­личество дочерних узлов и уровень их вложенности заранее не известны.

Основные операции при работе с бинарным деревом поиска — поиск в нем опре­деленного значения, а также поиск наименьшего и наибольшего элементов дерева и поиск предшествующего и последующего элементов для данного.

Выполнение операции поиска основано на том, что находясь на определенной вершине, всегда можно однозначно указать, в каком из поддеревьев находится искомое значение (если таковое имеется в данном дереве), так как согласно свой­ству бинарного дерева поиска все значения узлов в левом поддереве не больше, а в правом — не меньше значения в корне.