Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Структуры данных и хэширование / Словари для произвольных данных / Двоичные деревья /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Cвязанные двоичные деревья поиска - Программирование от RIN.RU
Cвязанные двоичные деревья поиска



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


Конструктор класса 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  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь