Построение бинарного дерева

ПРИМЕР

ОПИСАНИЕ

ОБЪЯВЛЕНИЕ

Структура бинарного дерева

Структура бинарного дерева состоит из узлов. Как и в связанном списке, эти узлы содержат поля данных и указатели на другие узлы в коллекции. В этом разделе мы определим узлы дерева и операции для его построения и прохождения. Объявим класс TreeNode, реализующий функциональность узла дерева, и разработаем ряд функций, позволяющих создавать бинарные деревья и осуществлять прохождение по их узлам.

Узел дерева содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL является признаком пустого дерева.

Корневой узел определяет входную точку дерева, а поля указателей – узлы следующего уровня. Листовой узел содержит NULL в полях правого и левого указателей (Рис. 7).

Проектирование класса TreeNode

В этом разделе мы разберем разработку класса TreeNode, в котором объявляются объекты-узлы бинарного дерева. Узел состоит из поля данных, которое является открытым (public) элементом, т.е. к которому можно обращаться непосредственно. Это позволяет читать или обновлять данные во время прохождения дерева, а также допускает возвращение ссылки на данные. Последняя особенность используется более сложными структурами данных, например, словарями. Два поля с указателями являются закрытыми (private) элементами, доступ к которым осуществляется посредством функций Left() и Right().

Спецификация класса TreeNode

// Следующее объявление понадобится

// нам в дальнейшем

template <class T>

class BinSTree;

// объявление объекта для узла бинарного дерева

template <class T>

class TreeNode

{

private:

// указатели левого и правого дочерних узлов

TreeNode<T> *left;

TreeNode<T> *right;

public:

// открытый элемент, допускающий обновление

T data;

// конструктор инициализирует поля данных и указателей

// значение NULL соответствует пустому поддереву

TreeNode(const T& item, TreeNode<T> *lptr,

TreeNode<T> *rptr):data(item), left(lptr), right(rptr)

{

}

// методы доступа к полям указателей

TreeNode<T>* Left(void) const;

TreeNode<T>* Right(void) const;

// сделать класс BinSTree дружественным, поскольку

// необходим доступ к полям left и right

friend class BinSTree<T>;

};

Конструктор инициализирует поля данных и указателей. Если задать вместо обоих указателей NULL, узел будет инициализирован как лист.

Если в параметр lptr или rptr конструктора поместить указатели на другой объект TreeNode, конструктор присоединяет этот объект как левого или правого сына нового узла.

Методы доступа Left и Right возвращают соответствующий указатель. Класс BinSTree объявляется дружественным классу TreeNode и может модифицировать указатели. Другие клиенты должны использовать конструктор для создания указателей и методы Left и Right для прохождения дерева.

// указатели целочисленных узлов дерева

TreeNode<int> *root, *lchild, *rchild;

TreeNode<int> *p;

// создать листья, содержащие

// 20 и 30 в качестве данных

lchild = new TreeNode<int> (20);

rchild = new TreeNode<int> (30);

// создать корень, содержащий число

// 10 и двух сыновей

root = new TreeNode<int> (10, lchild, rchild);

root->data = 50; // присвоить корню 50

Методы Left и Right возвращают значения полей левого и правого указателей. Благодаря этому клиент имеет доступ к левому и правому сыновьям узла.

Бинарное дерево состоит из коллекции объектов TreeNode, связанных между собой посредством полей Left и Right. Объект TreeNode создается динамически с помощью функции new.

TreeNode<int> *p; // объявление указателя

// на узел дерева

p = new TreeNode(item); // левый и правый указатели равны NULL

Вызов функции new обязательно должен включать значение данных, и необязательно указатели на правое и/или левое поддерево. Определим функцию GetTreeNode, принимающую данные, и ноль или более указателей на объект TreeNode для создания и инициализации узла бинарного дерева. При недостаточном количестве доступной памяти программа прекращается сразу после выдачи сообщения об ошибке.

// создать объект TreeNode с указательными полями lptr и rptr.

// по умолчанию указатели содержат NULL.

template <class T>

TreeNode<T> *GetTreeNode(T item, TreeNode<T> *lptr = NULL,

TreeNode<T> *rptr = NULL)

{

TreeNode<T> *p;

// вызвать new для создания нового узла

// передать туда параметры lptr и rptr

p = new TreeNode<T> (item, lptr, rptr);

// если памяти недостаточно, завершить

// программу сообщением об ошибке

if (p == NULL)

{

cerr << “Ошибка при выделении памяти!\n";

exit(1);

}

// вернуть указатель на выделенную системой память

return p;

}

Функция FreeTreeNode принимает указатель на объект TreeNode и освобождает занимаемую узлом память, вызывая оператор С++ delete.

// освободить динамическую память, занимаемую данным узлом

template <class t>

void FreeTreeNode(TreeNode<T> *p)

{

delete p;

}

Функция GetTreeNode может быть использована для явного построения каждого узла дерева и, следовательно, всего дерева. Это было продемонстрировано на дереве с тремя узлами, содержащими 10, 20 и 30. Для более крупного экземпляра процесс будет немного утомительным, так как вы должны поместить в дерево все значения данных и указателей.

Создадим функцию MakeCharTree, строящую три дерева, узлы которых содержат символьные элементы данных. Эти деревья будут использоваться для иллюстрации методов TreeNode в следующем разделе. Параметры функции включают в себя ссылку на корень дерева и число n (0 < n < 2), которое служит для обозначения дерева. Следующие объявления создают указатель на объект TreeNode, с именем root, и назначают его корнем дерева Tree_2.

// объявить указатель на корень

TreeNode<char> *root;

// сформировать на этом корне дерево tree_2

MakeCharTree(root,2);

На рисунке 8 показаны три дерева, построенных этим методом. Мы не приводим здесь кода этой функции ввиду ее примитивности, потренируйтесь сами.

Рис. 8. Дерево MakeCharTree

Дата добавления: 2017-01-14