Реализация класса InorderIterator.

↑

▷ Содержание

⇐ ПредыдущаяСтр 8 из 9Следующая ⇒

Итерационный симметричный метод прохождения эмулирует рекурсивное сканирование с помощью стека адресов узлов. Начиная с корня, осуществляется спуск вдоль левых поддеревьев. По пути указатель каждого пройденного узла запоминается в стеке. Процесс останавливается на узле с нулевым левым указателем, который становится первым посещаемым узлом в симметричном сканировании. Спуск от узла t и запоминание адресов узлов в стеке выполняет метод GoFarLeft. Вызовом этого метода с t=root ищется первый посещаемый узел (рис. 18).

// вернуть адрес крайнего узла на левой ветви узла t

// запомнить в стеке адреса всех пройденных узлов

template <class T>

TreeNode<T> *InorderIterator<T>::GoFArLeft(TreeNode<T> *t)

{

 // если t=NULL, вернуть NULL

 if (t == NULL)

 return NULL;

 // пока не встретится узел с нулевым левым указателем, спускаться по левым ветвям, запоминая в стеке S адреса пройденных узлов. Возвратить указатель на этот узел

 while (t->Left()!= NULL)

 {

 S.Push(t);

 t = t->Left();

 }

 return t;

}

Рис. 18.

После инициализации базового класса конструктор присваивает элементу данных root адрес корня бинарного дерева поиска. Узел для начала симметричного сканирования получается в результате вызова функции GoFarLeft с root в качестве параметра. Это значение запоминается в переменной сurrent.

// инициализировать флаг iterationComplete. Базовый класс сбрасывает его, но

// дерево может быть пустым. начальный узлел сканирования - крайний слева узел.

template <class T>

InorderIterator<T>::InorderIterator(TreeNode<T> *tree):

 Iterator<T>(), root(tree)

{

 iterationComplete = (root == NULL);

 current = GoFarLeft(root);

}

Метод Reset по существу является таким же, как и конструктор, за исключением того, что он очищает стек. Перед первым обращением к Next указатель current уже указывает на первый узел симметричного сканирования. Метод Next работает по следующему алгоритму. Если правая ветвь узла не пуста, перейти к его правому сыну и осуществить спуск по левым ветвям до узла с нулевым левым указателем, попутно запоминая в стеке адреса пройденных узлов.

Если правая ветвь узла пуста, то сканирование его левой ветви, самого узла и его правой ветви завершено. Адрес следующего узла, подлежащего обработке, находится в стеке. Если стек не пуст, удалить следующий узел. Если же стек пуст, то все узлы обработаны и сканирование завершено. Итерационное прохождение дерева, состоящего из пяти узлов, изображено на рисунке 19.

Рис. 19.

template <class T>

void InorderIterator<T>::Next(void)

{

 // ошибка, если все узлы уже посещались

 if (iterationComplete)

 {

 cerr << "Next: итератор прошел конец списка!" << endl;

 exit(1);

 }

 // current - текущий обрабатываемый узел

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

 if (current->Right()!= NULL)

 current = GoFarLeft(current->Right());

 // правого поддерева нет, но в стеке есть другие узлы, подлежащие обработке.

 // Вытолкнуть из стека новый текущий адрес, продвинуться вверх по дереву

 else if (!S.StackEmpty())

 current = S.Pop();

 // нет ни правого поддерева, ни узлов в стеке. Сканирование завершено

 else

 iterationComplete = 1;

}

Алгоритм TreeSort.

Когда объект типа InorderIterator осуществляет прохождение дерева поиска, узлы проходятся в сортированном порядке и, следовательно, можно построить еще один алгоритм сортировки, называемый TreeSort. Этот алгоритм предполагает, что элементы изначально хранятся в массиве. Поисковое дерево служит фильтром, куда элементы массива копируются в соответствии с алгоритмом вставки в бинарное дерево поиска. Осуществляя симметричное прохождение этого дерева и записывая элементы снова в массив, мы получаем в результате отсортированный список. На рисунке 20 показана сортировка 8 - элементного массива.

#include "bstree.h"

#include "treeiter.h"

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

template <class T>

void TreeSort(T arr[], int n)

{

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

 BinSTree<T> sortTree;

 int i;

 // вставить каждый элемент массива в поисковое дерево

 for (i=0; i<n; i++)

 sortTree.Insert(arr[i]);

 // объявить итератор симметричного прохождения для sortTree

 InorderIterator<T> treeSortIter(sortTree.GetRoot());

 // выполнить симметричное прохождение дерева

 // скопировать каждый элемент снова в массив

 i = 0;

 while (!treeSortIter.EndOfList())

 {

 arr[i++] = treeSortIter.Data();

 treeSortIter.Next();

 }

}

Рис. 20.

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США