rendered paste body#ifndef _TREE_H_
#define _TREE_H_
#include <list>
template<typename T>
class BinaryTree
{
public:
//конструктор по умолчанию
BinaryTree()
: pkey(0), pleft(0), pright(0), pparent(0)
{
}
//конструктор копирования
BinaryTree(const BinaryTree<T>& other)
: pkey(0), pleft(0), pright(0), pparent(0)
{
pparent = 0;
if(other.hasKey())
{
pkey = new T(other.key());
if(other.hasLeft())
{
pleft = new BinaryTree<T>(this, other.left());
}
if(other.hasRight())
{
pright = new BinaryTree<T>(this, other.right());
}
}
}
//деструктор
~BinaryTree()
{
if(pleft)
{
delete pleft;
}
if(pright)
{
delete pright;
}
if(pkey)
{
delete pkey;
}
}
//функция для вставки элементов из отрезка [begin, end]
//Пример: int m[] = {1, 3, 2, 6, 7, -4}
// int* p = m;
// tree.insertFrom(p, p + 5);
//Занесет в дерево tree пять первых элементов массива. Работает с любыми итераторами
template<typename Iterator>
void insertFrom(const Iterator& begin, const Iterator& end)
{
for(Iterator i = begin; i != end; ++i)
{
this->insert(*i);
}
}
//Возвращает список, составленный из элементов дерева
std::list<T> makeList() const
{
std::list<T> result;
if(pkey)
{
result.push_back(*pkey);
if(hasLeft())
{
result.splice(result.end(), pleft->makeList());
}
if(hasRight())
{
result.splice(result.end(), pright->makeList());
}
}
return result;
}
//Вставляет элемент в дерево согласно правилам. Выделяет память, если нужно.
void insert(const T& new_value)
{
if(!pkey)
{
pkey = new T(new_value);
}
if(new_value == *pkey)
{
return;
}
else if(new_value < *pkey)
{
if(!pleft)
{
pleft = new BinaryTree<T>(this);
}
pleft->insert(new_value);
}
else
{
if(!pright)
{
pright = new BinaryTree<T>(this);
}
pright->insert(new_value);
}
}
//Возвращает true если у узла есть родитель, иначе false
bool isRoot() const
{
return (pparent ? true : false);
}
//Возвращает ссылку на узел-родитель. Если родителя нет, кидает исключение
BinaryTree<T>& parent()
{
if(!pparent)
{
throw NoParent();;
}
return *pparent;
}
//Возвращает константную ссылку на узел-родитель. Если родителя нет, кидает исключение
const BinaryTree<T>& parent() const
{
if(!pparent)
{
throw NoParent();;
}
return *pparent;
}
//Возвращает true, если у узла есть ключевое значение, иначе false
bool hasKey() const
{
return (pkey ? true : false);
}
//Возвращает ссылку на ключевое значение узла. Если значения нет (указатель нулевой), кидает исключение
T& key()
{
if(!pkey)
{
throw NoValue();
}
return *pkey;
}
//Возвращает константную ссылку на ключевое значение узла.
//Если значения нет (указатель нулевой), кидает исключение
const T& key() const
{
if(!pkey)
{
throw NoValue();
}
return *pkey;
}
//Устанавливает новое ключевое значение. В данном случае, дерево не перестраивается, поэтому эту
//функцию нужно использовать очень аккуратно, чтобы не нарушить структуру дерева
void setKey(const T& new_value)
{
if(pkey)
{
delete pkey;
}
pkey = new T(new_value);
}
//Возвращает ссылку на левое поддерево. Если левого поддерева нет (указатель нулевой),
//то кидает исключение
BinaryTree<T>& left()
{
if(!pleft)
{
throw NoSubtree();
}
return *pleft;
}
//Возвращает константную ссылку на левое поддерево. Если левого поддерева нет (указатель нулевой),
//то кидает исключение
const BinaryTree<T>& left() const
{
if(!pleft)
{
throw NoSubtree();
}
return *pleft;
}
//Возвращает ссылку на правое поддерево. Если правого поддерева нет (указатель нулевой),
//то кидает исключение
BinaryTree<T>& right()
{
if(!pright)
{
throw NoSubtree();
}
return *pright;
}
//Возвращает константную ссылку на правое поддерево. Если правого поддерева нет (указатель нулевой),
//то кидает исключение
const BinaryTree<T>& right() const
{
if(!pright)
{
throw NoSubtree();
}
return *pright;
}
//Рекурсивный поиск по дереву. Возвращается указатель на констатное поддерево,
//ключевое значение коренного узла которого равно искомому
//Если такого значения в дереве нет, возвращается ноль
//Сложность по времени: в среднем O(logn), в худшем O(n)
const BinaryTree<T>* find(const T& pattern) const
{
if(!pkey)
{
return 0;
}
if(pattern == *pkey)
{
return this;
}
if(pattern < *pkey)
{
if(!pleft)
{
return 0;
}
return pleft->find(pattern);
}
else
{
if(!pright)
{
return 0;
}
return pright->find(pattern);
}
}
//Рекурсивный поиск по дереву. Возвращается указатель на поддерево,
//ключевое значение коренного узла которого равно искомому
//Если такого значения в дереве нет, возвращается ноль
BinaryTree<T>* find(const T& pattern)
{
if(!pkey)
{
return 0;
}
if(pattern == *pkey)
{
return this;
}
if(pattern < *pkey)
{
if(!pleft)
{
return 0;
}
return pleft->find(pattern);
}
else
{
if(!pright)
{
return 0;
}
return pright->find(pattern);
}
}
//Удаляет правое поддерево
void removeLeft()
{
if(pleft)
{
delete pleft;
pleft = 0;
}
}
//Удаляет левое поддерево
void removeRight()
{
if(pright)
{
delete pright;
pright = 0;
}
}
//Удаляет выбранный элемент, если он находится в дереве.
//Дерево перестраивается, чтобы соответствовать структуре двоичного дерева
bool remove(const T& pattern)
{
BinaryTree<T>* psearchResult = find(pattern);
if(!psearchResult)
{
return false;
}
else
{
BinaryTree<T>& searchResultParent = psearchResult->parent();
bool searchResultIsRight = (psearchResult->key() > searchResultParent.key() ? true : false);
if(psearchResult->isLeaf())
{
if(searchResultIsRight)
{
searchResultParent.removeRight();
return true;
}
else
{
searchResultParent.removeLeft();
return true;
}
}
if(!psearchResult->hasLeft())
{
BinaryTree<T>& searchResultRight = psearchResult->right();
(searchResultIsRight ? searchResultParent.pright : searchResultParent.pleft)
= &searchResultRight;
searchResultRight.pparent = &searchResultParent;
pright = pleft = 0;
delete this;
return true;
}
else if(!psearchResult->hasRight())
{
BinaryTree<T>& searchResultLeft = psearchResult->left();
(searchResultIsRight ? searchResultParent.pright : searchResultParent.pleft)
= &searchResultLeft;
searchResultLeft.pparent = &searchResultParent;
pright = pleft = 0;
delete this;
return true;
}
else
{
std::list<T> leftList = psearchResult->left().makeList();
std::list<T> rightList = psearchResult->right().makeList();
std::list<T> leftAndRight;
leftAndRight.splice(leftAndRight.end(), leftList);
leftAndRight.splice(leftAndRight.end(), rightList);
if(searchResultIsRight)
{
searchResultParent.pright = 0;
}
else
{
searchResultParent.pleft = 0;
}
searchResultParent.insertFrom(leftAndRight.begin(), leftAndRight.end());
//TODO: Fix memory leaks
return true;
}
}
}
//Возвращает true, если у дерева нет поддеревьев
bool isLeaf() const
{
return !pleft && !pright;
}
//Возвращает true, если у дерева есть левое поддерево
bool hasLeft() const
{
return (pleft ? true : false);
}
//Возвращает true, если у дерева есть правое поддерево
bool hasRight() const
{
return (pright ? true : false);
}
//Возвращает true, если дерево пустое
bool empty() const
{
return !(haskey() && isLeaf());
}
//Классы для исключений
class NoValue{};
class NoSubtree{};
class NoParent{};
protected:
//Приватный конструктор для удобства задания родителей
BinaryTree(BinaryTree<T> *new_parent, const BinaryTree<T>& other = BinaryTree<T>())
: pkey(0), pleft(0), pright(0), pparent(new_parent)
{
if(other.hasKey())
{
pkey = new T(other.key());
if(other.hasLeft())
{
pleft = new BinaryTree<T>(this, other.left());
}
if(other.hasRight())
{
pright = new BinaryTree<T>(this, other.right());
}
}
}
private:
T *pkey; //указатель на ключевое значение
BinaryTree<T> *pparent; //указатель на родителя
BinaryTree<T> *pleft; //указатель на левое поддерево
BinaryTree<T> *pright; //указатель на правое поддерево
};
#endif /*_TREE_H_*/