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

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

//Предварительное описание класса «бинарное дерево поиска»

template <class T>

class BinSTree;

//Определение класса «узел бинарного дерева»

template <class T>

class TreeNode

{

//Указатели на левый и правый порожденные узлы

TreeNode<T> *left;

TreeNode<T> *right;

public:

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

T data;

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

//на порожденные узлы

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 как дружественного

friend class BinSTree<T>;

};

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

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

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

Пример 1.

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

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 возвращают значения полей левого и правого указателей. Благодаря этому клиент имеет доступ к левому и правому сыновьям узла.