Курсовая работа: Реализация АВЛ–деревьев через классы объектно–ориентированного программирования

// наследник класса TreeNode

template <class T>

class AVLTreeNode: public TreeNode<T>

{

private:

// дополнительный член класса balanceFactor используется методами класса AVLTree и позволяет избегать "перевешивания" узлов

int balanceFactor;

AVLTreeNode<T>* & Left(void);

AVLTreeNode<T>* & Right(void);

public:

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

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

AVLTreeNode<T> *rptr = NULL, int balfac = 0);

// возвратить левый/правый указатель узла типа TreeNode преобразовав его к типу AVLTreeNode

AVLTreeNode<T> *Left(void) const;

AVLTreeNode<T> *Right(void) const;

// метод для доступа к новому полю данных

int GetBalanceFactor(void);

// методы класса AVLTree должны иметь доступ к Left и Right

friend class AVLTree<T>;

};

Описание :

Элемент данных balanceFactor является скрытым, так как обновлять его должны только выравнивающие баланс операции вставки и удаления. Доступ к полям - указателям осуществляется с помощью методов Left и Right. Новые определения для этих методов обязательны, поскольку они возвращают указатель на структуру AVLTreeNode.

Поскольку класс AVLTree образован на базе класса BinSTree, будем использовать деструктор базового класса и метод ClearList. Эти методы удаляют узлы с помощью оператора delete. В каждом случае указатель ссылается на объект типа AVLTreeNode, а не TreeNode. Так как деструктор базового класса TreeNode виртуальный, при вызове delete используется динамическое связывание и удаляется объект типа AVLTreeNode.

Пример:

Эта функция создает АВЛ - дерево, изображенное на рисунке 4. Каждому узлу присваивается показатель сбалансированности.

Рис. 4.

AVLTreeNode<char> *root; // корень АВЛ - дерева