Конструкторы и деструкторы
Конструктор класса BraidedSearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева, представленного в виде изолированного головного узла:
template BraidedSearchTree::BraidedSearchTree (int (*с) (Т, Т) ) : cmp(c) { win = root = new BraidedNode (NULL); }
Деструктор класса удаляет дерево целиком, обращаясь к деструктору головного узла:
template BraidedSearchTree::~BraidedSearchTree (void) { delete root; }
Использование ленты
Элемент данных win описывает окно для дерева - т. е. элемент win указывает на узел, над которым располагается окно. Компонентные функции next и prew перемещают окно на следующую или предыдущую позиции. Если окно находится в головной позиции, то функция next перемещает его на первую позицию, а функция prew - на последнюю позицию. Обе функции возвращают ссылку на элемент в новой позиции окна:
template Т BraidedSearchTree::next (void) { win = win->next(); return win->val; }
template Т BraidedSearchTree::prev(void) { win = win->prev(); return win->val; }
Компонентная функция val возвращает ссылку на элемент внутри окна. Если окно находится в головной позиции, то возвращается значение NULL.
template T BraidedSearchTree::val (void) { return win->val; }
Симметричный обход выполняется путем прохода по ленте от первой позиции до последней, применяя функцию visit для каждого элемента на своем пути:
template void BraidedSearchTree::inorder (void (*visit) (Т) ) { BraidedNode *n = root->next(); while (n != root) { (*visit)(n->val); n = n->next(); } }
Компонентные функции isFirst, isLast и isHead возвращают значение TRUE (истина), если окно находится в первой, последней или головной позициях соответственно.
template bool BraidedSearchTree::isFirst (void) { return (win == root->next() ) && (root != root->next ()); }
template bool BraidedSearchTree::isLast (void) { return (win == root->prev() ) && (root != root->next() ); }
template bool BraidedSearchTree::isHead (void) { return (win == root); }
Функция isEmpty возвращает значение TRUE (истина) только если текущее дерево пусто и состоит только из одиночного головного узла:
template bool BraidsdSearchTree::isEmpty () { return (root == root->next() ); }
1 2 3
8 8 8
|