Модели и структуры данных



         

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


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

  • 1) Поиск узла с заданным ключом ( Find ).
  • 2) Добавление нового узла ( Dob ).
  • 3) Удаление узла ( поддерева ) ( Udal ).
  • 4) Обход дерева в определенном порядке:

    • Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder);
    • Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder);
    • Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).

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

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

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

  • функция нахождения сына данного узла ( Inson );
  • функция нахождения отца данного узла ( Inp );
  • процедура включения в дерево узла слева от данного (leftIn);

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

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

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

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

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


Содержание  Назад  Вперед