Класс BinSTree

BinSTree – это класс, реализующий функциональность бинарного поискового дерева. Он содержит деструктор, конструктор копирования и перегруженные операторы присваивания, позволяющие инициализировать объекты и играющие роль операторов присваивания. Деструктор отвечает за очистку списка. Он и операторы присваивания вместе с методом ClearList вызывают скрытый метод DeleteTree. Мы также включили сюда скрытый метод CopyTree для использования в конструкторе копирования и перегруженном операторе "=".

//Спецификация класса BinSTree

#include <iostream.h>

#include <stdlib.h>

#include "treenode.h"

template <class T>

class BinSTree

{

protected: // Требуется для наследования

// Указатели на корень и на текущий узел

TreeNode<T> *root;

TreeNode<T> *current;

// Количество узлов дерева

int size;

// Распределение/освобождение памяти

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

TreeNode<T> *lptr, TreeNode<T> *rptr);

void FreeTreeNode(TreeNode<T> *p);

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

// и оператором присваивания

void DeleteTree(TreeNode<T> *t);

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

// и функцией ClearList

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

TreeNode<T>* & parent) const;

public:

// конструкторы и деструктор

BinSTree(void);

BinSTree(const BinSTree<T>& tree);

~BinSTree(void);

// оператор присваивания

BinSTree<T>& operator= (const BinSTree<T>& rhs);

// стандартные методы обработки списков

// Осуществляет поиск путем сравнения элемента

// с данными, хранящимися в узле.

// После выполнения текущая позиция соответствует

// совпавшему узлу.

int Find(T& item);

// Находит подходящее для вставки место и добавляет

// новый элемент данных. После выполнения этого метода

// текущая позиция соответствует новому узлу.

void Insert(const T& item);

// Находит соответствующий узел, удаляет его и

// связывает все его поддеревья так, чтобы сохранить

// структуру бинарного дерева поиска.

void Delete(const T& item);

void ClearList(void);

int ListEmpty(void) const;

int ListSize(void) const;

//Методы, специфичные для деревьев

// Если ключ в текущей позиции совпадает с ключом

//элемента данных, присваивает значение элемента данных

//узлу. В противном случае вставляет элемент данных в

//дерево.

void Update(const T& item);

// Возвращает указатель на корень.

TreeNode<T> *GetRoot(void) const;

}

ОПИСАНИЕ

Этот класс имеет защищенные данные. Переменная root указывает на корневой узел дерева. Указатель current ссылается на точку последнего изменения в списке. Например, current указывает положение нового узла после операции вставки, а метод Find заносит в current ссылку на узел, совпавший с элементом данных.

Класс BinSTree содержит две операции, специфические для деревьев. Метод Update присваивает новый элемент данных текущему узлу или вставляет в дерево новый элемент, если тот не совпадает с данными в текущей позиции. Метод GetRoot предоставляет доступ к корню дерева. Имея корень дерева, пользователь может применять различные алгоритмы, размещаемые во внешних функциях. Это расширяет возможности использования различных алгоритмов обработки деревьев, например, распечатки дерева.

Пример 2.

BinSTree<int> T; //Дерево с целочисленными данными

T.Insert(50); //Создать дерево с четырьмя узлами (A)

T.Insert(40);

T.Insert(70);

T.Insert(45);

T.Delete(40); // удалить узел 40 (B)

T.ClearList(); // удалить узлы дерева

// дерево univInfo содержит информацию о студентах.

// Поле ssn является ключевым

BinSTree<Student> univInfo;

Student stud;

//Назначить ключ "9876543789" и найти его на дереве

stud.ssn = "9876543789";

if (univInfo.Find(stud))

{

//Студент найден.

//Присвоить новый средний балл и обновить узел

stud.gpa = 3.86;

univInfo.Update(stud);

}

else

cout << "Студент отсутствует в базе данных." << endl;