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

0

Описанные выше методы прохода дерева по существу являются примерами любопытной модели объектно-ориентированного проектирования — шаблона стандартных методов (template method pattern). Эта модель- описывает обобщенный механизм обработки, который специальным образом может быть использован для конкретного применения путем переопределения соответствующих шагов.

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

Следуя модели проектирования стандартных методов, создадим алгоритм templateEulerTour, реализующий стандартный эйлеровый проход бинарного дерева. При обращении к узлу v метод templateEulerTour на определенных стадиях прохождения вызывает несколько других вспомогательных методов. Прежде всего создается трехэлементный массив г для хранения результатов вычислений с помощью вызова метода initResult. Затем, если v является простым узлом, templateEulerTour вызывает вспомогательный метод visitExternal, в противном случае (если v — составной) templateEulerTour выполняет следующие действия:

•          вызывает вспомогательный метод visitLeft, выполняющий вычисления при обращении к узлам слева;

•            рекурсивно обращается к левому дочернему элементу;

•          вызывает вспомогательный метод visitBelow, выполняющий вычисления при обращении к узлу снизу;

•            рекурсивно обращается к правой ветви;

•          вызывает вспомогательный метод visitRight, выполняющий вычисления при обращении к узлу справа.

И наконец, templateEulerTour возвращает результат, вызывая вспомогательный метод returnResult. Метод templateEulerTour можно рассматривать как шаблон или «каркас» прохода по Эйлеру (см. фрагмент кода 6.22).

В контексте объектно-ориентированного программирования возможен класс EulerTour, который содержит:

•             метод templateEulerTour;

•          все вспомогательные методы, вызываемые методом templateEulerTour, являются абстрактными (не содержащими операторов или возвращающими null);

•            содержит метод execute, вызывающий templateEulerTou^T1, TlrootO).

Сам класс EulerTour не выполняет каких-либо значимых операций. Тем не менее с помощью наследования можно создать новый класс и переопределить в нем абстрактные методы прохода по дереву.

Алгоритм templateEiilerTour(T,v): г = initResult() if 7".isExternal(i/) then

t[ 0] = visitExternal(7>,r) else

visitLeft(7>,r)

r[ 1] = templateEulerTour(r, 7".leftChild(i/)) visitBelow(7>,r)

r[2] = templateEulerTour(T, r.rightChild(v^)

visitRight(7>,A)

return return Result(r)

Фрагмент кода 6.22. Метод templateEulerTour для вычисления стандартного эй- лерового прохода ветви, корнем^которой служит узел v бинарного дерева Г, соответствующий модели проектирования стандартных методов. Этот метод вызывает методы initResult, visit External, visitLeft, visitB^low, yisitRight и returnResult

Примеры шаблонных ме1[15]одов

< r

Для начала определим значение выражения, ассоциируемого с деревом арифметического выражения (см. пример 6.5), создав новый класс EvaluateExpression, который:

•                  наследует класс EulerTour;

•                  переопределяет метод initResult, возвращая массив из трех элементов;

•                  переопределяет метод visitExternal, возвращая хранимое в узле значение;        , г , , ‘ . -

•                  переопределяет метод visitRight, выполняя над г[1] к г[2] операцию, хранящуюся в узле, и устанавливая Значение г[0] равным результату операции;          >

•                  переопределяет метод returnResult, возвращая г[0].

Такой подход вполне можно сравнить с непосредственной реализацией алгоритма, приведенного во фрагменте кода,6.18.

В следующем примере распечатаем выражение, ассоциируемое с деревом арифметического выражения (см. пример 6.5), пользуясь новым классом PrintExpression, который:

Этот подход можно сравнить с непосредственной реализацией алгоритма, приведенного во фрагменте кода 6.21.

Реализация на Java

Законченная реализация стандартного класса EulerTour и его специализированных версий EvaluateExpressionTour и PrintExpressionTour показана во фрагментах кода 6.23—6.25. Обратите внимание на использование объекта класса TraversalResult с полями fmalResult, leftResult и rightResult вместо массива, имеющего длину 3.

Г

*                  Шаблон алгоритмов прохода бинарного дерева по Эйлеру.

*                  Подклассы данного класса будут переопределять некоторые методы

*                    класса для образования специфического вида прохода. 7

public abstract class EulerTour {

protected InspectableBinaryTree tree; public Object execute(BinaryTree T) { tree == T;

return null; // возвращать пока нечего

}

protected Object eulerTour(Position p) { Traversal Result r = initResult(); if (tree.isExternal(p)) { visitExternal(p, r); } else {

visitLeft(p, r);

r.leftResult = eulerTour(tree.leftChild(p)); // рекурсивное прохождение visitBelow(p, r);

r.rightResult = eulerTour(tree.rightChild(p)); // рекурсивное прохождение visitRight(p, r);

}

return result(r);

}

// методы, которые могут переопределяться подклассами protected void visitExternal(Position p. TraversalResult r) {} protected void visitLeft(Position p, TraversalResult r) {} protected void visitBelow(Position p, TraversalResult r) {} protected void visitRight(Position p, TraversalResult r) {} protected TraversalResult initResult() { return new TraversalResult(); }

protected Object result(TraversalResult r) { return r.finalResult; } }

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

j**

*       Данная версия класса EulerTour предназначена для вычисления

*       значения

*       арифметического выражения, хранящегося в дереве.

*       Она предполагает, что

*       элементы, хранимые в простых узлах, являются объектами Integer,

*       а элементы,

*       хранимые в составных узлах, имеют тип Operatorlnfo,

*       поддерживающий метод

*       operation(lnteger х, Integer у), который возвращает результат

*       применения

*                  арифметической операций между х и у. 7

public class EvaluateExpressionTour extends EulerTour {

public Object execute(BinaryTree T).{

super.execute(T); // вызывает метод суперкласса System.out.print("The value is:"); System.out.println(eulerTour(tree.root())); return null; // возвращать пока нечего

}

protected void visitExternal(Position p, TraversalResult r) { r.finalResult = (Integer) p.element();

}

protected void visitRight(Position p, TraversalResult r) { Operatorlnfo op = (Operatorlnfo) p.element(); r.finalResult = op.operation((lnteger) г.1е^Рё8ии,

(Integer) nrigbfResult);

}

}

Фрагмент кода 6.24. Класс EvaluateExpressionTour, который преобразует EulerTour для определения значения, соответствующего дереву арифметического выражения

Г

*       Данная версия класса EulerTour предназначена для вывода на печать

*       арифметического выражения, хранящегося в дереве.

*       Версия предполагает, что

*       элементы, хранимые в узлах дерева, поддерживают метод toString,

*       который распечатывает значение из простого узла или оператор

*       из составного узла.

7

public class PrintExpressionTour extends EulerTour { public Object execute(BinaryTree T) { super.execute(T); System.out.print( "Expression:"); eulerTour(T.root()); System.out. println();

return null; // возвращать пока нечего

}

protected void visitExternal(Position p, Traversal Result r) { System.out.print(p.element());

}

protected void visitLeft(Position p, TraversalResult r) { System.out.printf (");

}

protected void visitBelow(Position p, TraversalResult r) { System.out.print(p.element());

}

protected void visitRight(Position p, TraversalResult r) { System, out. printf)");

} }

Фрагмент кода 6.25. Класс PrintExpressionTour, который преобразует EulerTour для вывода на печать значения дерева арифметического выражения

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

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

По теме:

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