Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Спецификация класса AVLTreeNode.
Объявление: // наследник класса 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; // корень АВЛ - дерева
void MakeAVLCharTree(AVLTreeNode<char>* &root) { AVLTreeNode<char> *a, *b, *c, *d, *e; e = new AVLTreeNode<char>('E', NULL, NULL, 0); d = new AVLTreeNode<char>('D', NULL, NULL, 0); c = new AVLTreeNode<char>('C', e, NULL, -1); b = new AVLTreeNode<char>('B', NULL, d, 1); a = new AVLTreeNode<char>('A', b, c, 0); root = a; }
Реализация класса AVLTreeNode. Конструктор класса AVLTreeNode вызывает конструктор базового класса и инициализирует balanceFactor.
// Конструктор инициализирует balanceFactor и базовый класс // Начальные значения полей указателей по умолчанию, равные NULL // инициализируют узел как лист
template <class T>
AVLTreeNode<T>::AVLTreeNode (const T& item, AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr, int balfac): TreeNode<T>(item, lptr, rptr), balanceFactor(balfac) {}
Методы Left и Right в классе AVLTreeNode упрощают доступ к полям данных. При попытке обратиться к левому сыну с помощью метода Left базового класса возвращается указатель на объект типа TreeNode. Чтобы получить указатель на узел АВЛ - дерева, требуется преобразование типов.
Например: AVLTreeNode<T> *p, *q; q = p->Left(); // недопустимая операция q = (AVLTreeNode<T> *)p->Left(); // необходимое приведение типа Во избежание постоянного преобразования типа указателей мы определяем методы Left и Right для класса AVLTreeNode, возвращающие указатели на объекты типа AVLTreeNode.
template <class T>. AVLTreeNode<T>* AVLTreeNode::Left(void) { return ((AVLTreeNode<T> *)left; } Класс AVLTree. АВЛ - дерево представляет собой списковую структуру, похожую на бинарное дерево поиска, с одним дополнительным условием: дерево должно оставаться сбалансированным по высоте после каждой операции вставки или удаления. Поскольку АВЛ - дерево является расширенным бинарным деревом поиска, класс AVLTree строится на базе класса BinSTree и является его наследником. Для выполнения АВЛ - условий следует изменить методы Insert и Delete. Кроме того, в производном классе определяются конструктор копирования и перегруженный оператор присвоения, так как мы строим дерево с большей узловой структурой.
|
|||||
Последнее изменение этой страницы: 2020-03-14; просмотров: 131; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 100.24.20.141 (0.02 с.) |