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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-03