Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 64262
Модуль Forms 63999
Пример работы с... 61137
ТЕХНОЛОГИИ ДОСТ... 60862
Имитационное мо... 56411
Реклама
Сейчас на сайте
Гостей: 9
На сайте нет зарегистрированных пользователей

Пользователей: 13,080
новичок: setan
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование литейного цеха на GPSS + Пояснительная записка
Моделирование интернет кафе на GPSS + Отчет
Метод конечных разностей для интерполяции/экстраполяции на Delphi

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Деревья со ссылками
позволяет упростить вывод элементов в различном порядке. Вы можете использовать тот же
прием, чтобы облегчить обращение к узлам дерева в произвольном порядке. На-
пример, если поместить ссылки в листья двоичного дерева, то выполнение сим-
метричного и обратного обходов упростится. Если дерево упорядоченное, то это
обход в прямом и обратном порядке сортировки.
При создании ссылок указатели на предшественников узла (симметричный
порядок) и потомков должны помещаться в неиспользованных указателях дочер-
них узлов. Если узел имеет неиспользованный левый указатель на потомка, сохра-
ните ссылку в позиции, указывающей на предшественника узла при симметрич-
ном обходе. Если узел имеет неиспользованный правый указатель на потомка,
сохраните ссылку в позиции, указывающей на дочерний узел при симметричном
обходе. Поскольку ссылки симметричны и ссылки левых потомков указывают на
предыдущих правых, а правых - на следующие узлы, этот тип деревьев называет-
ся деревом с симметричными ссылками (symmetrically threaded tree). На рис. 6.22
показано подобное дерево (потоки выделены пунктирными линиями).
Дерево с симметричными ссылками
Рис. 6.22. Дерево с симметричными ссылками
Поскольку ссылки занимают позиции указателей на дочерние узлы, необхо-
димо найти какое-то различие между ссылками и обычными указателями на до-
черние узлы. Проще всего это сделать, добавив в узлы новые поля, такие как Boolean
- HasLef tChi Id и HasRightChild, указывающие, есть ли у узла правые
и левые потомки.
Чтобы использовать ссылки для нахождения предшественника узла, необхо-
димо проверить левый указатель на дочерний узел. Если указатель - ссылка, то он
указывает на предшественника узла. Если указатель имеет значение nil, то этот
узел является первым в дереве, поэтому не имеет предшественника. В обратном
случае двигайтесь по направлению этого левого указателя. Затем следуйте за пра-
вым указателем потомка, пока не достигнете узла, в котором вместо правого по-
томка имеется ссылка. Этот узел (а не тот, на который указывает ссылка) - пред-
шественник первоначального узла. Он, в свою очередь, является самым правым
в левой от исходного узла ветви дерева. Следующий код показывает, как можно
найти предшественника узла в Delphi.
function Predecessor(node : PThreadedNode) : PThreadedNode;
var
child : PThreadedNode;
begin
if (nodeA.LeftChild=nil) then
// Это первый узел при симметричном обходе.
Predecessor := nil
else if (node^.HasLeftChild) then begin
// Это указатель на узел.
// Нахождение крайнего правого узла слева.
child := node^.LeftChild;
while (child^.HasRightChild) do
child := child^.RightChild;
Predecessor := child;
end else
// Ссылка указывает на предшественника.
Predecessor := node^ .LeftChild;
end;



Аналогично выполняется поиск следующего узла. Если правый указатель на
дочерний узел - ссылка, то он указывает на потомка узла. Если указатель имеет
значение nil, этот узел - последний в дереве, поэтому он не имеет потомка. В об-
ратном случае следуйте за указателем на правый дочерний узел. Затем двигайтесь
за указателями на левый дочерний узел до тех пор, пока не достигнете узла со
ссылкой для указатель левого дочернего узла. Тогда найденный узел окажется сле-
дующим за исходным. Это будет самый левый узел в правой от исходного узла
ветви дерева.
Удобно также ввести функции, определяющие положение первого и последне-
го узлов дерева. Чтобы найти первый узел, просто следуйте за левыми указателя-
ми на дочерние узлы вниз от корня, пока не достигнете узла с нулевым указате-
лем. Чтобы найти последний узел, следуйте за правыми указателями на дочерние
узлы вниз от корня, пока не достигнете узла с нулевым указателем.
function FirstNode : PThreadedNode;
begin
Result := Root;
While (Result^.LeftChildonil) do
Result := Result^.LeftChild;
end;
function LastNode : PThreadedNode;
begin
Result := Root;
While (Result^.Right Childonil) do
Result:=Result^.RightChild;
end;



Используя эти функции, можно легко записать процедуры, которые отобра-
жают узлы дерева в прямом и обратном порядках.
procedure Inorder;
var
node : PThreadedNode;
begin
// Нахождение первого узла.
node := FirstNode;
// Обход списка.
while (nodeonil) do
begin
VisitNode(nodeA.Value);
node := Successor(node);
end;
end;
procedure Reverselnorder;
var
node : PThreadedNode;
begin
// Нахождение последнего узла.
node := LastNode;
// Обход списка.
while (nodeonil) do
begin
VisitNode(Node^.Value);
node := Predecessor(node);
end;



Процедура вывода узлов в порядке симметричного обхода, описанная ранее,
использует рекурсию. Устранить рекурсию вы можете с помощью этих новых про-
цедур, которые не используют ни рекурсию, ни системный стек.
Каждый указатель на потомка в дереве содержит либо связь с дочерним узлом,
либо поток для предшественника или потомка. Так как каждый узел имеет два ука-
зателя на дочерние узлы, то если в дереве всего N узлов, оно будет содержать 2 * N
связей и потоков. Приведенные алгоритмы обхода посещают каждую связь и поток
в дереве один раз, поэтому для их выполнения требуется О(2 * N) = O(N) шагов.
Эти процедуры можно немного ускорить, если отследить индексы первого и пос-
леднего узлов дерева. Тогда не нужно будет искать первый или последний узел пе-
ред выводом узлов по порядку. Поскольку эти алгоритмы обращаются ко всем N
узлам в дереве, время выполнения для алгоритмов также будет порядка O(N), но
на практике они работают немного быстрее.
Опубликовал Kest October 22 2009 12:08:41 · 0 Комментариев · 6316 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Turbo Pascal for ...
PBEditPack
Preview
Редактор текста (...
Delphi World 6.0
32 урока по Delphi
Сапёр
DateEdit
Конвертирование и...
Панель статистики...
Rss Parser
AUTOWEB
CABfiles
Sztransppanel
Prolog Interprete...
Dynamic Titles дл...
WinAmp
Шифрование по алг...
Интерактивный инт...
DelTrayIcon [Исхо...

Топ загрузок
Приложение Клие... 100455
Delphi 7 Enterp... 86165
Converter AMR<-... 20072
GPSS World Stud... 12525
Borland C++Buil... 11616
Borland Delphi ... 8526
Turbo Pascal fo... 7035
Visual Studio 2... 4992
Калькулятор [Ис... 4744
FreeSMS v1.3.1 3539
Случайные статьи
• Убедитесь, что е...
S-Video
autocad lt
Атрибуты и свойства
Еще про алгоритм find
Структура базы данных
• Kerberos
Моделирование и си...
Модули
Внешний DNS-сервер...
Шаринг
Агрегированные кон...
Ввод-вывод на прим...
Маршруты
Прием находится в ...
Передача коммутато...
Подвесной светильн...
Профессиональная к...
1.4.4. Параметры к...
Разделители
Точки останова
История языков про...
14-29):Табл
Пример кода програ...
Вид граничного режима
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?