ОСНОВНЫЕ ОПЕРАЦИИ НАД ДЕРЕВЬЯМИ

Над деревьями определены следующие основные операции, для которых приведены реализующие их программы.

1) Поиск узла с заданным ключом ( Find ).

2) Добавление нового узла ( Dob ).

3) Удаление узла ( поддерева ) ( Udal ).

4) Обход дерева в определенном порядке:

Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder);

Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder);

Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).

Кроме выше указанных процедур приведены следующие процедуры и функции:

1. процедура включения в стек при нисходящем обходе (Push_st);

2. функция извлечения из стека при нисходящем обходе (Pop_st);

3. процедура включения в стек при восходящем и смешанном обходе (S_Push);

4. функция извлечения из стека при восходящем и смешанном обходе (S_Pop).

Для прошитых деревьев:

1. функция нахождения сына данного узла ( Inson );

2. функция нахождения отца данного узла ( Inp );

3. процедура включения в дерево узла слева от данного (leftIn);

 

ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ).

Нужная вершина в дереве ищется по ключу. Поиск в бинарном дереве осуществляется следующим образом.

Пусть построено некоторое дерево и требуется найти звено с ключом X. Сначала сравниваем с X ключ, находящийся в корне дерева. В случае равенства поиск закончен и нужно возвратить указатель на корень в качестве результата поиска. В противном случае переходим к рассмотрению вершины, которая находится слева внизу, если ключ X меньше только что рассмотренного, или справа внизу, если ключ X больше только что рассмотренного. Сравниваем ключ X с ключом, содержащимся в этой вершине, и т.д. Процесс завершается в одном из двух случаев:

1) найдена вершина, содержащая ключ, равный ключу X;

2) в дереве отсутствует вершина, к которой нужно перейти для выполнения очередного шага поиска.

В первом случае возвращается указатель на найденную вершину. Во втором - указатель на звено, где остановился поиск, (что удобно для построения дерева ). Реализация функции Find приведена в приложении в программном примере 1.

 

ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ).

Для включения записи в дерево прежде всего нужно найти в дереве ту вершину, к которой можно "подвести" (присоединить) новую вершину, соответствующую включаемой записи. При этом упорядоченность ключей должна сохраняться.

Алгоритм поиска нужной вершины, вообще говоря, тот же самый, что и при поиске вершины с заданным ключом. Эта вершина будет найдена в тот момент, когда в качестве очередного указателя, определяющего ветвь дерева, в которой надо продолжить поиск, окажется указатель NIL (случай 2 функции Find ). Тогда процедура вставки записывается так, как в программном примере 2.

 

ОБХОД ДЕРЕВА.

Во многих задачах, связанных с деревьями, требуется осуществить систематический просмотр всех его узлов в определенном порядке. Такой просмотр называется прохождением или обходом дерева.

Бинарное дерево можно обходить тремя основными способами: нисходящим, смешанным и восходящим (возможны также обратный нисходящий, обратный смешанный и обратный восходящий обходы). Принятые выше названия методов обхода связаны с временем обработки корневой вершины: До того как обработаны оба ее поддерева (Preorder), после того как обработано левое поддерево, но до того как обработано правое (Inorder), после того как обработаны оба поддерева (Postorder). Используемые в переводе названия методов отражают направление обхода в дереве: от корневой вершины вниз к листьям - нисходящий обход; от листьев вверх к корню - восходящий обход, и смешанный обход - от самого левого листа дерева через корень к самому правому листу.

Схематично алгоритм обхода двоичного дерева в соответствии с нисходящим способом может выглядеть следующим образом:

1. В качестве очередной вершины взять корень дерева. Перейти к пункту 2.

2. Произвести обработку очередной вершины в соответствии с требованиями задачи. Перейти к пункту 3.

3.а) Если очередная вершина имеет обе ветви, то в качестве новой вершины выбрать ту вершину, на которую ссылается левая ветвь, а вершину, на которую ссылается правая ветвь, занести в стек; перейти к пункту 2;

