Существует много приложений, в которых требуется выполнение некоторой определенной операции Р над каждой вершиной дерева. операцию Р в этом случае можно мыслить как параметр некоторой более общей задачи – «посещения» всех вершин или «обхода дерева». Если удается найти некоторое правило, обеспечивающее однозначную упорядоченность вершин при всяком обходе, то получаем аналог линейной упорядоченности для соответствующего класса нелинейных структур. В этом случае для многих алгоритмов работы с деревом справедливы утверждения: переход к следующей вершине, переход к предыдущей вершине. Возможность введения принципа упорядочения основана на двух положениях:
- дерево является рекурсивно определяемой структурой,
- поддеревья для каждой вершины упорядочены.
Отсюда вытекает три принципа упорядоченного обхода позиционного бинарного дерева (рис.11.1):
- нисходящий обход (R, A, B);
- восходящий обход (А, B, R);
- смешанный (A, R, B).
R
 |
 |
A B
Левое Правое поддерево поддерево
Пусть t – указатель на корень бинарного дерева, а
Down (t:Ptr)
начало
 |
да
t=NULL
конец
 |
|||
 |
|||
P(t)
 |
down(t^.left) down(t^.right)
Вместо рекурсивной процедуры может быть использован итерационный алгоритм со стеком для хранения ссылок на обнаруженные, но не обработанные ветви дерева. Пример соответствующего обхода с данными об изменении стека ссылок в процессе реализации итерационного алгоритма представлен на рис.11.3.
A Состояние стека
при обходе дерева
B H H
E H
M E H
E H
C E Y X F H
H
X
D M G F
Рисунок 11.3.
Смешанный подход реализуется рекурсивной процедурой:
- смешанный обход левого поддерева,
- обработка корня дерева,
- смешанный обход правого поддерева.
Использование смешанного обхода, бинарного дерева поиска (рис.11.4), построенного для последовательности чисел:
13, 25, -7, 4, 15, 161, 151, 41, 22.
13
-7 25
 |
 |
 |
|||
4 15 161
 |
 |
||
22
151
 |
41
Рисунок 11.4
Приводит к упорядочению исходной последовательности по возрастанию. Нетрудно показать, что это справедливо для любого дерева поиска, и на этом может основываться достаточно эффективный алгоритм сортировки массивов.
Рассматривая предложенное выше связанное представление бинарных деревьев, легко обнаружить, что в нем имеется много указателей типа NULL. Используя индукцию, можно показать, что в представлении бинарного дерева с N вершинами при использовании связанного представления дерева N+1 указателей имеют значение NULL.
Это не занятое пространство можно использовать для некоторой модификации ранее приведенного представления позиционных бинарных деревьев.. В предлагаемом представлении пустые указатели заменяются указателями нитями, которые адресуют вершины дерева, не связанные с данной ребрами, но следующие за ней при установленном варианте обхода (рис.11.5)
A
|
lp |
info |
rp |
||||||||||||
|
|
B |
E |
||||||||||||
|
lp |
info |
rp |
lp |
info |
rp |
|||||||||
|
|
C |
D |
F |
G |
||||||||||
|
|
info |
PE |
info |
lp |
info |
rp |
info |
|||||||
|
|
H |
I |
||||||||||||
|
|
info |
PI |
info |
PG |
Рисунок 11.5.
То есть не используемое значение указателя можно заменить адресом, указывающим на вершину, которая следует за данной в соответствии с тем порядком обхода, для которого прошивалось дерево. Различие связей и нитей можно показать через дополнительный флаг адреса.
Прошивка дерева кроме экономии памяти решает один принципиально важный вопрос. Она позволяет обходить дерево не с первой вершины, а с текущей. Тем самым некоторая операция может выполняться для некоторого подмножества упорядоченного множества вершин бинарного дерева.
Прошивка дерева сокращает потребность в дополнительной памяти и ускоряет обход дерева. В то же время включение новой вершины в прошитое дерево в общем случае занимает больше времени, чем включение в непрошитое дерево, поскольку при этом требуется поддерживать не только структурные связи, но и связи по нитям.
Двоичные деревья часто употребляются для представления множества данных, среди которых идет поиск элементов по уникальному ключу.
Если дерево организовано так, что для каждой вершины Р справедливо утверждение, что все ключи левого поддерева Р меньше ключа key данной вершины, а все ключи правого поддерева больше key, то такое дерево принято называть деревом поиска.
Примером может служить частотный словарь. Задача заключается в том, что в заранее заданной последовательности требуется определить частоту вхождения каждого из слов, используемых в некотором текстовом файле. Это означает, что любое слово надо искать в дереве, причем в начале дерево не содержит вершин. Если слово найдено, то счетчик вхождений увеличивается на единицу, если нет, то в дерево включается новое слово.
Определим тир Ptr следующим образом:
Type Ptr=^retro;
Retro=record
Key:integer;
Qt:integer;
Lp:Ptr;
Rp:Ptr
End;
На рис.11.6 представлена блок-схема модификации бинарного дерева при анализе очередного слова в частотном словаре с идентифицирующим кодом x:
Search (x:integer, var p: Ptr).
Рисунок 11.6.
К сожалению, исключение элемента из дерева поиска обычно происходит не так просто, как включение. Простым оно оказывается лишь в том случае, если исключаемый элемент является терминальной вершиной или вершиной с одним потомком. В противном случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. Очевидно соответствующие вершины могут иметь не более одного поддерева. На рис.11.7 демонстрируются различные случаи удаления заданной вершины (на рисунке эта вершина отмечена стрелкой.).
Рисунок 11.7.
Все детали приводятся в рекурсивном алгоритме соответствующей процедуры delete:
Delete (x:integer; var
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
PD
