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



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



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

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

  • 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);









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