3.б) если очередная вершина является конечной, то выбрать в качестве новой очередной вершины вершину из стека, если он не пуст, и перейти к пункту 2; если же стек пуст, то это означает, что обход всего дерева окончен, перейти к пункту 4;

3.в) если очередная вершина имеет только одну ветвь, то в качестве очередной вершины выбрать ту вершину, на которую эта ветвь указывает, перейти к пункту 2.

4. Конец алгоритма.

 

Для примера рассмотрим возможные варианты обхода дерева (рис.6.26).

При обходе дерева представленного на рис.6.26 этими тремя методами мы получим следующие последовательности: ABCDEFG (нисходящий); CBAFEDG (смешанный); CBFEGDA ( восходящий ).

Рис.6.26. Схема дерева

 

НИСХОДЯЩИЙ ОБХОД (Preorder, r_Preorder).

В соответствии с алгоритмом, приведенным выше, текст процедуры имеет вид (Программный пример 3):

Трассировка нисходящего обхода приведена в табл.6.1:

Таблица 6.1

 

РЕКУРСИВНЫЙ НИСХОДЯЩИЙ ОБХОД.

Алгоритм существенно упрощается при использовании рекурсии. Так, нисходящий обход можно описать следующим образом:

1). Обработка корневой вершины;

2). Нисходящий обход левого поддерева;

3). Нисходящий обход правого поддерева.

Алгоритм рекурсивного нисходящего обхода реализован в программном примере 4.

 

CМЕШАННЫЙ ОБХОД (Inorder, r_Inorder).

Смешанный обход можно описать следующим образом:

1) Спуститься по левой ветви с запоминанием вершин в стеке;

2) Если стек пуст то перейти к п.5;

3) Выбрать вершину из стека и обработать данные вершины;

4) Если вершина имеет правого сына, то перейти к нему; перейти к п.1.

5) Конец алгоритма.

В программном примере 5. реализован алгоритм смешанного обхода дерева.

Трассировка смешанного обхода приведена в табл. 6.2:

Таблица 6.2

 

РЕКУРСИВНЫЙ СМЕШАННЫЙ обход описывается следующим образом:

1) Смешанный обход левого поддерева;

2) Обработка корневой вершины;

3) Смешанный обход правого поддерева.

Текст программы рекурсивной процедуры (r_Inorder) демонстрируется в программном примере 6.

 

ВОСХОДЯЩИЙ ОБХОД (Postorder, r_Postorder).

Трудность заключается в том, что в отличие от Preorder в этом алгоритме каждая вершина запоминается в стеке дважды: первый раз - когда обходится левое поддерево, и второй раз - когда обходится правое поддерево. Таким образом, в алгоритме необходимо различать два вида стековых записей: 1-й означает, что в данный момент обходится левое поддерево; 2-й - что обходится правое, поэтому в стеке запоминается указатель на узел и признак (код-1 и код-2 соответственно).

Алгоритм восходящего обхода можно представить следующим образом:

1) Спуститься по левой ветви с запоминанием вершины в стеке как 1-й вид стековых записей;

2) Если стек пуст, то перейти к п.5;

3) Выбрать вершину из стека, если это первый вид стековых записей, то возвратить его в стек как 2-й вид стековых запи сей; перейти к правому сыну; перейти к п.1, иначе перейти к п.4;

4) Обработать данные вершины и перейти к п.2;

5) Конец алгоритма.

Текст программы процедуры восходящего обхода (Postorder) представлен в программном примере 7.

 

РЕКУРСИВНЫЙ СМЕШАННЫЙ ОБХОД описывается следующим образом:

1). Восходящий обход левого поддерева;

2). Восходящий обход правого поддерева;

3). Обработка корневой вершины.

Текст программы процедуры рекурсивного обхода (r_Postorder) демонстрируется в программном примере 8.

Если в рассмотренных выше процедурах поменять местами поля left и right, то получим процедуры обратного нисходящего, обратного смешанного и обратного восходящего обходов.