Разработка функций класса TreeNode

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

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

Наша реализация метода прохождения предусматривает передачу указателя на функцию в качестве параметра (visit). Эта функция осуществляет доступ к содержащимся в узле данным. Передавая в качестве параметра указатели на разные функции, можно добиться выполнения различных действий при прохождении каждого узла в процессе прохождения дерева. В языках С++ и С (по крайней мере, в современных реализациях С) имя функции является указателем на эту функцию. Это значит, что вместо синтаксиса * <имя> можно использовать просто имя функции. Таким образом, при задании функции в качестве параметра другой функции можно пользоваться упрощенным синтаксисом. Наш метод прохода можно записать так:

template <class T>

void <Метод_прохода> (TreeNode<T> *t, void visit(T& item));

Всякий раз при вызове метода клиент должен передавать имя функции, выполняющей некоторое действие с данными, имеющимися в узле. По мере того как метод перемещается от узла к узлу, вызывается эта функция и выполняется предусмотренное действие.

Чтобы определить аргумент некоторой функции как указатель на функцию, необходимо в описание параметра поместить описание передаваемой функции. Пусть, например, функция G имеет параметр — функцию f. В этом параметре указывается имя функции (f), список параметров (int x) и возвращаемый тип (int).

int G(int t, int f(int x)) //Параметр-функция f

{

//Вычислить f(t) с помощью функции f и параметра t.

//Возвратить произведение этого значения и t

return t * f(t);

}

Вызывая функцию G, клиент должен передать функцию для f с той же структурой. Пусть в нашем примере клиент определил функцию XSquared, вычисляющую x2.

// XSquared - целочисленная функция с целочисленным параметром x

int XSquared(int x)

{

return x*x;

}

Клиент вызывает функцию G с целочисленным параметром t и параметром-функцией XSquared. Оператор

Y = G(3, XSquared)

вызывает функцию G, которая в свою очередь вызывает функцию XSquared с параметром 3. Оператор:

cout << G(3.0, XSquared) << endl;

печатает результат 27.