Главная » Java, Структуры данных и алгоритмы » Методы дерева

0

АТД «дерево» хранит элементы в позициях, которые, как и позиции в списке, определяются соседними позициями. Позициями в дереве выступают его узлы, и соседствующие позиции отвечают требованиям роди- тельско-дочерних отношений, определяющих правильное дерево. Таким образом, термины «позиция» и «узел» в контексте обсуждения дерева могут взаимозаменяться. Как и в случае с позициями в списке, позиция в дереве поддерживает метод:

element(): возвращает объект данной позиции.

Input: none; Output: объект.

Преимущества использования позиций в деревьях, однако, вытекают из следующих методов доступа (accessor method) АТД «дерево», принимающих и возвращающих объекты позиций:

root(): возвращает корень дерева. Input: нет; Output: позиция.

parent(v): возвращает родителя узла v; ошибка, если v является корнем.

Input: позиция; Output: позиция.

children(v): возвращает итератор дочерних элементов узла v.

Input: позиция; Output: итератор объектов позиций.

Если дерево Г упорядочено, то итератор children(v) обеспечивает доступ к дочерним элементам узла v в определенном порядке. Для простого узла v children(v) — пустой итератор.

Основные методы дополняются следующими методы запроса (query methods):

islnternal(v): проверяет, является ли v составным.

Input: позиция; Output: логическое значение.

isExternal(v): проверяет, является ли v простым.

Input: позиция; Output: логическое значение.

isRoot(v): проверяет, является ли v корнем.

Input: позиция; Output: логическое значение.

Эти методы позволяют упростить анализ программирования с использованием деревьев, поскольку могут использоваться в выражениях проверки условий в if-конструкциях и циклах while вместо сложных проверок при обнаружении ошибок. К примеру, islnternal(v) и isExternal(v) могут использоваться для проверки возврата методом children(v) пустого итератора или итератора, имеющего элементы.

Существует несколько общих методов, не относящихся непосредственно к структуре дерева, но они, в принципе, должны им поддерживаться.

Такими общими методами (generic method) являются:

size(): возвращает количество узлов в дереве. Input: нет; Output: целое число.

elements(): возвращает итератор всех элементов, хранимых в узлах дерева.

Input: нет; Output: итератор объектов.

positions(): возвращает итератор всех узлов дерева.

Input: нет; Output: итератор позиций.

swapElements(v,w): меняет местами элементы, хранимые в узлах v и w.

Input: две позиции; Output: отсутствует.

replaceElement(v,e): замещает на е и возвращает элемент, хранившийся в узле v.

Input: позиция и ее объект; Output: объект.

Здесь не приводятся специальные методы обновления дерева. Вместо этого в последующих главах опишем методы обновления (update methods) деревьев, зависящие от их специфики и условий применения. В принципе, кроме приведенных в этой книге имеется много других методов обновления деревьев. В следующем разделе приведены способы преобразования набора методов, входящих в структуру рассматриваемого АТД, в совокупность Java-интерфейсов.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии