Проектування класу TreeNode 15

У цьому пунктіі розробляється клас TreeNode, в якому оголошуються об'єкти-вузли бінарного дерева. Вузол складається з поля даних, яке є відкритим (public) елементом, тобто до якого користувач може звертатися безпосередньо. Це дозволяє програмістові читати або оновлювати дані під час проходження дерева, а також допускає повернення посилання на дані. Остання особливість використовується більш складними структурами даних, такими як словники. Два поля з вказівниками є закритими елементами, доступ до яких здійснюється за допомогою функцій Left () і Right ().

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

ОБ’ЯВЛЕННЯ

// BinSTree залежить від TreeNode

template <class T>

class BinSTree;

// Оголошення об'єкта для вузла бінарного дерева

template <class T>

class TreeNode 16

{

private:

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

TreeNode <T> * left;

TreeNode <T> * right;

public:

// Відкритий елемент, що допускає оновлення

Т data;

// Конструктор

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

TreeNode <T> * rptr = NULL);

// Методи доступу до полів вказівників

TreeNode <T> * Left (void) const;

TreeNode <T> * Right (void) const;

// Зробити клас BinSTree дружнім, оскільки він необхідний

// Доступ до полів left і right

friend class BinSTree <T>; 17

};

ОПИС

Конструктор ініціалізує поля даних і вказівників. За допомогою порожнього вказівника NULL вузли ініціалізуються як листя. Маючи вказівник Р об'єкта 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); 18

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

Реалізація класу TreeNode Клас TreeNode ініціалізує поля об'єкту. Для ініціалізації поля даних конструктор має параметр item. вказівники призначають вузлу лівого і правого сина (піддерево). за відсутності сина використовується значення NULL.

// Конструктор ініціалізує поля даних і вказівників

// Значення NULL відповідає порожньому піддереву

template <class T>

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

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

{}

Методи Left і Right повертають значення полів лівого і правого вказівників. Завдяки цьому програміст має доступ до лівого і правого синів вузла.

Побудова бінарного дерева

Бінарне дерево складається з колекції об'єктів TreeNode, пов'язаних за допомогою своїх полів з вказівниками. Об'єкт TreeNode створюється динамічно за допомогою функції new.

Виклик функції new обов'язково повинен включати значення даних. Якщо, як параметр, передається також вказівник об'єкта TreeNode, тоді він використовується новоствореним вузлом для приєднання вузла сина.

TreeNode <int> * p; // оголошення вказівника

// на цілочисельний вузол дерева

р = new TreeNode (item); // лівий і правий вказівники дорівнюють NULL

Визначимо функцію 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

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

// Якщо пам'яті недостатньо, завершити програму повідомленням про помилку

if (p == NULL)

{

cerr <<" Помилка при виділенні пам'яті! \ п ";

exit (l);

}

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

return p;

}

Функція FreeTreeNode приймає вказівник на об'єкт TreeNode і звільняє займану вузлом пам'ять, викликаючи функцію C + + delete.

// Звільнити динамічну пам'ять, займану даним вузлом

template <class t>

void FreeTreeNode (TreeNode <T> * p)

{

delete p;

}

Не нашли, что искали? Воспользуйтесь поиском: