Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Основные операции над деревьями.




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

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

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

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

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

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

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

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

Приведенные ниже программы процедур и функций могут быть непосредственно использованы при решении индивидуальных задач. Кроме выше указанных процедур приведены следующие процедуры и функции:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{=== Программный пример 6.2. Поиск звена по ключу === } Function Find(k:KeyType;d:TreePtr;var rez:TreePtr):bollean; { где k - ключ, d - корень дерева, rez - результат } Var p,g: TreePtr; b: boolean; Begin b:=false; p:=d; { ключ не найден } if d <> NIL then repeat q: =p; if p^.key = k then b:=true { ключ найден } else begin q:=p; { указатель на отца } if k < p^.key then p:=p^.left { поиск влево } else p:=p^.right { поиск вправо} end; until b or (p=NIL); Find:=b; rez:=q; End; { Find }

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

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

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

{=== Программный пример 6.3. Добавление звена ===} Procedure Dob (k:KeyType; var d:TreePtr; zap:data); { k - ключ, d - узел дерева, zap - запись } Var r,s: TreePtr; t: DataPtr; Begin if not Find(k,d,r) then begin (* Занесение в новое звено текста записи *) new(t); t^:=zap; new(s); s^.key:=k; s^.ssil:=t; s^.left:=NIL; s^.right:=NIL; if d = NIL then d:=s (* Вставка нового звена *) else if k < r^.key then r^.left:=s else r^.right:=s; end; End; { Dop }

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

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

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

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

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

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

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

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

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

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

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

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

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





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:



©2015- 2022 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.